New imperfect random source with applications to coin-flipping

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

Abstract

We introduce a new imperfect random source that realistically generalizes the SV-source of Sántha and Vazirani [SV86] and the bit-fixing source of Lichtenstein, Linial and Saks [LLS89]. Our source is expected to generate a known sequence of (possibly dependent) random variables (for example, a stream of unbiased random bits). However, the realizations/observations of these variables could be imperfect in the following two ways: (1) inevitably, each of the observations could be slightly biased (due to noise, small measurements errors, imperfections of the source, etc.), which is characterized by the statistical noise parameter δ ε [0 1/2[, and (2) few 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 0. 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 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 (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 adaptive adversaries. While the optimal non-adaptive adversarial threshold for such protocols is known to be n=2 [BN00], the optimal adaptive threshold is conjectured by Ben-Or and Linial [BL90] to be only O(pn). 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 (pn) faulty players.

Original languageEnglish (US)
Title of host publicationAutomata, Languages and Programming - 28th International Colloquium, ICALP 2001, Proceedings
EditorsFernando Orejas, Paul G. Spirakis, Jan van Leeuwen
PublisherSpringer Verlag
Pages297-309
Number of pages13
ISBN (Print)3540422870, 9783540422877
DOIs
StatePublished - 2001
Event28th International Colloquium on Automata, Languages and Programming, ICALP 2001 - Crete, Greece
Duration: Jul 8 2001Jul 12 2001

Publication series

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

Other

Other28th International Colloquium on Automata, Languages and Programming, ICALP 2001
CountryGreece
CityCrete
Period7/8/017/12/01

ASJC Scopus subject areas

  • Theoretical Computer Science
  • Computer Science(all)

Fingerprint Dive into the research topics of 'New imperfect random source with applications to coin-flipping'. Together they form a unique fingerprint.

Cite this