Randomness extractor
Encyclopedia
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, but uniformly distributed. In other words, outputting a completely random sample from a semi-random input.
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.
, 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
such that for every distribution X on {0, 1}n with
the distribution 
is ε-close to the uniform distribution on {0, 1}m.
Futuremore, if
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.
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 = Extn of functions
is an explicit (k, ε)-extractor if Ext(x, y) can be computed in polynomial time (in its input length) and for every n, Extn 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
and output length
the seed with the extractor's output yields a distribution that is close to uniform.
Definition (Strong Extractor): A
-strong extractor is a function
such that for every distribution
on 
with 
the distribution 
(The two copies of 
denote the same random variable) is 
-close to the uniform distribution on 
.
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
where, for a random input 
, when a computationally unbounded adversary 
can adaptively read all of 
except for 
bits, 
for some negligible function 
.
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
APRF is a function 
where, for any setting of 
bits of the input 
to any fixed values, the probability vector 
of the output 
over the random choices for the 
remaining bits satisfies 
for all 
and for some negligible function 
.
Kamp and Zuckerman has a theorem stating that if a function
is a k-APRF, then 
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
-extractor 
for the set of 
oblivious bit-fixing sources, where 
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
-extractor obviously is at most
, 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
, there exists an explicit k-APRF 
, computable in a linear number of arithmetic operations on 
-bit strings, with 
and 
.
In the proof of this theorem, we need a definition of a negligible function. Negligibility is defined as a function
being negligible if 
for all constants 
.
Proof:
Consider the following
-extractor: The function 
is an extractor for the set of 
oblivious bit-fixing source: 
. 
has 
, 
and 
.
The proof of this extractor's existence with
, as well as the fact that it is computable in linear computing time on the length of 
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
is a negligible function.
The size of
is:
Since we know
then the lower bound on 
is dominated by 
. In the last step we use the fact that 
which means that the power of 
is at most 
. And since 
is a positive integer we know that 
is at most 
.
is calculated by using the definition of the extractor, where we know:
and by using the value of
we have:
Using this value of
we account for the worst case, where 
is on its lower bound. Now by algebraic calculations we get:
Which inserted in the value of
gives
,
which proves that there exists an explicit k-APRF extractor with the given properties.
. 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
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
, while for an exchangeable sequence the probability may be more complicated, but both are equally likely.
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.http://newsroom.spie.org/x4741.xml?highlight=x535
Randomness extraction is also used in some branches of computational complexity theory
.
Random extraction is also used to convert data to a simple random sample, which is normally distributed, and independent, which is desired by statistics.
Information entropy
In information theory, entropy is a measure of the uncertainty associated with a random variable. In this context, the term usually refers to the Shannon entropy, which quantifies the expected value of the information contained in a message, usually in units such as bits...
source (such as radioactive decay
Radioactive decay
Radioactive decay is the process by which an atomic nucleus of an unstable atom loses energy by emitting ionizing particles . The emission is spontaneous, in that the atom decays without any physical interaction with another particle from outside the atom...
, or thermal noise), generates a random output that is shorter, but uniformly distributed. In other words, outputting a completely random sample from a semi-random input.
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
Pseudorandom generator
In theoretical computer science, a pseudorandom generator is a deterministic procedure that produces a pseudorandom distribution from a short uniform input, known as a random seed.-Definition:...
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-entropyMin-entropy
In probability theory or information theory, the min-entropy of a discrete random event x with possible states 1... n and corresponding probabilities p1... pn is...
, which is a measurement of the amount of randomness in the worst case. The definition uses the worst case randomness of min-entropy
Min-entropy
In probability theory or information theory, the min-entropy of a discrete random event x with possible states 1... n and corresponding probabilities p1... pn is...
and not the average case randomness described by Shannon-entropy
Information entropy
In information theory, entropy is a measure of the uncertainty associated with a random variable. In this context, the term usually refers to the Shannon entropy, which quantifies the expected value of the information contained in a message, usually in units such as bits...
.
Definition (Extractor): A (k, ε)-extractor is a function
such that for every distribution X on {0, 1}n with
the distribution is ε-close to the uniform distribution on {0, 1}m.Futuremore, if
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 methodProbabilistic method
The probabilistic method is a nonconstructive method, primarily used in combinatorics and pioneered by Paul Erdős, for proving the existence of a prescribed kind of mathematical object. It works by showing that if one randomly chooses objects from a specified class, the probability that the...
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 = Extn of functions
is an explicit (k, ε)-extractor if Ext(x, y) can be computed in polynomial time (in its input length) and for every n, Extn 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
and output length
-
.
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 concatenatingConcatenation
In computer programming, string concatenation is the operation of joining two character strings end-to-end. For example, the strings "snow" and "ball" may be concatenated to give "snowball"...
the seed with the extractor's output yields a distribution that is close to uniform.
Definition (Strong Extractor): A
-strong extractor is a function
such that for every distribution
on with the distribution (The two copies of denote the same random variable) is -close to the uniform distribution on .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
Cryptography
Cryptography is the practice and study of techniques for secure communication in the presence of third parties...
is random key generation
Key generation
Key generation is the process of generating keys for cryptography. A key is used to encrypt and decrypt whatever data is being encrypted/decrypted....
. 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
Secrecy
Secrecy is the practice of hiding information from certain individuals or groups, perhaps while sharing it with other individuals...
, 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
Encryption
In cryptography, encryption is the process of transforming information using an algorithm to make it unreadable to anyone except those possessing special knowledge, usually referred to as a key. The result of the process is encrypted information...
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
where, for a random input , when a computationally unbounded adversary can adaptively read all of except for bits, for some negligible function .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
APRF is a function where, for any setting of bits of the input to any fixed values, the probability vector of the output over the random choices for the remaining bits satisfies for all and for some negligible function .Kamp and Zuckerman has a theorem stating that if a function
is a k-APRF, then 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
-extractor for the set of oblivious bit-fixing sources, where 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
-extractor obviously is at most, 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
, there exists an explicit k-APRF , computable in a linear number of arithmetic operations on -bit strings, with and .In the proof of this theorem, we need a definition of a negligible function. Negligibility is defined as a function
being negligible if for all constants .Proof:
Consider the following
-extractor: The function is an extractor for the set of oblivious bit-fixing source: . has , and .The proof of this extractor's existence with
, as well as the fact that it is computable in linear computing time on the length of 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
is a negligible function.The size of
is:Since we know
then the lower bound on is dominated by . In the last step we use the fact that which means that the power of is at most . And since is a positive integer we know that is at most . is calculated by using the definition of the extractor, where we know:and by using the value of
we have:Using this value of
we account for the worst case, where is on its lower bound. Now by algebraic calculations we get:Which inserted in the value of
gives,which proves that there exists an explicit k-APRF extractor with the given properties.
Von Neumann extractor
Perhaps the earliest example is due to John von NeumannJohn von Neumann
John von Neumann was a Hungarian-American mathematician and polymath who made major contributions to a vast number of fields, including set theory, functional analysis, quantum mechanics, ergodic theory, geometry, fluid dynamics, economics and game theory, computer science, numerical analysis,...
. 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
Correlation
In statistics, dependence refers to any statistical relationship between two random variables or two sets of data. Correlation refers to any of a broad class of statistical relationships involving dependence....
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
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
, 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
Quantum cryptography
Quantum key distribution uses quantum mechanics to guarantee secure communication. It enables two parties to produce a shared random secret key known only to them, which can then be used to encrypt and decrypt messages...
, where photons are used by the randomness extractor to generate secure random bits.http://newsroom.spie.org/x4741.xml?highlight=x535
Randomness extraction is also used in some branches of computational complexity theory
Computational complexity theory
Computational complexity theory is a branch of the theory of computation in theoretical computer science and mathematics that focuses on classifying computational problems according to their inherent difficulty, and relating those classes to each other...
.
Random extraction is also used to convert data to a simple random sample, which is normally distributed, and independent, which is desired by statistics.