**
Randomness vs. Fault-Tolerance
**

*
Ran Canetti, Eyal Kushilevitz, Rafail Ostrovsky and Adi Rosen
*

**
Abstract:
**

**
**
We investigate the relations between the * fault tolerance*
(or * resilience*)
and the * randomness* requirements of multiparty protocols.
Fault-tolerance is measured in terms of the maximum number of
colluding faulty players, t , that a protocol can withstand and still
maintain the privacy of the inputs and the correctness of the outputs (of
the honest players). Randomness is
measured in terms of the total number of random bits needed by the
players in order to execute the protocol.

Previously, the upper bound on the amount of randomness needed for securely
computing any non-trivial function ƒ was
polynomial both in n, the total number of parties,
and the circuit-size C(ƒ). This was
the state of knowledge even for the special case t=1 (i.e.,
when there is at most one malicious player).
In this paper, we show that
for any linear-size circuit, and for any value t < n/2,
O(poly(t). \log n) randomness is sufficient. More generally,
we show that
for any function ƒwith circuit-size C(ƒ), we
need only O(poly(ƒ).log n + poly(ƒ).C(ƒ)/n
randomness in order to withstand any coalition of size at most t.
Moreover, in our protocol only t+1 players flip coins and
the rest of the players are deterministic.
Our results generalize to the case of * adaptive* adversaries as well.

**comment:**
Appeared
In
Proceedings of Sixteenth Annual ACM Symposium on
Principles of Distributed Computing (PODC-97)

Fetch PostScript file of the paper Fetch PDF file of the paper

Back to Publications List |