Welcome to the resource topic for
**2001/024**

**Title:**

Secure Multiparty Computation of Approximations

**Authors:**
Joan Feigenbaum, Yuval Ishai, Tal Malkin, Kobbi Nissim, Martin Strauss, 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.

**ePrint:**
https://eprint.iacr.org/2001/024

See all topics related to this paper.

Feel free to post resources that are related to this paper below.

**Example resources include:**
implementations, explanation materials, talks, slides, links to previous discussions on other websites.

For more information, see the rules for Resource Topics .