Private Multiparty Sampling and Approximation of Vector Combinations

Full textClick to download.
CitationProceedings of the 34th International Colloquium on Automata, Languages and Programming (ICALP), 2007.
Authors Yuval Ishai
Tal Malkin
Martin J. Strauss
Rebecca N. Wright


We consider the problem of private efficient data mining of vertically-partitioned databases. Each of several parties holds a column of a data matrix (a vector) and the parties want to investigate the com- ponentwise combination of their vectors. The parties want to minimize communication and local computation while guaranteeing privacy in the sense that no party learns more than necessary. Sublinear-communication private protocols have been primarily been studied only in the two-party case. We give efficient multiparty protocols for sampling a row of the data matrix and for computing arbitrary functions of a row, where the row index is additively shared among two or more parties. We also give protocols for approximating the componentwise sum, minimum, or max- imum of the columns in which the communication and the number of public-key operations are at most polynomial in the size of the small approximation and polylogarithmic in the number of rows.

Back to publications
Back to previous page