TY - GEN
T1 - Random selection with an adversarial majority
AU - Gradwohl, Ronen
AU - Vadhan, Salil
AU - Zuckerman, David
PY - 2006
Y1 - 2006
N2 - 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.
AB - 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.
UR - http://www.scopus.com/inward/record.url?scp=33749553752&partnerID=8YFLogxK
UR - http://www.scopus.com/inward/citedby.url?scp=33749553752&partnerID=8YFLogxK
U2 - 10.1007/11818175_25
DO - 10.1007/11818175_25
M3 - Conference contribution
AN - SCOPUS:33749553752
SN - 3540374329
SN - 9783540374329
T3 - Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
SP - 409
EP - 426
BT - Advances in Cryptology - CRYPTO 2006 - 26th Annual International Cryptology Conference, Proceedings
PB - Springer Verlag
T2 - 26th Annual International Cryptology Conference, CRYPTO 2006
Y2 - 20 August 2006 through 24 August 2006
ER -