Full entropy

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 n bits of entropy for an n-bit output). ^[1]

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: ${\displaystyle 1-\epsilon }$, where per NIST a practical ${\displaystyle \epsilon <2^{-32}}$. ^[1]

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. ^[2]

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 W elements of length n. 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 W and positive parameter ${\displaystyle \delta }$ is achieved if an adversary cannot guess the real set with probability higher than ${\displaystyle {\frac {1}{2}}+\delta }$. ^[3]

Additional entropy

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

Minimum value of additional entropy H-n

W	${\displaystyle \delta =2^{-20}}$	${\displaystyle \delta =2^{-10}}$
${\displaystyle 2^{32}}$	67.3	47.3
${\displaystyle 2^{48}}$	83.3	63.3
${\displaystyle 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. ^[5] NIST therefore defines the "vetted conditioning components" in its NIST SP 800-90B standard, including AES-CBC-MAC. ^[5]

References

1. Buller et al. 2023, p. i.
2. Johnston 2018, p. 18.
3. Buller et al. 2023, p. 1.
4. Buller et al. 2023, p. 2.
5. Johnston 2018, p. 16.

Sources

• Buller, Darryl; Kaufer, Aaron; Roginsky, Allen; Turan, Meltem Sönmez (April 2023). "NIST Interagency Report NIST IR 8427 Discussion on the Full Entropy Assumption of the SP 800-90 Series" (PDF). NIST. doi:10.6028/NIST.IR.8427.ipd . Retrieved 1 November 2023.
• Johnston, D. (2018). Random Number Generators—Principles and Practices: A Guide for Engineers and Programmers. De Gruyter. ISBN   978-1-5015-0606-2 . Retrieved 2023-11-01.