# Random Selection with

an Adversarial Majority

Ronen Gradwohl, Salil Vadhan, David Zuckerman

### Abstract

We consider the problem of random selection, where p players follow a protocol
to jointly select a random element of a universe of size n. However, some of
the players may be adversarial and collude to force the output to lie in a
small subset of the universe. We describe essentially the first protocols that
solve this problem in the presence of a dishonest majority in the
full-information model (where the adversary is computationally unbounded and
all communication is via broadcast). Our protocols are nearly optimal in
several parameters, including the round complexity (as a function of n), the
randomness complexity, the communication complexity, and the tradeoffs between
the fraction of honest players, the probability that the output lies in a small
subset of the universe, and the density of this subset.

### Versions

*Electronic Colloquium on
Computational Complexity,* Technical Report TR06-026, February 2006. [official
ECCC page]
- In C. Dwork, editor,
*Advances in
Cryptology---CRYPTO `06*, number 4117 in *Lecture Notes in
Computer Science*, pages 409-426, Springer-Verlag, 20-24 August 2006.[ps][pdf][Springer page][talk (given by J. Katz)]
- Revised full version, June
2006.[ps][pdf]

[ back to
Salil Vadhan's research]