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.
展开▼
