Welcome to the resource topic for 1998/014
Title:
Randomness versus Fault-Tolerance
Authors: Ran Canetti, Eyal Kushilevitz, Rafail Ostrovsky, Adi Rosen
Abstract:We investigate the relations between two major requirements of multiparty
protocols: {\em fault tolerance} (or {\em resilience}) and {\em randomness}.
Fault-tolerance is measured in terms of the maximum number of colluding faulty
parties, t, that a protocol can withstand and still maintain the privacy of the inputs and the correctness of the outputs (of the honest parties). Randomness
is measured in terms of the total number of random bits needed by the parties
in order to execute the protocol.
Previously, the upper bound on the amount of randomness required by general
constructions for securely computing any non-trivial function f was polynomial
both in n, the total number of parties, and the circuit-size C(f). This was
the state of knowledge even for the special case t=1 (i.e., when there is at
most one faulty party). In this paper, we show that for any linear-size
circuit, and for any number t < n/3 of faulty parties, O(poly(t) * log n)
randomness is sufficient. More generally, we show that for any function f
with circuit-size C(f), we need only O(poly(t) * log n + poly(t) * C(f)/n)
randomness in order to withstand any coalition of size at most t.
Furthermore, in our protocol only t+1 parties flip coins and the rest of
the parties are deterministic. Our results generalize to the case of adaptive
adversaries as well.
ePrint: https://eprint.iacr.org/1998/014
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 .