Two-party private estimation of dataset similarity

Abstract

A two-party approximation protocol is transformed into a private approximation protocol. A first input xε{0, 1, . . . , M}and a second input yε{0, 1, . . . , M}of a two party approximation protocol approximating a function of a form ƒ(x, y)=Σg (x, y) is received. Variable B is set as a public upper bound on ƒ(x, y). Variable l is set l=O*(1). The following is performed until or B<1, where t is an arbitrary number: (1) a private importance sampling protocol with the first input x, the second input y, and a third input 1, is executed independently for jε[l], where k is a security parameter, an output of the private importance sampling protocol is shares of Iε[n]∪{⊥}; (2) l coin tosses z, . . . , zare independently generated where z=1 iff I≠⊥; and (3) B is divided by 2 if or B<1 is not satisfied. When or B<1 a private (ε, δ)-approximation protocol Ψ for ƒ(x, y)=Σg(x, y) is outputted where ε is an arbitrary number, and δ=exp(−k).