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.
ePrint: https://eprint.iacr.org/2019/616
See all topics related to this paper.
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.
For more information, see the rules for Resource Topics .