Rafail Ostrovsky - Publications
On Complete Primitives for Fairness
Dov Gordon, Yuval Ishai, Tal Moran, Rafail Ostrovsky, Amit Sahai
Abstract:
For secure two-party and multi-party computation with abort,
classification of which primitives are has been
extensively studied in the literature. However, for fair secure
computation, where (roughly speaking) either all parties learn the
output or none do, the question of complete primitives has remained
largely unstudied. In this work, we initiate a rigorous study of completeness for
primitives that allow fair computation. We show the following
results:
-
No "short" primitive is complete for fairness.
In surprising contrast to other notions of security for secure
two-party computation, we show that for fair secure
computation, no primitive of size O(\log k) is complete, where k
is a security parameter. This is the case even if we can enforce
parallelism in calls to the primitives (i.e., the adversary does not
get output from any primitive in a parallel call until it sends input
to all of them). This negative result holds regardless of any
computational assumptions.
- A fairness hierarchy. We clarify the fairness
landscape further by exhibiting the existence of a "fairness
hierarchy". We show that for every "short" \ell = O(\log k), no
protocol making (serial) access to any \ell-bit primitive can be
used to construct even a (\ell+1)-bit simultaneous broadcast.
- Positive results. To complement the negative results,
we exhibit a k-bit primitive that \emph{is} complete for two-party
fair secure computation.
We show how to generalize this result to the
multi-party setting.
- Fairness combiners. We also introduce the question of
constructing a protocol for fair secure computation from primitives
that may be faulty. We show that this is possible when a majority of the instances are
honest. On the flip side, we show that this result is tight: no
functionality is complete for fairness if half (or more) of the
instances can be malicious.
comment:
Preliminary version in TCC 2010.
Fetch PostScript file of the
paper
Fetch PDF file of the
paper