Ronen Shaltiel

Iftach Haitner, Noam Mazor, Ronen Shaltiel et al.

Consider a PPT two-party protocol $π=(A,B)$ in which the parties get no private inputs and obtain outputs $O^A,O^B\in \{0,1\}$, and let $V^A$ and $V^B$ denote the parties' individual views. Protocol $π$ has $α$-agreement if $Pr[O^A=O^B]=1/2+α$. The leakage of $π$ is the amount of information a party obtains about the event $\{O^A=O^B\}$; that is, the leakage $ε$ is the maximum, over $P\in\{A,B\}$, of the distance between $V^P|OA=OB$ and $V^P|OA\neq OB$. Typically, this distance is measured in statistical distance, or, in the computational setting, in computational indistinguishability. For this choice, Wullschleger [TCC 09] showed that if $α>>ε$ then the protocol can be transformed into an OT protocol. We consider measuring the protocol leakage by the log-ratio distance (which was popularized by its use in the differential privacy framework). The log-ratio distance between X,Y over domain Ωis the minimal $ε>0$ for which, for every $v\inΩ$, $log(Pr[X=v]/Pr[Y=v])\in [-ε,ε]$. In the computational setting, we use computational indistinguishability from having log-ratio distance $ε$. We show that a protocol with (noticeable) accuracy $α\inΩ(ε^2)$ can be transformed into an OT protocol (note that this allows $ε>>α$). We complete the picture, in this respect, showing that a protocol with $α\in o(ε^2)$ does not necessarily imply OT. Our results hold for both the information theoretic and the computational settings, and can be viewed as a "fine grained" approach to "weak OT amplification". We then use the above result to fully characterize the complexity of differentially private two-party computation for the XOR function, answering the open question put by Goyal, Khurana, Mironov, Pandey, and Sahai [ICALP 16] and Haitner, Nissim, Omri, Shaltiel, and Silbak [FOCS 18].

Iftach Haitner, Kobbi Nissim, Eran Omri et al.

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.