## Cryptology ePrint Archive: Report 2001/024

**Secure Multiparty Computation of Approximations**

*Joan Feigenbaum and Yuval Ishai and Tal Malkin and Kobbi Nissim 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 it requires some
additional overhead in computation and communication. Hence, if
computation of $f$ is inefficient or just efficient enough to be
practical, then secure computation of $f$ may be impractically
expensive. Furthermore, 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. 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 $L^{2}$ distance
in a relaxed model. Finally, we give an efficient private
approximation of the permanent and other related \#P-hard problems.

**Category / Keywords: **cryptographic protocols / distributed cryptography, approximation algorithms, massive data sets, Hamming distance.

**Date: **received 15 Mar 2001

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

**Available format(s): **Postscript (PS) | Compressed Postscript (PS.GZ) | BibTeX Citation

**Version: **20010316:173320 (All versions of this report)

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

[ Cryptology ePrint archive ]