In cryptography, full entropy is a property of an output of a

random number generator Random number generation is a process by which, often by means of a random number generator (RNG), a sequence of numbers or symbols is generated that cannot be reasonably predicted better than by random chance. This means that the particular ou ...

. The output has full entropy if it cannot practically be distinguished from an output of a theoretical perfect random number source (has almost bits of entropy for an -bit output). The term is extensively used in the

NIST The National Institute of Standards and Technology (NIST) is an agency of the United States Department of Commerce whose mission is to promote American innovation and industrial competitiveness. NIST's activities are organized into physical s ...

random generator standards

NIST SP 800-90A NIST SP 800-90A ("SP" stands for "''special publication''") is a publication by the National Institute of Standards and Technology with the title ''Recommendation for Random Number Generation Using Deterministic Random Bit Generators''. The publica ...

and

NIST SP 800-90B NIST SP 800-90B ("SP" stands for "''special publication''") is a publication by the National Institute of Standards and Technology with the title ''Recommendation for the Entropy Sources Used for Random Bit Generation''. The publication specifies ...

. With full entropy, the per-bit entropy in the output of the random number generator is close to one:

1-\epsilon

, where per NIST a practical

\epsilon<2^

. Some sources use the term to define the ideal random bit string (one bit of entropy per bit of output). In this sense, "getting to 100% full entropy is impossible" in the real world.

Definition

The mathematical definition relies on a "distinguishing game": an adversary with unlimited computing power is provided with two sets of random numbers, each containing elements of length . One set is ''ideal'', it contains bit strings from the theoretically perfect random number generator, the other set is ''real'' and includes bit strings from the practical random number source after a

randomness extractor A randomness extractor, often simply called an "extractor", is a function, which being applied to output from a weak entropy source, together with a short, uniformly random seed, generates a highly random output that appears Independent and identic ...

. The full entropy for particular values of and positive parameter is achieved if an adversary cannot guess the real set with probability higher than

\frac 1 2 + \delta

Additional entropy

The practical way to achieve the full entropy is to obtain from an entropy source bit strings longer than bits, apply to them a high-quality randomness extractor that produces the -bit result, and build the real set from these results. The ideal elements by nature have an entropy value of . The inputs of the conditioning function will need to have a higher

min-entropy The min-entropy, in information theory, is the smallest of the Rényi family of entropies, corresponding to the most conservative way of measuring the unpredictability of a set of outcomes, as the negative logarithm of the probability of the ''mo ...

value to satisfy the full-entropy definition. The number of additional bits of entropy

H-n

depends on and ; the following table contains few representative values:

Randomness extractor requirements

Not every

will produce the desired results. For example, the

Von Neumann extractor A randomness extractor, often simply called an "extractor", is a function, which being applied to output from a weak entropy source, together with a short, uniformly random seed, generates a highly random output that appears independent from the so ...

, while providing an unbiased output, does not decorrelate groups of bits, so for serially correlated inputs (typical for many

entropy source In computing, a hardware random number generator (HRNG), true random number generator (TRNG), non-deterministic random bit generator (NRBG), or physical random number generator is a device that random number generation, generates random numbers f ...

s) the output bits will not be

independent Independent or Independents may refer to: Arts, entertainment, and media Artist groups * Independents (artist group), a group of modernist painters based in Pennsylvania, United States * Independentes (English: Independents), a Portuguese artist ...

. NIST therefore defines the "vetted conditioning components" in its

standard, including AES-

CBC-MAC In cryptography, a cipher block chaining message authentication code (CBC-MAC) is a technique for constructing a message authentication code (MAC) from a block cipher. The message is encrypted with some block cipher algorithm in cipher block ch ...

References

Sources

* * Random number generation {{cryptography-stub