Full text  Click to download. 
Citation  Proceedings 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 verticallypartitioned 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. Sublinearcommunication private protocols have been primarily been studied only in the twoparty 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 publickey operations are at most polynomial in the size of the small approximation and polylogarithmic in the number of rows.