Full entropy

Template:Short description In cryptography, full entropy is a property of an output of a random number generator. The output has full entropy if it cannot practically be distinguished from an output of a theoretical perfect random number source (has almost Template:Mvar bits of entropy for an Template:Mvar-bit output).Template:Sfn

The term is extensively used in the NIST random generator standards NIST SP 800-90A and NIST SP 800-90B. With full entropy, the per-bit entropy in the output of the random number generator is close to one: $1-ϵ$, where per NIST a practical $ϵ<2^{-32}$.Template:Sfn

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.Template:Sfn

Definition

The mathematical definition relies on a "distinguishing game": an adversary with an unlimited computing power is provided with two sets of random numbers, each containing Template:Mvar elements of length Template:Mvar. 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. The full entropy for particular values of Template:Mvar and positive parameter Template:Mvar is achieved if an adversary cannot guess the real set with probability higher than $\frac{1}{2}+\delta$.Template:Sfn

Additional entropy

The practical way to achieve the full entropy is to obtain from an entropy source bit strings longer than Template:Mvar bits, apply to them a high-quality randomness extractor that produces the Template:Mvar-bit result, and build the real set from these results. The ideal elements by nature have an entropy value of Template:Mvar. The inputs of the conditioning function will need to have a higher min-entropy value Template:Mvar to satisfy the full-entropy definition. The number of additional bits of entropy $H-n$ depends on Template:Mvar and Template:Mvar; the following table contains few representative values:Template:Sfn

Minimum value of additional entropy $H-n$

Template:Mvar	$\delta =2^{-20}$	$\delta =2^{-10}$
$2^{32}$	67.3	47.3
$2^{48}$	83.3	63.3
$2^{56}$	91.3	71.3

Randomness extractor requirements

Not every randomness extractor will produce the desired results. For example, the Von Neumann extractor, while providing an unbiased output, does not decorrelate groups of bits, so for serially correlated inputs (typical for many entropy sources) the output bits will not be independent.Template:Sfn NIST therefore defines the "vetted conditioning components" in its NIST SP 800-90B standard, including AES-CBC-MAC.Template:Sfn

Sources

• Template:Cite web
• Template:Cite book