## CryptoDB

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

Authors: Iftach Haitner Noam Mazor Ronen Shaltiel Jad Silbak DOI: 10.1007/978-3-030-36030-6_21 Search ePrint Search Google Consider a ppt two-party protocol $\varPi = (\mathsf {A} ,\mathsf {B} )$ in which the parties get no private inputs and obtain outputs $O^{\mathsf {A} },O^{\mathsf {B} }\in \left\{ 0,1\right\}$, and let $V^\mathsf {A}$ and $V^\mathsf {B}$ denote the parties’ individual views. Protocol $\varPi$ has $\alpha$-agreement if $\Pr [O^{\mathsf {A} }=O^{\mathsf {B} }] = \tfrac{1}{2}+\alpha$. The leakage of $\varPi$ is the amount of information a party obtains about the event $\left\{ O^{\mathsf {A} }=O^{\mathsf {B} }\right\}$; that is, the leakage$\epsilon$ is the maximum, over $\mathsf {P} \in \left\{ \mathsf {A} ,\mathsf {B} \right\}$, of the distance between $V^\mathsf {P} |_{O^{\mathsf {A} }= O^{\mathsf {B} }}$ and $V^\mathsf {P} |_{O^{\mathsf {A} }\ne O^{\mathsf {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 \ll \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 $\varOmega$ is the minimal $\epsilon \ge 0$ for which, for every $v \in \varOmega$, $\log \frac{\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 \varOmega (\epsilon ^2)$ can be transformed into an OT protocol (note that this allows $\epsilon \gg \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 [22] [FOCS ’18]. Specifically, we show that for any (noticeable) $\alpha \in \varOmega (\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 \varOmega (\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.
##### BibTeX
@article{tcc-2019-29985,
title={Channels of Small Log-Ratio Leakage and Characterization of Two-Party Differentially Private Computation},
booktitle={Theory of Cryptography},
series={Lecture Notes in Computer Science},
publisher={Springer},
volume={11891},
pages={531-560},
doi={10.1007/978-3-030-36030-6_21},
author={Iftach Haitner and Noam Mazor and Ronen Shaltiel and Jad Silbak},
year=2019
}