Abstract:

Random Selection -- one of the most basic protocol problems in cryptography
and distributed computing -- asks for mutually distrusting parties to
jointly generate a random string. Feige (FOCS 99) and Russell and Zuckerman
(FOCS 98) construct elegant random selection protocols that run in log* n
rounds, in the full-information model. These protocols, however, assume a
*built-in reliable broadcast channel*. We construct random selection
protocols that run in O(logn) rounds in the plain model, namely, *without*
reliable broadcast channels.

One of the consequences of this result is an O(log n)-round randomized
Byzantine Agreement protocol in synchronous networks, improving on the
previous best result of O(n/log n) rounds (Chor and Coan '85).

Based on joint work with Michael Ben-Or, Shafi Goldwasser and Elan Pavlov
(STOC 06, FOCS 06).