Paper 2001/024

Secure Multiparty Computation of Approximations

Joan Feigenbaum, Yuval Ishai, Tal Malkin, Kobbi Nissim, Martin Strauss, and Rebecca N. Wright

Abstract

Approximation algorithms can sometimes be used to obtain efficient solutions where no efficient exact computation is known. In particular, approximations are often useful in a distributed setting where the inputs are held by different parties and are extremely large. Furthermore, for some applications, the parties want to cooperate to compute a function of their inputs without revealing more information than they have to. Suppose the function $$ is an approximation to the function $$. Secure multiparty computation of $$ allows the parties to compute $$ without revealing more than they have to, but it requires some additional overhead in computation and communication. Hence, if computation of $$ is inefficient or just efficient enough to be practical, then secure computation of $$ may be impractically expensive. Furthermore, a secure computation of $$ is not necessarily as private as a secure computation of $$, because the output of $$ may reveal more information than the output of $$. In this paper, we present definitions and protocols of secure multiparty approximate computation that show how to realize most of the cost savings available by using $$ instead of $$ without losing the privacy of a secure computation of $$. We make three contributions. First, we give formal definitions of secure multiparty approximate computations. Second, we present an efficient, sublinear-communication, private approximate computation for the Hamming distance; we also give an efficient, polylogarithmic-communication solution for the $$ distance in a relaxed model. Finally, we give an efficient private approximation of the permanent and other related \#P-hard problems.