CryptoDB
Secure Multiparty Computation of Approximations
| Authors: | |
|---|---|
| Download: | |
| 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 requires some additional overhead in computation and communication. Hence, if $f$ is inefficient or just efficient enough to be practical, a secure computation of $f$ may be impractically expensive. A secure computation of $\fhat$ may be efficient enough, but 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 in this paper. First, we give formal definitions of secure multiparty approximate computations. Second, we introduce some general techniques for constructing secure multiparty approximations. Finally, we present an efficient, sublinear-communication, secure approximate computation for the Hamming and $L^{1}$ distances. |
BibTeX
@misc{eprint-2000-11374,
title={Secure Multiparty Computation of Approximations},
booktitle={IACR Eprint archive},
keywords={foundations / secure multiparty computation, approximation algorithms},
url={http://eprint.iacr.org/2000/030},
note={ rwright@research.att.com 11397 received June 15, 2001, last revised 16 Mar 2001, withdrawn 16 Mar 2001},
author={Joan Feigenbaum and Jessica Fong and Martin Strauss and Rebecca N. Wright},
year=2000
}