Random Selection with an Adversarial Majority
Speaker: Ronen Gradwohl , Weizmann Institute
Date: April 5 2006
Time: 4:00PM to 5:30PM
Location: 32-G575, Stata Center
Host: Guy Rothblum, CSAIL, MIT
Contact: Be Blackburn, 3-6098, imbe@mit.edu
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.
Joint work with Salil Vadhan and David Zuckerman.
See other events that are part of Cryptography and Information Security Seminar Seminars 2005/2006
See other events happening in April 2006
