# A Note on Randomness Extraction

Peter Occil

Randomness extraction (also known as unbiasing, debiasing, deskewing, whitening, or entropy extraction) is a set of techniques for generating unbiased random bits from biased sources. This note covers some useful extraction techniques.

## In Information Security

In information security, randomness extraction serves to generate a seed, password, encryption key, or other secret value from hard-to-predict nondeterministic sources.

Randomness extraction for information security is discussed in NIST SP 800-90B sec. 3.1.5.1, and RFC 4086 sec. 4.2 and 5.2. Possible choices of such extractors include keyed cryptographic hash functions (see, for example, (Cliff et al., 2009)[^1]; (Coretti et al., 2019)[^2]) and two-universal hash functions with a fixed but randomly chosen seed (Frauchiger et al., 2013)[^3]. In information security applications:

• Unkeyed hash functions and other unkeyed extraction functions should not be used by themselves in randomness extraction.
• Lossless compression should not be used as a randomness extractor.
• Where possible, there should be two or more independent nondeterministic sources from which to apply randomness extraction (McInnes and Pinkas 1990)[^4].

Some papers also refer to two-source extractors and resilient functions (especially the works by E. Chattopadhyay and D. Zuckerman), but there are few if any real implementations of these extraction techniques.

Example: The Cliff reference reviewed the use of HMAC (hash-based message authentication code) algorithms, and implies that one way to generate a seed is as follows:

1. Gather data with at least 512 bits of entropy.
2. Run HMAC-SHA-512 with that data to generate a 512-bit HMAC.
3. Take the first 170 (or fewer) bits as the seed (512 divided by 3, rounded down).

## Outside of Information Security

Outside of information security, randomness extraction serves the purpose of recycling randomly generated numbers or, more generally, to transform those numbers from one form to another while preserving their randomness. This can be done, for example, to reduce calls to a pseudorandom number generator (PRNG) or to generate a new seed for such a PRNG.

Perhaps the most familiar example of randomness extraction is the one by von Neumann (1951)[^5], which works if "independence of successive [coin] tosses is assumed"[^6]:

1. Flip a coin twice (whose probability of heads is unknown).
2. If the coin lands heads then tails, return heads. If it lands tails then heads, return tails. If neither is the case, go to step 1.

An algorithm found in (Morina et al. 2022)[^6] (called Algorithm M in this note) extends this to loaded dice. According to personal communication with K. Łatuszyński, the key "is to find two non overlapping events of the same probability" via "symmetric events {X_1 < X_2} and {X_2 < X_1} that have the same probability".

1. Throw a (loaded) die, call the result X. Throw the die again, call the result Y.
2. If X is less than Y, return 0. If X is greater than Y, return 1. If neither is the case, go to step 1.

Algorithm M in fact works in a surprisingly broad range of cases; for more, see the appendix.

Pae (2005)[^7] and (Pae and Loui 2006)[^8] characterize extracting functions. Informally, an extracting function is a function that maps a fixed number of digits to a variable number of bits such that, whenever the input has a given number of ones, twos, etc., every output bit-string of a given length occurs with the same probability as every other output bit-string of that length, regardless of the input's probability of zero or one.[^9] Among others, von Neumann's extractor and the one by Peres (1992)[^10] are extracting functions. The Peres extractor takes a list of bits (zeros and ones generated from a "coin" with a given probability of heads) as input and is described as follows:

1. Create two empty lists named U and V. Then, while two or more bits remain in the input:
1. If the next two bits are 0/0, append 0 to U and 0 to V.
2. Otherwise, if those bits are 0/1, append 1 to U, then write a 0.
3. Otherwise, if those bits are 1/0, append 1 to U, then write a 1.
4. Otherwise, if those bits are 1/1, append 0 to U and 1 to V.
2. If U is not empty, do a separate (recursive) run of this algorithm, reading from the bits placed in U.
3. If V is not empty, do a separate (recursive) run of this algorithm, reading from the bits placed in V.

A streaming algorithm, which builds something like an "extractor tree", is another example of a randomness extractor (Zhou and Bruck 2012)[^11].

I maintain source code of this extractor and the Peres extractor, which also includes additional notes on randomness extraction.

Pae's "entropy-preserving" binarization (Pae 2018)[^12], given below, is meant to be used in other extractor algorithms such as the ones mentioned above. It assumes the number of possible values, n, is known. However, it is obviously not efficient if n is a large number.

1. Let f be a number in the interval [0, n) that was previously randomly generated. If f is greater than 0, write a 1 (and go to step 2).
2. If f is less than n − 1, write a 0 x times, where x is (n − 1) − f.