Paper 2022/312

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

Shahar P. Cohen and Moni Naor

Abstract

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.

Metadata
Available format(s)
PDF
Category
Foundations
Publication info
Preprint.
Keywords
impossibility resultscommunication complexityblack-box separationnew models
Contact author(s)
shahar cohen @ weizmann ac il
moni naor @ weizmann ac il
History
2022-03-16: revised
2022-03-07: received
See all versions
Short URL
https://ia.cr/2022/312
License
Creative Commons Attribution
CC BY

BibTeX

@misc{cryptoeprint:2022/312,
      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{https://eprint.iacr.org/2022/312}},
      url = {https://eprint.iacr.org/2022/312}
}
Note: In order to protect the privacy of readers, eprint.iacr.org does not use cookies or embedded third party content.