Full entropy

<h2 id="definition">Definition</h2>
<p>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 <i>ideal</i>, it contains bit strings from the theoretically perfect random number generator, the other set is <i>real</i> and includes bit strings from the practical random number source after a <a href="/facts/Randomness_extractor/YxS1Ia7x">randomness extractor</a>. The full entropy for particular values of W and positive parameter δ is achieved if an adversary cannot guess the real set with probability higher than 
  
    
      
        
          
            1
            2
          
        
        +
        δ
      
    
    {\displaystyle {\frac {1}{2}}+\delta }
  
.<a class="footnote-ref" id="fnref:4" href="#fn:4"><sup>4</sup></a>
</p>
<h2 id="additional-entropy">Additional entropy</h2>
<p>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 <a href="/facts/Min-entropy/U0j0SNcp">min-entropy</a> value H to satisfy the full-entropy definition. The number of additional bits of entropy 
  
    
      
        H
        −
        n
      
    
    {\displaystyle H-n}
  
 depends on W and δ; the following table contains few representative values:<a class="footnote-ref" id="fnref:5" href="#fn:5"><sup>5</sup></a>
</p>
Minimum value of additional entropy                     H        −        n              {\displaystyle H-n}  <table><tbody><tr><th>W</th><th>                    δ        =                  2                      −            20                                {\displaystyle \delta =2^{-20}}  </th><th>                    δ        =                  2                      −            10                                {\displaystyle \delta =2^{-10}}  </th></tr><tr><td>                              2                      32                                {\displaystyle 2^{32}}  </td><td>67.3</td><td>47.3</td></tr><tr><td>                              2                      48                                {\displaystyle 2^{48}}  </td><td>83.3</td><td>63.3</td></tr><tr><td>                              2                      56                                {\displaystyle 2^{56}}  </td><td>91.3</td><td>71.3</td></tr></tbody></table>
<h2 id="randomness-extractor-requirements">Randomness extractor requirements</h2>
<p>Not every <a href="/facts/Randomness_extractor/YxS1Ia7x">randomness extractor</a> will produce the desired results. For example, the <a href="/facts/Von_Neumann_extractor/YxS1Ia7x">Von Neumann extractor</a>, while providing an unbiased output, does not decorrelate groups of bits, so for serially correlated inputs (typical for many <a href="/facts/Entropy_source/Kc7HIkgJ">entropy sources</a>) the output bits will not be <a href="/facts/Independent_and_identically_distributed_random_variables/othIRaWt">independent</a>.<a class="footnote-ref" id="fnref:6" href="#fn:6"><sup>6</sup></a> NIST therefore defines the "vetted conditioning components" in its <a href="/facts/NIST_SP_800-90B/8hCL5kC0">NIST SP 800-90B</a> standard, including <a href="/facts/Rijndael/HdXGBY2Q">AES</a>-<a href="/facts/CBC-MAC/nuJt6zMb">CBC-MAC</a>.<a class="footnote-ref" id="fnref:7" href="#fn:7"><sup>7</sup></a>
</p>

<h2 id="sources">Sources</h2>
<ul><li>Buller, Darryl; Kaufer, Aaron; Roginsky, Allen; Turan, Meltem Sönmez (April 2023). <a href="https://nvlpubs.nist.gov/nistpubs/ir/2023/NIST.IR.8427.pdf">"NIST Interagency Report NIST IR 8427 Discussion on the Full Entropy Assumption of the SP 800-90 Series"</a> (PDF). <a href="/facts/NIST/gr9Fnh85">NIST</a>. <a href="/facts/Doi_(identifier)/muM9Etpq">doi</a>:<a href="https://doi.org/10.6028%2FNIST.IR.8427.ipd">10.6028/NIST.IR.8427.ipd</a>. Retrieved 1 November 2023.</li>
<li>Johnston, D. (2018). <a href="https://books.google.com/books?id=kIxuDwAAQBAJ&pg=PA18"><i>Random Number Generators—Principles and Practices: A Guide for Engineers and Programmers</i></a>. De Gruyter. <a href="/facts/ISBN_(identifier)/15AdSPa9">ISBN</a> 978-1-5015-0606-2. Retrieved 2023-11-01.</li></ul>

<h2 id="references">References</h2>

<ol>
<li id="fn:1"><p>Buller et al. 2023, p. i. - 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. <a href="https://nvlpubs.nist.gov/nistpubs/ir/2023/NIST.IR.8427.pdf" target="_blank">https://nvlpubs.nist.gov/nistpubs/ir/2023/NIST.IR.8427.pdf</a> <a href="#fnref:1" class="footnote-back-ref">↩</a></p></li>
<li id="fn:2"><p>Buller et al. 2023, p. i. - 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. <a href="https://nvlpubs.nist.gov/nistpubs/ir/2023/NIST.IR.8427.pdf" target="_blank">https://nvlpubs.nist.gov/nistpubs/ir/2023/NIST.IR.8427.pdf</a> <a href="#fnref:2" class="footnote-back-ref">↩</a></p></li>
<li id="fn:3"><p>Johnston 2018, p. 18. - 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. <a href="https://books.google.com/books?id=kIxuDwAAQBAJ&pg=PA18" target="_blank">https://books.google.com/books?id=kIxuDwAAQBAJ&pg=PA18</a> <a href="#fnref:3" class="footnote-back-ref">↩</a></p></li>
<li id="fn:4"><p>Buller et al. 2023, p. 1. - 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. <a href="https://nvlpubs.nist.gov/nistpubs/ir/2023/NIST.IR.8427.pdf" target="_blank">https://nvlpubs.nist.gov/nistpubs/ir/2023/NIST.IR.8427.pdf</a> <a href="#fnref:4" class="footnote-back-ref">↩</a></p></li>
<li id="fn:5"><p>Buller et al. 2023, p. 2. - 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. <a href="https://nvlpubs.nist.gov/nistpubs/ir/2023/NIST.IR.8427.pdf" target="_blank">https://nvlpubs.nist.gov/nistpubs/ir/2023/NIST.IR.8427.pdf</a> <a href="#fnref:5" class="footnote-back-ref">↩</a></p></li>
<li id="fn:6"><p>Johnston 2018, p. 16. - 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. <a href="https://books.google.com/books?id=kIxuDwAAQBAJ&pg=PA18" target="_blank">https://books.google.com/books?id=kIxuDwAAQBAJ&pg=PA18</a> <a href="#fnref:6" class="footnote-back-ref">↩</a></p></li>
<li id="fn:7"><p>Johnston 2018, p. 16. - 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. <a href="https://books.google.com/books?id=kIxuDwAAQBAJ&pg=PA18" target="_blank">https://books.google.com/books?id=kIxuDwAAQBAJ&pg=PA18</a> <a href="#fnref:7" class="footnote-back-ref">↩</a></p></li>
</ol>

Full entropy open-in-new

Full entropy