Patent ID: 8630409

Claim:
An information processing system for automatically 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 ƒ(x, y)=Σ j=1 n g(x j , y j ), where g is any non-negative efficiently computable function; setting B as a public upper bound on ƒ(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 1 k , independently for jε[l], where k is a security parameter, and an output of the private importance sampling protocol is shares of I j ε[n]∪{⊥}, wherein n is an integer and ⊥ represents a predefined symbol agreed upon by a first party and a second party, and wherein the private importance sampling protocol is a privately obtained secret share of a sample index i in {1, 2, . . . , n} for the first party and the second party; independently generating l coin tosses z 1 , . . . , z l , where z j =1 iff I j ≠⊥; 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=1 n g(x j , y i ), where Ψ = 2 ⁢ B l ⁢ ∑ j = 1 l ⁢ ⁢ z j , ε is an arbitrary number, and δ=exp(−k).