International Association for Cryptologic Research

International Association
for Cryptologic Research

CryptoDB

Paper: Secure Multiparty Computation of Approximations

Authors:
Joan Feigenbaum
Yuval Ishai
Tal Malkin
Kobbi Nissim
Martin Strauss
Rebecca N. Wright
Download:
URL: http://eprint.iacr.org/2001/024
Search ePrint
Search Google
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.
BibTeX
@misc{eprint-2001-11436,
  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
}