**Secure Multiparty Computation of Approximations**

*Joan Feigenbaum and Jessica Fong and 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 $\fhat$ is an approximation to the function $f$. Secure multiparty computation of $f$ allows the parties to compute $f$ without revealing more than they have to, but requires some additional overhead in computation and communication. Hence, if $f$ is inefficient or just efficient enough to be practical, a secure computation of $f$ may be impractically expensive. A secure computation of $\fhat$ may be efficient enough, but a secure computation of $\fhat$ is not necessarily as private as a secure computation of $f$, because the output of $\fhat$ may reveal more information than the output of $f$. 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 $\fhat$ instead of $f$ without losing the privacy of a secure computation of $f$.

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 $L^{1}$ distances.

**Category / Keywords: **foundations / secure multiparty computation, approximation algorithms

**Date: **received June 15, 2001, last revised 16 Mar 2001, withdrawn 16 Mar 2001

**Contact author: **rwright at research att com

**Available format(s): **(-- withdrawn --)

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

**Version: **20051128:071245 (All versions of this report)

**Short URL: **ia.cr/2000/030

**Discussion forum: **Show discussion | Start new discussion

[ Cryptology ePrint archive ]