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

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 Ω( √ n) bound in the simultaneous message case or the Ω(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 [BK97]. 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.