@conference {643282,
	title = {Random selection with an adversarial majority},
	booktitle = {Advances in Cryptology{\textemdash}CRYPTO {\textquoteleft}06, C. Dwork, ed.},
	volume = {4117},
	year = {2006},
	pages = {409{\textendash}426},
	publisher = {Springer Verlag, Lecture Notes in Computer Science },
	organization = {Springer Verlag, Lecture Notes in Computer Science },
	abstract = {
	Version History:\&nbsp;Full version published in ECCC TR 06-026, February 2006. Updated full version\&nbsp;published June 2006.



	We consider the problem of random selection, where\&nbsp;\(p\)\&nbsp;players follow a protocol to jointly select a random element of a universe of size\&nbsp;\(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\&nbsp;\(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.

},
	url = {https://link.springer.com/chapter/10.1007/11818175_25},
	author = {Ronen Gradwohl and Salil Vadhan and David Zuckerman}
}
