Computational Two-Party Correlation: A Dichotomy for Key-Agreement Protocols
share
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: ∙ 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 (X'_κ ,Y'_κ) such that (X'_κ,Y'_κ,T_κ) is (somewhat) computationally indistinguishable from (X_κ,Y_κ,T_κ). ∙ 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. ∙ We use the above dichotomy to make progress on open problems on minimal cryptographic assumptions required for differentially private mechanisms for the XOR function. ∙ A subsequent work of Haitner et al. uses the above dichotomy to makes progress on a longstanding open question regarding the complexity of fair two-party coin-flipping protocols.
READ FULL TEXT