New Imperfect Random Source with Applications to Coin-Flipping.
Yevgeniy Dodis, IBM Watson Research Laboratory and NYU
November 21, 4:30 PM, Rutgers Univ. Hill CORE building, Room 431
Abstract.
We introduce a new model of imperfect random source that realistically
generalizes the SV-source of Santha and Vazirani and the
bit-fixing source of Lichtenstein, Linial and Saks. Our
source generates a sequence of correlated random variables, presumably
generated by some physical source(s) of randomness. However, the
realizations/observations of these variables could be imperfect in the
following two ways: (1) inevitably, each observation
could be slightly imperfect (due to noise, small measurements
errors, imperfections of the source, etc.), which is characterized by
the ``statistical noise'' parameter delta in [0,1/2], and (2)
a small number of the observations could be completely incorrect (due
to very poor measurement, improper setup, unlikely but certain
internal correlations, etc.), which is characterized by the ``number
of errors'' parameter b. While the SV-source considered only
scenario (1), and the bit-fixing source --- only scenario (2), we
believe that our combined source is more realistic in modeling the
problem of extracting quasi-random bits from physical sources.
Unfortunately, we show that dealing with the {\em combination} of
scenarios (1) and (2) is dramatically more difficult (at least from
the point of randomness extraction) than dealing with each scenario
individually. For example, if b delta is Omega(1) the adversary
controlling our source can force the outcome of any bit extraction
procedure to a constant with probability 1-o(1), irrespective of the
random variables, their correlation and the number of observations.
We also apply our source to the question of producing n-player
collective coin-flipping protocols secure against {\em adaptive}
adversaries. While the optimal non-adaptive adversarial threshold for
such protocols is known to be n/2, the optimal adaptive
threshold is {\em conjectured} by Ben-Or and Linial to be
only O(sqrt{n}). We give some evidence towards this conjecture by
showing that there exists no black-box transformation from a
non-adaptively secure coin-flipping protocol (with arbitrary
conceivable parameters) resulting in an adaptively secure
protocol tolerating omega(sqrt{n}) faulty players.