Two-party private estimation of dataset similarity

An information processing system for transforming a two-party approximation protocol into a private approximation protocol, the information processing comprising:

• a memory;
• a processor communicatively coupled to the memory;
• and
• a private approximation protocol generator communicatively coupled to the memory and the processor, the private approximation protocol generator being configured to perform a method comprising:
• receiving a first input x∈{0, 1, . . . , M}n and a second input y∈{0, 1, . . . , M}n of a two party approximation protocol (TPAP) for approximating a function of a form f(x, y)=Σj=1ng(xj, yj), where g is any non-negative efficiently computable function;
• setting B as a public upper bound on f(x, y) for any possible first input x and any possible second input y;
• setting l=O*(1);
• performing the following until
• ∑
• j
• =
• 1
• l
• 
• 
• z
• j
• ≧
• l
• t
• or B<1, where t is an arbitrary number:
• executing a private importance sampling protocol with the first input x, the second input y, and a third input 1k, independently for j∈[l], where k is a security parameter, and wherein an output of the private importance sampling protocol is shares of Ij∈[n]∪{⊥};
• independently generating l coin tosses z1, . . . , zl, where zj=1 iff Ij≠⊥;
• and
• dividing B by 2 if
• ∑
• j
• =
• 1
• l
• 
• 
• z
• j
• ≧
• l
• t
• or B<1 is not satisfied;
• determining that
• ∑
• j
• =
• 1
• l
• 
• 
• z
• j
• ≧
• l
• 8
• or B<1;
• and
• outputting a private (ε, δ)-approximation protocol Ψ for f(x, y)=Σj=1ng(xj, yj), where
• Ψ
• =
• 2
• 
• B
• l
• 
• ∑
• j
• =
• 1
• l
• 
• 
• z
• j
• ,
• ε is an arbitrary number, and δ=exp(−k).

A computer program product for transforming a two-party approximation protocol into a private approximation protocol, the computer program product comprising:

• a non-transitory storage medium readable by a processing circuit and storing instructions for execution by the processing circuit for performing a method comprising:
• receiving a first input x∈{0, 1, . . . , M}n and a second input y∈{0, 1, . . . , M}n of a two party approximation protocol (TPAP) for approximating a function of a form f(x, y)=Σj=1ng(xj, yj), where g is any non-negative efficiently computable function;
• setting B as a public upper bound on f(x, y) for any possible first input x and any possible second input y;
• setting l=O*(1);
• performing the following until
• ∑
• j
• =
• 1
• l
• 
• 
• z
• j
• ≧
• l
• t
• or B<1, where t is an arbitrary number:
• executing a private importance sampling protocol with the first input x, the second input y, and a third input 1k, independently for j∈[l], where k is a security parameter, and wherein an output of the private importance sampling protocol is shares of Ij∈[n]∪{⊥};
• independently generating l coin tosses z1, . . . , zl, where zj=1 iff Ij≠⊥;
• and
• dividing B by 2 if
• ∑
• j
• =
• 1
• l
• 
• 
• z
• j
• ≧
• l
• t
• or B<1 is not satisfied;
• determining that
• ∑
• j
• =
• 1
• l
• 
• 
• z
• j
• ≧
• l
• 8
• or B<1;
• and
• outputting a private (ε, δ)-approximation protocol Ψ for f(x, y)=Σj=1ng(xj, yj), where
• Ψ
• =
• 2
• 
• B
• l
• 
• ∑
• j
• =
• 1
• l
• 
• 
• z
• j
• ,
• ε is an arbitrary number, and δ=exp(−k).