Random selection with an adversarial majority

Ronen Gradwohl*, Salil Vadhan, David Zuckerman

*Corresponding author for this work

Research output: Chapter in Book/Report/Conference proceedingConference contribution

11 Scopus citations

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.

Original languageEnglish (US)
Title of host publicationAdvances in Cryptology - CRYPTO 2006 - 26th Annual International Cryptology Conference, Proceedings
PublisherSpringer Verlag
Pages409-426
Number of pages18
ISBN (Print)3540374329, 9783540374329
DOIs
StatePublished - 2006
Event26th Annual International Cryptology Conference, CRYPTO 2006 - Seattle, WA, United States
Duration: Aug 20 2006Aug 24 2006

Publication series

NameLecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
Volume4117 LNCS
ISSN (Print)0302-9743
ISSN (Electronic)1611-3349

Other

Other26th Annual International Cryptology Conference, CRYPTO 2006
CountryUnited States
CitySeattle, WA
Period8/20/068/24/06

ASJC Scopus subject areas

  • Theoretical Computer Science
  • Computer Science(all)

Fingerprint Dive into the research topics of 'Random selection with an adversarial majority'. Together they form a unique fingerprint.

Cite this