Computational Two-Party Correlation: A Dichotomy for Key-Agreement Protocols
This work addresses foundational issues in cryptography for protocol designers, showing that non-trivial correlation inherently requires key-agreement, with incremental applications to privacy and fairness.
The paper tackles the problem of characterizing the computational correlation in two-party protocols, proving a dichotomy theorem that every such protocol is either uncorrelated (with trivial output correlation) or implies key-agreement, and applies this to advance open problems in differentially private mechanisms and fair coin-flipping.
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: $\bullet$ 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_κ)$. $\bullet$ 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. $\bullet$ We use the above dichotomy to make progress on open problems on minimal cryptographic assumptions required for differentially private mechanisms for the XOR function. $\bullet$ 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.