## CryptoDB

### Ronen Shaltiel

#### Publications

Year
Venue
Title
2019
TCC
Channels of Small Log-Ratio Leakage and Characterization of Two-Party Differentially Private Computation
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  [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.
2015
CRYPTO
2009
TCC
2009
JOFC
2009
JOFC
2007
JOFC
2005
EUROCRYPT
2004
CRYPTO
2004
TCC
2004
TCC
2003
CHES

TCC 2007