Communication Lower Bounds of Key-Agreement Protocols via Density Increment Arguments
- LecturerMr. Mi-Ying Huang (University of Southern California)
Host: Kai-Min Chung - Time2023-07-18 (Tue.) 10:15 ~ 12:30
- LocationAuditorium 101 at IIS new Building
Abstract
Key-agreement protocols in the random oracle model (ROM) offer provable security and serve as an alternative to public-key cryptography. In ROM, all parties, including potential eavesdroppers, have access to a random oracle, which acts as an ideal hard function in symmetric cryptography. However, Impagliazzo and Rudich (STOC 1989) and Barak and Mahmoody (Crypto 2009) demonstrated that these protocols have limited security. Specifically, an adversary making $[@BackSlash]ell$ queries can reveal the key with $O([@BackSlash]ell^2)$ queries, matching the security gap in Merkle's Puzzles, a well-known key-agreement protocol proposed by Merkle (CACM 78).
Apart from query complexity, the communication complexity of two-party protocols in ROM is a practical concern. Haitner et al. (ITCS 2019) observed that to achieve secrecy against an eavesdropper with $O([@BackSlash]ell^2)$ queries in Merkle's Puzzles, the honest parties must exchange at least $[@BackSlash]Omega([@BackSlash]ell)$ bits. They conjectured that high communication complexity is inevitable, suggesting that any $[@BackSlash]ell$-query protocol with $c$ communication bits is only secure against an $O(c[@BackSlash]cdot [@BackSlash]ell)$-query adversary. In this work, we affirm this conjecture for all non-adaptive protocols with perfect completeness.
Apart from query complexity, the communication complexity of two-party protocols in ROM is a practical concern. Haitner et al. (ITCS 2019) observed that to achieve secrecy against an eavesdropper with $O([@BackSlash]ell^2)$ queries in Merkle's Puzzles, the honest parties must exchange at least $[@BackSlash]Omega([@BackSlash]ell)$ bits. They conjectured that high communication complexity is inevitable, suggesting that any $[@BackSlash]ell$-query protocol with $c$ communication bits is only secure against an $O(c[@BackSlash]cdot [@BackSlash]ell)$-query adversary. In this work, we affirm this conjecture for all non-adaptive protocols with perfect completeness.