Near-optimal private approximation protocols via a black box transformation

Abstract

We show the following transformation: any two-party protocol for outputting a (1+ε)-approximation to f(x,y) = ∑j=1n g(x j, yj) with probability at least 2/3, for any non-negative efficienty computable function g, can be transformed into a two-party private approximation protocol with only a polylogarithmic factor loss in communication, computation, and round complexity. In general it is insufficient to use secure function evaluation or fully homomorphic encryption on a standard, non-private protocol for approximating f. This is because the approximation may reveal information about x and y that does not follow from f(x,y). Applying our transformation and variations of it, we obtain near-optimal private approximation protocols for a wide range of problems in the data stream literature for which previously nothing was known. We give near-optimal private approximation protocols for the ℓp-distance for every p ≥ 0, for the heavy hitters and importance sampling problems with respect to any ℓp-norm, for the max-dominance and other dominant ℓp-norms, for the distinct summation problem, for entropy, for cascaded frequency moments, for subspace approximation and block sampling, and for measuring independence of datasets. Using a result for data streams, we obtain private approximation protocols with polylogarithmic communication for every non-decreasing and symmetric function g(xj,yj) = h(xj-yj) with at most quadratic growth. If the original (non-private) protocol is a simultaneous protocol, e.g., a sketching algorithm, then our only cryptographic assumption is efficient symmetric computationally-private information retrieval; otherwise it is fully homomorphic encryption. For all but one of these problems, the original protocol is a sketching algorithm. Our protocols generalize straightforwardly to more than two parties. © 2011 ACM.