Randomness extraction Clause Samples

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- ▇▇▇▇. 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- ▇▇▇▇. 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]. 1.1 Basic terms‌ In this section, we define basic terms related to randomness extraction. Let us denote the used notation first: Um the uniform distribution over all elements of {0, 1}m s ∈R S s is randomly chosen from set S s real number from interval (0, 1) 1.1. (Statistical distance) Two distributions X1, X2 over the same domain T are s-close if for every event A ⊆ T , |X1(A) − X2(A)| ≤ s . We say distribution X over {0, 1}m is s-close to uniform if it is s-close tu Um. 1). We are interested in them mostly with respect to an extractor output distribution. On the co...