TWO-PARTY PRIVATE ESTIMATION OF DATASET SIMILARITY

A two-party approximation protocol is transformed into a private approximation protocol. A first input xε{0, 1, . . . , M}n and a second input yε{0, 1, . . . , M}n of a two party approximation protocol approximating a function of a form ƒ(x, y)=Σj=1ng(xj, yj) 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 untilor 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 1k, is executed independently for jε[l], where k is a security parameter, an output of the private importance sampling protocol is shares of Ijε[n]∪{⊥}; (2) l coin tosses z1, . . . , zl are independently generated where zj=1 iff Ij≠⊥; and (3) B is divided by 2 ifor B<1 is not satisfied. Whenor B<1 a private (ε, δ)-approximation Ψ protocol for ƒ(x, y)=Σj=1ng(xj, yj) is outputted whereε is an arbitrary number, and δ=exp(−k).