Randomness extractor

Template:Cleanup

A randomness extractor, often simply called "an extractor," is a function which, when applied to a high-entropy source (such as radioactive decay, or thermal noise), generates a random output that is shorter, yet uniformly distributed. In other words, outputting a completely random sample from a semi-random input.[1]

The goal of this process is to generate a truly random output stream, which could then be considered as being a true random number generator (TRNG).

A randomness extractor is an algorithm that converts a weakly random source and a truly random seed into a uniform distribution of random numbers. The weakly random source is usually longer than the output, and the truly random seed is short compared to the two. The only restriction for successful application of the extractor is that the high-entropy source is nondeterministic, in other words, there is no way in which the source can be fully controlled, calculated or predicted. An extractor is a certain kind of pseudorandom generator construction.

The goal in using extractors is to obtain a truly random sequence with a uniform distribution. When constructing an extractor, the aim is to get as long an output as possible when using as short as possible inputs; specifically the truly random seed's length is useful to minimize.

No single randomness extractor currently exists that has been proven to work when applied to any type of high-entropy source.

Formal definition of extractors

When defining an extractor, we need a measurement of how well it extracts. In other words, we need to define the level of randomness it produces. For this is used min-entropy, which is a measurement of the amount of randomness in the worst case. The definition uses the worst case randomness of min-entropy and not the average case randomness described by Shannon-entropy.

Definition (Extractor): A (k, ε)-extractor is a function

$\text{Ext}: \{0,1\}^n \times \{0,1\}^d \rightarrow \{0,1\}^m \,$

such that for every distribution X on {0, 1}ⁿ with $H_{\infty}(X) \geq k$ the distribution $Ext(X,U_{d})$ is ε-close to the uniform distribution on {0, 1}m.

Futuremore, if $U_{d} \circ Ext(X, U_{d})$ is ε-close to the uniform distribution on {0, 1}^m+d, we call it as a strong (k, ε)-extractor.

Now, the length of the weakly random input is required to be longer than the length of the output. The aim is to have a short as possible seed (low d), and an output that is as long as possible (high m), while keeping the min-entropy over a certain limit. In short we will have: n > m and we aim for d<< m.

Explicit extractors

By standard probabilistic method it can be shown that there exists a (k, ε)-extractor, i.e. that the construction is possible. It is however rarely enough to show the existence of an extractor. An explicit construction is needed:

Definition (Explicit Extractor): For functions k(n), ε(n), d(n), m(n) a family Ext = Ext_n of functions

$\text{Ext}_n : \{0,1\}^n \times \{0,1\}^{d(n)} \rightarrow \{0,1\}^{m(n)}$

is an explicit (k, ε)-extractor if Ext(x, y) can be computed in polynomial time (in its input length) and for every n, Ext_n is a (k(n), ε(n))-extractor.

In words, this definition states that an extractor can be generated in polynomial time. It is worth to note that using the extractor is not a polynomial time operation, but rather a linear time operation on the input, plus any time needed to modify the input before using the extractor itself.

By the probabilistic method it can be shown that there exists a (k, ε)-extractor with seed length

$d = \log{(n-k)}+2\log \left(\frac{1}{\varepsilon}\right) +O(1)$

and output length

$m = k +d-2\log \left(\frac{1}{\varepsilon}\right) - O(1)$.

Dispersers

Another variant of the randomness extractor is the disperser.

Strong extractors

The two inputs taken by an extractor must be independent sources of randomness (the actual random source and a shorter seed). For an extractor to be a strong extractor it is required that concatenating the seed with the extractor's output yields a distribution that is close to uniform.

Definition (Strong Extractor): A $(k, \epsilon)$-strong extractor is a function

$\text{Ext}: \{0,1\}^n \times \{0,1\}^d \rightarrow \{0,1\}^m \,$

such that for every distribution $X$ on $\{0,1\}^n$ with $H_{\infty}(X) \geq k$ the distribution $U_{d} \circ Ext(X, U_{d})$ (The two copies of $U_{d}$ denote the same random variable) is $\epsilon$-close to the uniform distribution on $\{0,1\}^{m+d}$.

Randomness extractors in cryptography

This section is mainly based on . Jesse Kamp and David Zuckerman examine deterministic extractors (extractors without an input seed), which is why the following section concerns extractors with only one input.

One of the most important aspects of cryptography is random key generation. It is often needed to derive secret and random keys using sources that are semi-secret. Using extractors, having a single short secret random key is sufficient to generate longer pseudo-random keys, which can be used for public key encryption. In other words, randomness extraction can be useful in the key derivation phase.

When using a strong extractor the output will appear be uniform, even to someone who sees the pseudo-random source (or the seed, but not both). In other words, the randomness, and thus the secrecy, of the output is intact even if the input source is compromised. The high level of randomness in the output along with the fact that every part of the output depends on the entire input, ensures that knowing part of the input will not reveal any part of the output. This is referred to as Exposure-Resilient cryptography wherein the desired extractor is used in a so called Exposure-Resilient Function (ERF).

The point of using Exposure-Resilient Functions is the practical application of these. When initializing a specific encryption application the parties often doesn't have any common and private knowledge. The initial exchange of data is difficult to keep completely secret, which is why Exposure-Resilient Functions are useful.

Definition (k-ERF): An adaptive k-ERF is a function $f$ where, for a random input $r$ , when a computationally unbounded adversary $A$ can adaptively read all of $r$ except for $k$ bits, $|Pr[A^{r}(f(r)) = 1] - Pr[A^{r}(R) = 1]| \leq \epsilon(n)$ for some negligible function $\epsilon(n)$.

The goal is to construct adaptive ERF's when trying to extract output that is indistinguishable to uniform. Often a stronger condition is needed; that is that every output occurs with almost uniform probability. To solve this is used Almost-Perfect Resilient Functions (APRF):

Definition (k-APRF): A $k = k(n)$ APRF is a function $f$ where, for any setting of $n-k$ bits of the input $r$ to any fixed values, the probability vector $p$ of the output $f(r)$ over the random choices for the $k$ remaining bits satisfies $|p_{i}-2^{-m}| < 2^{-m} \epsilon(n)$ for all $i$ and for some negligible function $\epsilon(n)$.

Kamp and Zuckerman has a theorem stating that if a function $f$ is a k-APRF, then $f$ is also a k-ERF. More specific, any extractor for oblivious bit-fixing sources with small enough error is also an APRF and therefore also a k-ERF. A more specific extractor is expressed in this lemma:

Lemma: Any $2^{-m} \epsilon(n)$-extractor $f: \{0,1\}^{n} \rightarrow \{0,1\}^{m}$ for the set of $(n,k)$ oblivious bit-fixing sources, where $\epsilon(n)$ is negligible, is also a k-APRF.

This lemma is proved by Kamp and Zuckerman. The lemma is proved by examining the distance from uniform of the output, which in a $2^{-m} \epsilon(n)$-extractor obviously is at most$2^{-m} \epsilon(n)$, which satisfies the condition of the APRF.

The lemma leads to the following theorem, stating that there in fact exists a k-APRF function as described: Theorem (existence): For any positive constant $\gamma \leq \frac{1}{2}$, there exists an explicit k-APRF $f: \{0,1\}^{n} \rightarrow \{0,1\}^{m}$, computable in a linear number of arithmetic operations on $m$-bit strings, with $m = \Omega(n^{2\gamma})$ and $k = n^{\frac{1}{2}+\gamma}$.

In the proof of this theorem, we need a definition of a negligible function. Negligibility is defined as a function $\epsilon(n)$ being negligible if $\epsilon(n) = O(\frac{1}{n^{c}})$ for all constants $c$.

Proof: Consider the following $\epsilon$-extractor: The function $f$ is an extractor for the set of $(n,\delta n)$ oblivious bit-fixing source: $f: \{0,1\}^{n} \rightarrow \{0,1\}^{m}$. $f$ has $m = \Omega(\delta^{2}n)$, $\epsilon = 2^{-cm}$ and $c > 1$.

The proof of this extractor's existence with $\delta \leq 1$, as well as the fact that it is computable in linear computing time on the length of $m$ can be found in the paper by Jesse Kamp and David Zuckerman (p. 1240).

That this extractor fulfills the criteria of the lemma is trivially true as $\epsilon = 2^{-cm}$ is a negligible function.

The size of $m$ is: $m = \Omega(\delta^{2}n) = \Omega(n) \geq \Omega(n^{2\gamma})$ Since we know $\delta \leq 1$ then the lower bound on $m$ is dominated by $n$. In the last step we use the fact that $\gamma \leq \frac{1}{2}$ which means that the power of $n$ is at most $1$. And since $n$ is a positive integer we know that $n^{2\gamma}$ is at most $n$.

$k$ is calculated by using the definition of the extractor, where we know:

$(n,k) = (n, \delta n) \Rightarrow k = \delta n$

and by using the value of $m$ we have:

$m = \delta^{2}n = n^{2\gamma}$

Using this value of $m$ we account for the worst case, where $k$ is on its lower bound. Now by algebraic calculations we get:

$\delta^{2}n = n^{2\gamma}$

$\Rightarrow \delta^{2} = n^{2\gamma -1}$

$\Rightarrow \delta = n^{\gamma -\frac{1}{2}}$

Which inserted in the value of $k$ gives

$k = \delta n = n^{\gamma -\frac{1}{2}}n = n^{\gamma +\frac{1}{2}}$,

which proves that there exists an explicit k-APRF extractor with the given properties. $\Box$

Examples

Von Neumann extractor

Template:Details Perhaps the earliest example is due to John von Neumann. His extractor took successive pairs of consecutive bits (non-overlapping) from the input stream. If the two bits matched, no output was generated. If the bits differed, the value of the first bit was output. The Von Neumann extractor can be shown to produce a uniform output even if the distribution of input bits is not uniform so long as each bit has the same probability of being one and there is no correlation between successive bits.

Thus, it takes as input a Bernoulli sequence with p not necessarily equal to 1/2, and outputs a Bernoulli sequence with $p = 1/2.$ More generally, it applies to any exchangeable sequence – it only relies on the fact that for any pair, 01 and 10 are equally likely: for independent trials, these have probabilities $p\cdot q = q\cdot p$, while for an exchangeable sequence the probability may be more complicated, but both are equally likely.

Cryptographic hash

Another approach is to fill a buffer with bits from the input stream and then apply a cryptographic hash to the buffer and use its output. This approach generally depends on assumed properties of the hash function.

Applications

Randomness extractors are used widely in cryptographic applications, whereby a cryptographic hash function is applied to a high-entropy, but non-uniform source, such as disk drive timing information or keyboard delays, to yield a uniformly random result.

Randomness extractors have played a part in recent developments in quantum cryptography, where photons are used by the randomness extractor to generate secure random bits.[2]

Randomness extraction is also used in some branches of computational complexity theory.

References

• Extractors and Pseudorandom Generators, Luca Trevisan
• Recent developments in explicit constructions of extractors, Ronen Shaltiel
• Randomness Extraction and Key Derivation Using the CBC, Cascade and HMAC Modes, Yevgeniy Dodis et al.
• Key Derivation and Randomness Extraction, Olivier Chevassut et al.
• Deterministic Extractors for Bit-Fixing Sources and Exposure-Resilient Cryptography, Jesse Kamp and David Zuckerman

See also

• Decorrelation
• Hardware random number generator