Paper 2019/616
Channels of Small LogRatio Leakage and Characterization of TwoParty Differentially Private Computation
Iftach Haitner, Noam Mazor, Ronen Shaltiel, and Jad Silbak
Abstract
Consider a PPT twoparty 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 logratio distance (which was popularized by its use in the differential privacy framework). The logratio 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 logratio 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 twoparty 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 twoparty 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 (infinitelyoften) 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.
Metadata
 Available format(s)
 Category
 Foundations
 Publication info
 Preprint. MINOR revision.
 Keywords
 oblivious transferdifferential privacyhardness amplification
 Contact author(s)

iftachh @ cs tau ac il
noammaz @ gmail com
jadsilbak @ gmail com
ronen @ cs haifa ac il  History
 20190919: revised
 20190603: received
 See all versions
 Short URL
 https://ia.cr/2019/616
 License

CC BY
BibTeX
@misc{cryptoeprint:2019/616, author = {Iftach Haitner and Noam Mazor and Ronen Shaltiel and Jad Silbak}, title = {Channels of Small LogRatio Leakage and Characterization of TwoParty Differentially Private Computation}, howpublished = {Cryptology ePrint Archive, Paper 2019/616}, year = {2019}, note = {\url{https://eprint.iacr.org/2019/616}}, url = {https://eprint.iacr.org/2019/616} }