Summary: 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\{0,1\}\), and let \(V^\mathsf{A}\) and \(V^\mathsf{B}\) denote the parties’ individual views. Protocol \(\varPi\) has \(\alpha\)-agreement if \(\mathrm{Pr}[O^{\mathsf{A}}=O^{\mathsf{B}}]=\frac{1}{2}+\alpha\). The leakage of \(\varPi\) is the amount of information a party obtains about the event \(\{O^{\mathsf{A}}=O^{\mathsf{B}}\}\); that is, the leakage \(\epsilon\) is the maximum, over \(\mathsf{P}\in\{\mathsf{A},\mathsf{B}\}\), 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, J. Wullschleger [Lect. Notes Comput. Sci. 5444, 332–349 (2009; Zbl 1213.94141)] 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 V. Goyal et al. [LIPIcs – Leibniz Int. Proc. Inform. 55, Article 29, 15 p. (2016; Zbl 1425.94062)] and I. Haitner et al. [SIAM J. Comput. 49, No. 6, 1041–1082 (2020; Zbl 1498.94064)]. 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. [loc. cit.] that only handle \(\alpha\in\varOmega(\epsilon)\), and upon Haitner et al. [loc. cit.] 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.
For the entire collection see [Zbl 1428.94013].