Randomness extraction. Properties of randomized algorithms and cryptographic protocols are very often proven under the assumption of having an access to a source of true random data. Replacing it with a data source that produces more pre- dictable output or, in a worse case, with a source that is influenced by an attacker, may lead to the loss of these properties. Nowadays, pseudo- random number generators are broadly used as randomness providers. Usually, they employ some computational problem, that is believed to be hard, however, this still means they are secure only from the computational perspective. This need of randomness is very unfavourable, taking into account that contemporary computers are built using deterministically behaving hard- xxxx. Therefore, randomness itself has to be brought mostly by some ad- ditional hardware, most likely based on the phenomena producing out- put containing some entropy. Among such devices, we can count either purpose-built hardware measuring some physical phenomena (e.g. thermal noise, photo-electric effect) or input devices, intended originally for user interaction, utilized in this way. Fortunately, mobile devices offer a wide range of hardware that belongs into the latter category. The output of a randomness source often contains only a limited amount of entropy. The exact (lower) limit should be determined for every source to inform us about how much of the original information we can use in prac- xxxx. Also, the overall properties of the source need to be examined, with the aim to design an algorithm producing true randomness from the source output. This is, in fact, a point where we employ randomness extractors. This chapter has introductory character into the area of randomness ex- tractors in order to clarify the given terms. Presented results were chosen according to the contribution for our thesis. For a more extensive overview, the reader is referred to [33, 32].
Randomness extraction. Let a random variable X be given. An extractor is a randomized func- tion which uses the randomness inherent in X to obtain a nearly uniform bit string. Allowing the function to be randomized means that it has ac- cess to additional uniform randomness, called seed, and we expect that the concatenation of the seed and the output of the extractor is close to uniform (this implies that the extractor cannot just output the seed).
