Weizmann Logo
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style



TR18-071 | 15th April 2018 12:26

Computational Two-Party Correlation


Authors: Iftach Haitner, Kobbi Nissim, Eran Omri, Ronen Shaltiel, Jad Silbak
Publication: 15th April 2018 12:26
Downloads: 77


Let $\pi$ be an efficient two-party protocol that given security parameter $\kappa$, both parties output single bits $X_\kappa$ and $Y_\kappa$, respectively. We are interested in how $(X_\kappa,Y_\kappa)$ ``appears'' to an efficient adversary that only views the transcript $T_\kappa$. We make the following contributions:

\item We develop new tools to argue about this loose notion, and show (modulo some caveats) that for every such protocol $\pi$, there exists an efficient \textit{simulator} such that the following holds: on input $T_\kappa$, the simulator outputs a pair $(X'_\kappa,Y'_\kappa)$ such that $(X'_\kappa,Y'_\kappa,T_\kappa)$ is (somewhat) \emph{computationally indistinguishable} from $(X_\kappa,Y_\kappa,T_\kappa)$.

\item We use these tools to prove the following \emph{dichotomy theorem}: every such protocol $\pi$ is:
\item either \textit{uncorrelated} --- it is (somewhat) indistinguishable from an efficient protocol whose parties interact to produce $T_\kappa$, but then choose their outputs \emph{independently} from some product distribution (that is determined in poly-time from $T_\kappa$),

\item or, the protocol implies a key-agreement protocol (for infinitely many $\kappa$).

Uncorrelated protocols are completely uninteresting from a cryptographic viewpoint, as the correlation between outputs is uninteresting. Our dichotomy shows that every protocol is either completely uninteresting or implies key-agreement.

\item We use the above dichotomy to make progress on open problems on minimal cryptographic assumptions required for differentially private mechanisms for the XOR function.

\item A subsequent work of \citeauthor{HaitnerMO18} uses the above dichotomy to makes progress on a long-standing open question regarding the complexity of fair two-party coin-flipping protocols.

We highlight the following two ideas regarding our technique:
\item The simulator algorithm is obtained by a carefully designed ``competition'' between efficient algorithms attempting to forecast $((X_\kappa,Y_\kappa)|T_\kappa=t)$. The winner is used to simulate the outputs of the protocol. To the best of our knowledge, this idea has not been used before (at least in this context).
\item Our key-agreement protocol uses the simulation to reduce to an information theoretic setup, and is in some sense non-black box.

ISSN 1433-8092 | Imprint