Logo Logo

Random Selection with an Adversarial Majority, Proceedings of the 2006 Annual International Cryptology Conference

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 non-simultaneous 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.

Type

Article

Author(s)

Ronen Gradwohl, Salil P. Vadhan, David Zuckerman

Date Published

2006

Citations

Gradwohl, Ronen, Salil P. Vadhan, and David Zuckerman. 2006. Random Selection with an Adversarial Majority. Proceedings of the 2006 Annual International Cryptology Conference. 26: 409-426.

KELLOGG INSIGHT

Explore leading research and ideas

Find articles, podcast episodes, and videos that spark ideas in lifelong learners, and inspire those looking to advance in their careers.
learn more

COURSE CATALOG

Review Courses & Schedules

Access information about specific courses and their schedules by viewing the interactive course scheduler tool.
LEARN MORE

DEGREE PROGRAMS

Discover the path to your goals

Whether you choose our Full-Time, Part-Time or Executive MBA program, you’ll enjoy the same unparalleled education, exceptional faculty and distinctive culture.
learn more