IACR paper details
Title  Secure Multiparty Computation of Approximations 

Booktitle  IACR Eprint archive 

Pages  

Year  2001 

URL  http://eprint.iacr.org/2001/024 

Author  Joan Feigenbaum 

Author  Yuval Ishai 

Author  Tal Malkin 

Author  Kobbi Nissim 

Author  Martin Strauss 

Author  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, sublinearcommunication, private approximate computation
for the Hamming distance; we also give an efficient,
polylogarithmiccommunication solution for the $L^{2}$ distance
in a relaxed model. Finally, we give an efficient private
approximation of the permanent and other related \#Phard problems.


Search for the paper
@misc{eprint200111436,
title={Secure Multiparty Computation of Approximations},
booktitle={IACR Eprint archive},
keywords={cryptographic protocols / distributed cryptography, approximation algorithms, massive data sets, Hamming distance.},
url={http://eprint.iacr.org/2001/024},
note={ tal@research.att.com 11397 received 15 Mar 2001},
author={Joan Feigenbaum and Yuval Ishai and Tal Malkin and Kobbi Nissim and Martin Strauss and Rebecca N. Wright},
year=2001
}
Download a complete BibTeX file.