| 摘要 |
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)=&Sgr;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 until ∑ j = 1 l  z j ≥ l t 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 lk, 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, . . . , z,l are independently generated where zj=1 iff Ij≠⊥; and (3) B is divided by 2 if ∑ j = 1 l  z j ≥ l t or B<1 is not satisfied. When ∑ j = 1 l  z j ≥ l 8 or B<1 a private (&egr;,δ) -approximation protocol Ψ for ƒ(x, y)=&Sgr;j=1ng(xj, yj) is outputted where Ψ = 2   B l  ∑ j = 1 l  z j , &egr; is an arbitrary number, and δ=exp(−k).
|
