Paper 2022/312

Low Communication Complexity Protocols, Collision Resistant Hash Functions and Secret Key-Agreement Protocols

Shahar P. Cohen
Moni Naor

We study communication complexity in computational settings where bad inputs may exist, but they should be hard to find for any computationally bounded adversary. We define a model where there is a source of public randomness but the inputs are chosen by a computationally bounded adversarial participant after seeing the public randomness. We show that breaking the known communication lower bounds of the private coins model in this setting is closely connected to known cryptographic assumptions. We consider the simultaneous messages model and the interactive communication model and show that for any non trivial predicate (with no redundant rows, such as equality): 1. Breaking the $ \Omega(\sqrt n) $ bound in the simultaneous message case or the $ \Omega(\log n) $ bound in the interactive communication case, implies the existence of distributional collision-resistant hash functions (dCRH). This is shown using techniques from Babai and Kimmel (CCC '97). Note that with a CRH the lower bounds can be broken. 2. There are no protocols of constant communication in this preset randomness settings (unlike the plain public randomness model). The other model we study is that of a stateful ``free talk", where participants can communicate freely before the inputs are chosen and may maintain a state, and the communication complexity is measured only afterwards. We show that efficient protocols for equality in this model imply secret key-agreement protocols in a constructive manner. On the other hand, secret key-agreement protocols imply optimal (in terms of error) protocols for equality.

Available format(s)
Publication info
A minor revision of an IACR publication in CRYPTO 2022
impossibility results communication complexity black-box separation new models
Contact author(s)
moni naor @ weizmann ac il
2022-07-10: last of 2 revisions
2022-03-07: received
See all versions
Short URL
Creative Commons Attribution


      author = {Shahar P.  Cohen and Moni Naor},
      title = {Low Communication Complexity Protocols, Collision Resistant Hash Functions and Secret Key-Agreement Protocols},
      howpublished = {Cryptology ePrint Archive, Paper 2022/312},
      year = {2022},
      note = {\url{}},
      url = {}
Note: In order to protect the privacy of readers, does not use cookies or embedded third party content.