Channels of Small Log-Ratio Leakage and Characterization of Two-Party Differentially Private Computation
share
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].
READ FULL TEXT