Concrete security

<h2 id="examples">Examples</h2>
Concrete security estimates have been applied to cryptographic algorithms:

<ul><li>In 1996, schemes for <a href="/facts/Digital_signature/tY7e2pnW">digital signatures</a> based on the <a href="/facts/RSA_(cryptosystem)/XTzyfHuq">RSA</a> and <a href="/facts/Rabin_cryptosystem/Q7MRkmdo">Rabin</a> cryptosystems were proposed, which were shown to be approximately as difficult to break as the original cryptosystems.<a class="footnote-ref" id="fnref:3" href="#fn:3">3</a></li>
<li>In 1997, some notions of concrete security (left-or-right indistinguishability, real-or-random indistinguishability, find-then-guess security, and semantic-security) for <a href="/facts/Symmetric_encryption/5zfe0b76">symmetric encryption</a> algorithms were proved approximately equivalent in various <a href="/facts/Block_cipher_mode_of_operation/vIUabB2z">block cipher modes of operation</a> such as CBC, CTR, and XOR (a stateless variant of CBC).<a class="footnote-ref" id="fnref:4" href="#fn:4">4</a></li>
<li>In 2017, a thesis showed that lattice point enumeration and lattice block reduction algorithms could be used to attack <a href="/facts/Lattice-based_cryptography/66HyNf1P">lattice-based cryptography</a>.<a class="footnote-ref" id="fnref:5" href="#fn:5">5</a></li>
<li>In 2021, "guess-and-determine" and "guess-and-decode"-type attacks were demonstrated against a proposed <a href="/facts/Pseudorandom_generator/sdRrlm8Y">pseudorandom generator</a> in <a href="/facts/NC0/UGJ79CeY">NC0</a>, where instances with parameter values previously claimed to have 128-bit security were solved in about 
 
 
 
 
 2
 
 78
 
 
 
 
 {\displaystyle 2^{78}}
 
 operations.<a class="footnote-ref" id="fnref:6" href="#fn:6">6</a>[better source needed]</li></ul>
In addition, a software tool named the "Foundational Cryptography Framework", which embeds into <a href="/facts/Coq_(software)/7oBXgLCE">Coq</a>, is able to <a href="/facts/Formal_verification/BYD4GnJR">formally verify</a> proofs of concrete security.<a class="footnote-ref" id="fnref:7" href="#fn:7">7</a> For example, it is able to verify the concrete security of <a href="/facts/ElGamal_encryption/sKDVyMyR">ElGamal encryption</a>.<a class="footnote-ref" id="fnref:8" href="#fn:8">8</a>

<h2 id="external-links">External links</h2>
<ul><li><a href="https://www.cs.purdue.edu/homes/jblocki/courses/555_Fall18/slides/Week2.pdf">https://www.cs.purdue.edu/homes/jblocki/courses/555_Fall18/slides/Week2.pdf</a></li>
<li><a href="https://crypto.stanford.edu/~dabo/cryptobook/draft_0_3.pdf">https://crypto.stanford.edu/~dabo/cryptobook/draft_0_3.pdf</a></li>
<li><a href="https://crypto.stanford.edu/~dabo/cryptobook/draft_0_3.pdf">https://eprint.iacr.org/2006/278.pdf</a></li>
<li><a href="https://www.baigneres.net/downloads/2007_provable_security.pdf">https://www.baigneres.net/downloads/2007_provable_security.pdf</a></li>
<li><a href="https://eprint.iacr.org/2020/1213.pdf">https://eprint.iacr.org/2020/1213.pdf</a></li></ul>

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

<ol>
<li id="fn:1">"Modern symmetric-key Encryption". University of Maryland. Archived from the original on 2017-09-10. Retrieved 6 May 2021. <a href="https://www.cs.umd.edu/class/fall2017/cmsc456/module_5_symmetric_key_encryption.pptx" target="_blank">https://www.cs.umd.edu/class/fall2017/cmsc456/module_5_symmetric_key_encryption.pptx</a> <a href="#fnref:1" class="footnote-back-ref">↩</a></li>
<li id="fn:2">Kamara, Seny. "Lectures 2+3: Provable Security" (PDF). Archived (PDF) from the original on 2017-02-15. Retrieved 6 May 2021. <a href="http://cs.brown.edu/~seny/2950-v/2-provablesecurity.pdf" target="_blank">http://cs.brown.edu/~seny/2950-v/2-provablesecurity.pdf</a> <a href="#fnref:2" class="footnote-back-ref">↩</a></li>
<li id="fn:3">Bellare, Mihir; Rogaway, Philip (1996). "The Exact Security of Digital Signatures-How to Sign with RSA and Rabin" (PDF). Advances in Cryptology — EUROCRYPT '96. Lecture Notes in Computer Science. Vol. 1070. Springer-Verlag. pp. 399–416. doi:10.1007/3-540-68339-9_34. ISBN 978-3-540-68339-1. <a href="978-3-540-68339-1" target="_blank">978-3-540-68339-1</a> <a href="#fnref:3" class="footnote-back-ref">↩</a></li>
<li id="fn:4">Bellare, Mihir; Desai, A.; Jokipii, E.; Rogaway, Philip (Oct 1997). "A concrete security treatment of symmetric encryption" (PDF). Proceedings 38th Annual Symposium on Foundations of Computer Science. pp. 394–403. doi:10.1109/SFCS.1997.646128. ISBN 0-8186-8197-7. S2CID 42604387. <a href="0-8186-8197-7" target="_blank">0-8186-8197-7</a> <a href="#fnref:4" class="footnote-back-ref">↩</a></li>
<li id="fn:5">Walter, Michael (2017). "On the Concrete Security of Lattice-Based Cryptography". UC San Diego. Retrieved 6 May 2021. <a href="https://escholarship.org/uc/item/5n51z56" target="_blank">https://escholarship.org/uc/item/5n51z56</a> <a href="#fnref:5" class="footnote-back-ref">↩</a></li>
<li id="fn:6">Yang, Jian; Guo, Qian; Johansson, Thomas; Lentmaier, Michael (3 Mar 2021). "Revisiting the Concrete Security of Goldreich's Pseudorandom Generator". arXiv:2103.02668 [cs.CR]. <a href="/wiki/ArXiv_(identifier)" target="_blank">/wiki/ArXiv_(identifier)</a> <a href="#fnref:6" class="footnote-back-ref">↩</a></li>
<li id="fn:7">Petcher, Adam (14 Oct 2014). "The Foundational Cryptography Framework". arXiv:1410.3735 [cs.PL]. <a href="/wiki/ArXiv_(identifier)" target="_blank">/wiki/ArXiv_(identifier)</a> <a href="#fnref:7" class="footnote-back-ref">↩</a></li>
<li id="fn:8">Petcher, Adam (14 Oct 2014). "The Foundational Cryptography Framework". arXiv:1410.3735 [cs.PL]. <a href="/wiki/ArXiv_(identifier)" target="_blank">/wiki/ArXiv_(identifier)</a> <a href="#fnref:8" class="footnote-back-ref">↩</a></li>
</ol>

Concrete security open-in-new

Concrete security