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 {\em complete} has been extensively studied in the literature. However, for \emph{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