Paper 2000/030

Secure Multiparty Computation of Approximations

Joan Feigenbaum, Jessica Fong, 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 requires some additional overhead in computation and communication. Hence, if $$ is inefficient or just efficient enough to be practical, a secure computation of $$ may be impractically expensive. A secure computation of $$ may be efficient enough, but 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 in this paper. First, we give formal definitions of secure multiparty approximate computations. Second, we introduce some general techniques for constructing secure multiparty approximations. Finally, we present an efficient, sublinear-communication, secure approximate computation for the Hamming and $$ distances.

Note: See Cryptology ePrint Archive: Report 2001/024 for a major revision of this papers.