Randomness Extractors in Cryptography
One of the most important aspects of cryptography is random key generation. It is often necessary to generate secret and random keys from sources that are semi-secret or which may be compromised to some degree. By taking a single, short (and secret) random key as a source, an extractor can be used to generate a longer pseudo-random key, which then can be used for public key encryption. More specifically, when a strong extractor is used its output will appear be uniformly random, even to someone who sees part (but not all) of the source. For example, if the source is known but the seed is not known (or vice versa). This property of extractors is particularly useful in what is commonly called Exposure-Resilient cryptography in which the desired extractor is used as an Exposure-Resilient Function (ERF). Exposure-Resilient cryptography takes into account that the fact that it is difficult to keep secret the initial exchange of data which often takes place during the initialization of an encryption application e.g., the sender of encrypted information has to provide the receivers with information which is required for decryption.
The following paragraphs define and establish an important relationship between two kinds of ERF--k-ERF and k-APRF--which are useful in Exposure-Resilient cryptography.
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 (defined below).
The goal is to construct an adaptive ERF whose output is highly random and uniformly distributed. But a stronger condition is often needed in which every output occurs with almost uniform probability. For this purpose Almost-Perfect Resilient Functions (APRF) are used. The definition of an APRF is as follows:
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 have proved a theorem stating that if a function is a k-APRF, then is also a k-ERF. More specifically, any extractor having sufficiently small error and taking as input an oblivious, bit-fixing source 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 .
Definition (negligible function): In the proof of this theorem, we need a definition of a negligible function. A function is defined as 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 .
The value of 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.
Read more about this topic: Randomness Extractor