Distributed pseudo-random bit generators---a new way to speed-up shared coin tossing
Mihir Bellare, Juan A. Garay, Tal Rabin · 1996
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, pseudorandom 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 DPRBG 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 sugg...