## Distributed pseudo-random bit generators-- A new way
to speed-up shared coin tossing

** Authors: M. Bellare, J. Garay and T. Rabin
**
** Abstract: ** A shared coin is one which $n$ players ``simultaneously''
hold and can later reveal, but no sufficiently small coalition can influence or
a priori predict the outcome. Such coins are expensive to produce, yet many
distributed protocols (including broadcast and Byzantine agreement) need them
in bulk.

We introduce a new paradigm for obtaining shared coins. We suggest *
distributed, pseudo-random bit generators* (D-PRBGs). Analogous to a
pseudo-random bit generator, which is an efficient algorithm to expand a short
random seed into a long random looking sequence, a D-PRBG is a protocol which
``expands'' a ``distributed seed,'' consisting of shared coins, into a longer
``sequence'' of shared coins, at low amortized cost per coin produced. Our main
result is the construction of a D-PRBG in which this amortized cost
(computation and communication) is significantly lower than the cost of any
``from-scratch'' shared coin generation protocol.

Furthermore, for applications which are executed repeatedly, we
suggest *bootstrapping*: each run of the D-PRBG produces not
only the coins for the current execution but also the seed for the
next execution. Since the cost of the initial seed can now
effectively be neglected, we get very fast coin generation.

Underlying these constructions are some techniques of independent
interest. We consider batch Verifiable Secret Sharing (VSS), where we
need to do a large number of VSSs simultaneously. We provide a method
in which the amortized cost per VSS is significantly lower than
the cost of a VSS for any known VSS protocol.

** Ref:** * Proceedings of the 15th ACM Symposium on Principles of
Distributed Computing, * ACM, 1996. Paper available below.