# [Resource Topic] 2019/616: Channels of Small Log-Ratio Leakage and Characterization of Two-Party Differentially Private Computation

Welcome to the resource topic for 2019/616

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

Authors: Iftach Haitner, Noam Mazor, Ronen Shaltiel, Jad Silbak

Abstract:

Consider a PPT two-party protocol \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 \Pi has \alpha-agreement if Pr[O^A=O^B]=1/2+\alpha. The leakage of \epsilon is the amount of information a party obtains about the event \{O^A=O^B\}; that is, the leakage \epsilon is the maximum, over P\in \{A,B\}, of the distance between V^P|_{O^A=O^B} and V^P|_{O^A\neq 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 \epsilon<<\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 X,Y over domain \Omega is the minimal \epsilon\geq 0 for which, for every v\in\Omega, \log(Pr[X=v]/Pr[Y=v])\in [-\epsilon,\epsilon]. In the computational setting, we use computational indistinguishability from having log-ratio distance \epsilon. We show that a protocol with (noticeable) accuracy \alpha\in\Omega(\epsilon^2) can be transformed into an OT protocol (note that this allows \epsilon>>\alpha). We complete the picture, in this respect, showing that a protocol with \alpha\in o(\epsilon^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]. Specifically, we show that for any (noticeable) \alpha\in\Omega(\epsilon^2), a two-party protocol that computes the XOR function with \alpha-accuracy and \epsilon-differential privacy can be transformed into an OT protocol. This improves upon Goyal et al. that only handle \alpha\in\Omega(\epsilon), 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 \alpha\in o(\epsilon^2), and extends to functions (over many bits) that contain'' an embedded copy’’ of the XOR function.

Feel free to post resources that are related to this paper below.

Example resources include: implementations, explanation materials, talks, slides, links to previous discussions on other websites.