Fast Private Norm Estimation and Heavy Hitters
We consider the problems of computing the Euclidean norm of the difference of two vectors and, as an application, computing the large components (Heavy Hitters) in the difference. We provide protocols that are approximate but private in the semi-honest mo
- PDF / 612,522 Bytes
- 18 Pages / 430 x 660 pts Page_size
- 33 Downloads / 183 Views
2
Department of Computer Science, Rutgers University, Piscataway, NJ 08854 USA [email protected] Department of Computer Science, Rutgers University, Piscataway, NJ 08854 USA [email protected] 3 Departments of Math and EECS, University of Michigan, Ann Arbor, MI 48109 USA [email protected] 4 Department of EECS, University of Michigan, Ann Arbor, MI 48109 USA [email protected]
Abstract. We consider the problems of computing the Euclidean norm of the difference of two vectors and, as an application, computing the large components (Heavy Hitters) in the difference. We provide protocols that are approximate but private in the semi-honest model and efficient in terms of time and communication in the vector length N . We provide the following, which can serve as building blocks to other protocols: – Euclidean norm problem: we give a protocol with quasi-linear local computation and polylogarithmic communication in N leaking only the true value of the norm. For processing massive datasets, the intended application, where N is typically huge, our improvement over a recent result with quadratic runtime is significant. – Heavy Hitters problem: suppose, for a prescribed B, we want the B largest components in the difference vector. We give a protocol with quasi-linear local computation and polylogarithmic communication leaking only the set of true B largest components and the Euclidean norm of the difference vector. We justify the leakage as (1) desirable, since it gives a measure of goodness of approximation; or (2) inevitable, since we show that there are contexts where linear communication is required for approximating the Heavy Hitters.
1
Introduction
Secure Multiparty Computation (SMC) has been studied for decades since [6,22]. Any protocol for computing a function can be converted, gate-by-gate, to a private protocol, in which no party learns anything from the protocol messages
Supported in part by NSF grant CCF-0728937 Supported in part by NSF grant DMS-0354600. Supported in part by NSF grant DMS-0354600.
R. Canetti (Ed.): TCC 2008, LNCS 4948, pp. 176–193, 2008. c International Association for Cryptologic Research 2008
Fast Private Norm Estimation and Heavy Hitters
177
other than what can be inferred from the function’s input/output relation. The computational overhead is at most polynomial in the size of the inputs. In recent years, however, input sizes in many problems have grown to the point where “polynomial computational overhead” is too coarse a measure; both computation and communication should be minimized. For example, absent privacy concerns, applications may require that a protocol use at most polylogarithmic communication—this occurs in processing distributed internet traffic at line speeds or in performing data mining algorithms in very large datasets. General-purpose SMC may blow up communication exponentially, so additional techniques are needed. In one theoretical approach, individual protocols are designed for functions of interest such as database lookup [9,18,7] and building
Data Loading...
