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 .