COMPUTATIONAL TWO-PARTY CORRELATION: A DICHOTOMY FOR KEY-AGREEMENT PROTOCOLS.

Let π be an efficient two-party protocol that, given security parameter κ, both parties output single bits Xκ and Yκ, respectively. We are interested in how (Xκ; Yκ) "appears" to an efficient adversary that only views the transcript Tκ. We make the following contributions: (a)We develop new tools to argue about this loose notion and show (modulo some caveats) that for every such protocol π, there exists an efficient simulator such that the following holds: on input Tκ, the simulator outputs a pair (X0κ ; Y 0κ) such that (X0κ ; Y 0κ ; Tκ) is (somewhat) computationally indistinguishable from (Xκ; Yκ; Tκ). (b) We use these tools to prove the following dichotomy theorem: every such protocol π is either uncorrelated|it is (somewhat) indistinguishable from an efficient protocol whose parties interact to produce Tκ, but then choose their outputs independently from some product distribution (that is determined in poly-time from Tκ), or the protocol implies a key-agreement protocol (for infinitely many κ's). Uncorrelated protocols are uninteresting from a cryptographic viewpoint, as the correlation between outputs is (computationally) trivial. Our dichotomy shows that every protocol is either completely uninteresting or implies key-agreement. (c) We use the above dichotomy to make progress on open problems on minimal cryptographic assumptions required for differentially private mechanisms for the XOR function. (d) A subsequent work [I. Haitner, N. Makriyannis, and E. Omri, in Theory of Cryptography Conference, Springer, Cham, Switzerland, 2018, pp. 539{562] uses the above dichotomy to makes progress on a long-standing open question regarding the complexity of fair two-party coin-ipping protocols. We also highlight the following two ideas regarding our technique: (a) The simulator algorithm is obtained by a carefully designed \competition" between efficient algorithms attempting to forecast (Xκ; Yκ)|Tκ=t. The winner is used to simulate the outputs of the protocol. (b) Our key-agreement protocol uses the simulation to reduce to an information theoretic setup and is, in some sense, a non-black-box. [ABSTRACT FROM AUTHOR]