Computational Two-Party Correlation

摘要

Let be an e cient two-party protocol that given security parameter , both parties outputsingle bits X and Y , respectively. We are interested in how (X ; Y ) ppears" to an e cientadversary 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 e cient simulator such that the follow-ing 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 ). We use these tools to prove the following dichotomy theorem: every such protocol is:{ either uncorrelated | it is (somewhat) indistinguishable from an e cient protocolwhose parties interact to produce T , but then choose their outputs independentlyfrom some product distribution (that is determined in poly-time from T ),{ or, the protocol implies a key-agreement protocol (for in nitely many ).Uncorrelated protocols are completely uninteresting from a cryptographic viewpoint, asthe correlation between outputs is uninteresting. Our dichotomy shows that every protocolis either completely uninteresting or implies key-agreement. We use the above dichotomy to make progress on open problems on minimal cryptographicassumptions required for di erentially private mechanisms for the XOR function. A subsequent work of Haitner et al. uses the above dichotomy to makes progress on a long-standing open question regarding the complexity of fair two-party coin-ipping protocols.We highlight the following two ideas regarding our technique: The simulator algorithm is obtained by a carefully designed competition" between e cientalgorithms attempting to forecast ((X ; Y )jT = t). The winner is used to simulate theoutputs of the protocol. To the best of our knowledge, this idea has not been used before(at least in this context). Our key-agreement protocol uses the simulation to reduce to an information theoreticsetup, and is in some sense non-black box.