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 \pi 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|OA=OB and V^P|OA!=OB. 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 \alpha>>\apsilon 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>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) ???(?^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.
Consider a PPT two-party protocol ?=(A,B) in which the parties get no private inputs and obtain outputs O^A,O^B?{0,1}, and let V^A and V^B denote the parties’ individual views. Protocol ? has ?-agreement if Pr[O^A=O^B]=1/2+?. The leakage of ? is the amount of information a party obtains about the event {O^A=O^B}; that is, the leakage ? is the maximum, over P?{A,B}, of the distance between V^P|OA=OB and V^P|OA!=OB. 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 ?>>? 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 ? is the minimal ??0 for which, for every v??, log(Pr[X=v]/Pr[Y=v])? [??,?]. In the computational setting, we use computational indistinguishability from having log-ratio distance ?. We show that a protocol with (noticeable) accuracy ???(?^2) can be transformed into an OT protocol (note that this allows ?>>?). We complete the picture, in this respect, showing that a protocol with ??o(?^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) ???(?^2), a two-party protocol that computes the XOR function with ?-accuracy and ?-differential privacy can be transformed into an OT protocol. This improves upon Goyal et al. that only handle ???(?), 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 ??o(?^2), and extends to functions (over many bits) that “contain” an “embedded copy” of the XOR function.
