How to Turn Loaded Dice into Fair Coins

We present a new, optimally efficient technique for extracting unbiased bits from certain physical sources of randomness. Sequences of random numbers are of ubiquitous importance in cryptography and vital to many other computing applications. While pseudo-random generators are useful for producing such sequences, a physical source of randomness is still needed to seed a pseudo-random generator. Many physical sources of randomness, like radioactive or quantum mechanical sources, or the hard disk source recently introduced by Jakobsson et al., possess the useful property of stationarity. In other words, they produce independent outputs on fixed probability distributions over the real numbers. The output of such source may be viewed as the results of rolling a biased or loaded die. While a loaded die may be a good source of entropy, many applications require input in the form of unbiased random bits, rather than the biased real numbers provided by such dice with unknown bias to generate unbiased random bits. We prove our algorithm to be optimally efficient in terms of its output entropy, and present techniques enabling a computationally practical implementation. Our algorithm is therefore well suited to taking any stationary physical sources and extracting useful randomness in the form of bistrings.