ETH Zürich » Computer Science » Theory » Cryptography

Publications: Abstract

Extracting Randomness from Generalized Symbol-Fixing and Markov Sources

Robert Koenig and Ueli Maurer

We introduce a new class of realistic sources of randomness and give concrete procedures for deterministic} extraction of almost uniform random bits from these sources. Moreover, we show how randomness can be extracted from general Markov sources. This extends the types of sources for which explicit deterministic randomness extractors are known.