Paper 2023/1349

Communication Lower Bounds of Key-Agreement Protocols via Density Increment Arguments

Mi-Ying (Miryam) Huang, University of Southern California
Xinyu Mao, University of Southern California
Guangxu Yang, University of Southern California
Jiapeng Zhang, University of Southern California
Abstract

Constructing key-agreement protocols in the random oracle model (ROM) is a viable method to assess the feasibility of developing public-key cryptography within Minicrypt. Unfortunately, as shown by Impagliazzo and Rudich (STOC 1989) and Barak and Mahmoody (Crypto 2009), such protocols can only guarantee limited security: any $\ell$-query protocol can be attacked by an $O(\ell^2)$-query adversary. This quadratic gap matches the key-agreement protocol proposed by Merkle (CACM 78), known as Merkle's Puzzles. Besides query complexity, the communication complexity of key-agreement protocols in the ROM is also an interesting question in the realm of find-grained cryptography, even though only limited security is achievable. Haitner et al. (ITCS 2019) first observed that in Merkle's Puzzles, to obtain secrecy against an eavesdropper with $O(\ell^2)$ queries, the honest parties must exchange $\Omega(\ell)$ bits. Therefore, they conjectured that high communication complexity is unavoidable, i.e., any $\ell$-query protocols with $c$ bits of communication could be attacked by an $O(c\cdot \ell)$-query adversary. This, if true, will suggest that Merkle's Puzzle is also optimal regarding communication complexity. Building upon techniques from communication complexity, Haitner et al. (ITCS 2019) confirmed this conjecture for two types of key agreement protocols with certain natural properties. This work affirms the above conjecture for all non-adaptive protocols with perfect completeness. Our proof uses a novel idea called density increment argument. This method could be of independent interest as it differs from previous communication lower bounds techniques (and bypasses some technical barriers).

Metadata
Available format(s)
PDF
Category
Foundations
Publication info
Published elsewhere. TCC 2023
Keywords
Key-agreementrandom oraclecommunication complexiy
Contact author(s)
miying huang @ usc edu
xinyumao @ usc edu
guangxuy @ usc edu
jiapengz @ usc edu
History
2023-09-11: approved
2023-09-10: received
See all versions
Short URL
https://ia.cr/2023/1349
License
Creative Commons Attribution
CC BY

BibTeX

@misc{cryptoeprint:2023/1349,
      author = {Mi-Ying (Miryam) Huang and Xinyu Mao and Guangxu Yang and Jiapeng Zhang},
      title = {Communication Lower Bounds of Key-Agreement Protocols via Density Increment Arguments},
      howpublished = {Cryptology {ePrint} Archive, Paper 2023/1349},
      year = {2023},
      url = {https://eprint.iacr.org/2023/1349}
}
Note: In order to protect the privacy of readers, eprint.iacr.org does not use cookies or embedded third party content.