Paper 2019/616

Channels of Small Log-Ratio Leakage and Characterization of Two-Party Differentially Private Computation

Iftach Haitner, Noam Mazor, Ronen Shaltiel, and Jad Silbak

Abstract

Consider a PPT two-party protocol $\mathrm{\Pi }=(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 $\mathrm{\Pi }$ has $\alpha$-agreement if $Pr[O^A=O^B]=1/2+\alpha$. 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{|}_{O^A=O^B}$ and $V^P{|}_{O^A\ne O^B}$. 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 $ϵ<<\alpha$ 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 $$ over domain $$ is the minimal $$ for which, for every $$. In the computational setting, we use computational indistinguishability from having log-ratio distance $$. We show that a protocol with (noticeable) accuracy $$ can be transformed into an OT protocol (note that this allows $$). We complete the picture, in this respect, showing that a protocol with $$ 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]. Specifically, we show that for any (noticeable) $$, a two-party protocol that computes the XOR function with $$-accuracy and $$-differential privacy can be transformed into an OT protocol. This improves upon Goyal et al. that only handle $$, and upon Haitner et al. who showed that such a protocol implies (infinitely-often) key agreement (and not OT). Our characterization is tight since OT does not follow from protocols in which $$, and extends to functions (over many bits) that ``contain'' an ``embedded copy'' of the XOR function.