Tal Malkin
Columbia University
Abstract: Approximation algorithms are often useful in obtaining efficient solutions to problems where no efficient exact computation is known, for example when the input data is extremely large, or when the problem is NP-hard. Secure multiparty computation allows mutually distrustful parties to compute a function of their inputs without revealing unnecessary information. Both secure multiparty computation and approximation algorithms are major research fields, and a rich body of work has emerged in the last decades in these two areas. However, some settings require the benefits offered by both concepts. For example, two companies may want to compute joint statistics on their data, which is typically huge, without revealing any additional information. Trying to combine techniques of secure multiparty computation with approximation algorithms is complex, and if done naively the resulting algorithm may be neither efficient, nor secure. Here, we initiate the study of secure multiparty computation of approximations, realizing most of the cost savings available by using an approximation algorithm, without losing the privacy of a secure computation.
We make three contributions: First, we introduce the concept and give formal definitions of secure multiparty approximate computation. Second, we present efficient private approximation protocols for distance functions, which are useful for computations on massive data sets. In particular, we give an efficient, sublinear-communication, private approximation for the Hamming distance, and an efficient, polylogarithmic-communication solution for the $L^{2}$ distance in a relaxed model. Finally, we give an efficient private approximation of the permanent and other related \#P-hard problems.
This talk is based on joint work with J. Feigenbaum, Y. Ishai, K. Nissim, M. Strauss, and R. Wright