eprint.iacr.org will be offline for approximately an hour for routine maintenance again at 10pm UTC on Wednesday, April 17.

Paper 2001/024

Secure Multiparty Computation of Approximations

Joan Feigenbaum, Yuval Ishai, Tal Malkin, Kobbi Nissim, 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.

Metadata
Available format(s)
PS
Category
Cryptographic protocols
Publication info
Published elsewhere. Unknown where it was published
Keywords
distributed cryptographyapproximation algorithmsmassive data setsHamming distance.
Contact author(s)
tal @ research att com
History
2001-03-16: received
Short URL
https://ia.cr/2001/024
License
Creative Commons Attribution
CC BY

BibTeX

@misc{cryptoeprint:2001/024,
      author = {Joan Feigenbaum and Yuval Ishai and Tal Malkin and Kobbi Nissim and Martin Strauss and Rebecca N.  Wright},
      title = {Secure Multiparty Computation of Approximations},
      howpublished = {Cryptology ePrint Archive, Paper 2001/024},
      year = {2001},
      note = {\url{https://eprint.iacr.org/2001/024}},
      url = {https://eprint.iacr.org/2001/024}
}
Note: In order to protect the privacy of readers, eprint.iacr.org does not use cookies or embedded third party content.