Concrete security: Difference between revisions

Content deleted Content added

Inline

Latest revision as of 19:54, 12 November 2023

In cryptography, concrete security or exact security is a practice-oriented approach that aims to give more precise estimates of the computational complexities of adversarial tasks than polynomial equivalence would allow.^{[citation needed]} It quantifies the security of a cryptosystem by bounding the probability of success for an adversary running for a fixed amount of time.^[1]^{[better source needed]} Security proofs with precise analyses are referred to as concrete.^[2]^{[better source needed]}

Traditionally, provable security is asymptotic: it classifies the hardness of computational problems using polynomial-time reducibility. Secure schemes are defined to be those in which the advantage of any computationally bounded adversary is negligible. While such a theoretical guarantee is important, in practice one needs to know exactly how efficient a reduction is because of the need to instantiate the security parameter - it is not enough to know that "sufficiently large" security parameters will do. An inefficient reduction results either in the success probability for the adversary or the resource requirement of the scheme being greater than desired.^{[citation needed]}

Concrete security parametrizes all the resources available to the adversary, such as running time and memory, and other resources specific to the system in question, such as the number of plaintexts it can obtain or the number of queries it can make to any oracles available. Then the advantage of the adversary is upper bounded as a function of these resources and of the problem size. It is often possible to give a lower bound (i.e. an adversarial strategy) matching the upper bound, hence the name exact security.^{[citation needed]}

Examples

Concrete security estimates have been applied to cryptographic algorithms:

In 1996, schemes for digital signatures based on the RSA and Rabin cryptosystems were proposed, which were shown to be approximately as difficult to break as the original cryptosystems.^[3]
In 1997, some notions of concrete security (left-or-right indistinguishability, real-or-random indistinguishability, find-then-guess security, and semantic-security) for symmetric encryption algorithms were proved approximately equivalent in various block cipher modes of operation such as CBC, CTR, and XOR (a stateless variant of CBC).^[4]^{[clarification needed]}
In 2017, a thesis showed that lattice point enumeration and lattice block reduction algorithms could be used to attack lattice-based cryptography.^[5]
In 2021, "guess-and-determine" and "guess-and-decode"-type attacks^{[clarification needed]} were demonstrated against a proposed pseudorandom generator in NC0, where instances with parameter values previously claimed to have 128-bit security were solved in about $2^{78}$ operations.^[6]^{[better source needed]}

In addition, a software tool named the "Foundational Cryptography Framework", which embeds into Coq, is able to formally verify proofs of concrete security.^[7] For example, it is able to verify the concrete security of ElGamal encryption.^[7]

References

^ "Modern symmetric-key Encryption". University of Maryland. Archived from the original on 2017-09-10. Retrieved 6 May 2021.
^ Kamara, Seny. "Lectures 2+3: Provable Security" (PDF). Archived (PDF) from the original on 2017-02-15. Retrieved 6 May 2021.
^ 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.
^ 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.
^ Walter, Michael (2017). "On the Concrete Security of Lattice-Based Cryptography". UC San Diego. Retrieved 6 May 2021.
^ 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 ^b Petcher, Adam (14 Oct 2014). "The Foundational Cryptography Framework". arXiv:1410.3735 [cs.PL].

External links

This cryptography-related article is a stub. You can help Wikipedia by expanding it.

[1] "Modern symmetric-key Encryption". University of Maryland. Archived from the original on 2017-09-10. Retrieved 6 May 2021.

[2] Kamara, Seny. "Lectures 2+3: Provable Security" (PDF). Archived (PDF) from the original on 2017-02-15. Retrieved 6 May 2021.

[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.

[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.

[5] Walter, Michael (2017). "On the Concrete Security of Lattice-Based Cryptography". UC San Diego. Retrieved 6 May 2021.

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

[:0-7] Petcher, Adam (14 Oct 2014). "The Foundational Cryptography Framework". arXiv:1410.3735 [cs.PL].

[1]

[2]

[3]

[4]

[5]

[6]

[7]

@@ Line 1: / Line 1: @@
+{{Short description|Cryptographic analysis}}
-In [[cryptography]], '''concrete security''' or '''exact security''' is a practice-oriented approach that aims to give more precise estimates of the computational complexities of [[Adversary (cryptography)|adversarial]] tasks than [[Polynomial-time reduction|polynomial equivalence]] would allow.
+{{Multiple issues|
+{{More citations needed|date=May 2021}}
+{{Technical|date=May 2021}}
+{{Primary sources|date=May 2021}}
+}}
+In [[cryptography]], '''concrete security''' or '''exact security''' is a practice-oriented approach that aims to give more precise estimates of the computational complexities of [[Adversary (cryptography)|adversarial]] tasks than [[Polynomial-time reduction|polynomial equivalence]] would allow.{{Citation needed|date=May 2021}} It quantifies the security of a cryptosystem by bounding the [[probability]] of success for an adversary running for a fixed amount of time.<ref>{{Cite web|title=Modern symmetric-key Encryption|url=https://www.cs.umd.edu/class/fall2017/cmsc456/module_5_symmetric_key_encryption.pptx|url-status=live|access-date=6 May 2021|website=University of Maryland|archive-url=https://web.archive.org/web/20170910200531/http://www.cs.umd.edu:80/class/fall2017/cmsc456/module_5_symmetric_key_encryption.pptx |archive-date=2017-09-10 }}</ref>{{Better source needed|date=May 2021}} [[Security proof|Security proofs]] with precise analyses are referred to as ''concrete''.<ref>{{Cite web|last=Kamara|first=Seny|title=Lectures 2+3: Provable Security|url=http://cs.brown.edu/~seny/2950-v/2-provablesecurity.pdf|url-status=live|access-date=6 May 2021|archive-url=https://web.archive.org/web/20170215070519/http://cs.brown.edu:80/~seny/2950-v/2-provablesecurity.pdf |archive-date=2017-02-15 }}</ref>{{Better source needed|date=May 2021}}
-Traditionally, [[provable security]] is '''asymptotic''': it classifies the hardness of computational problems using polynomial-time reducibility. Secure schemes are defined to be those in which the advantage of any [[computational boundedness|computationally bounded]] adversary is [[negligible function (cryptography)|negligible]]. While such a theoretical guarantee is important, in practice one needs to know exactly how efficient a reduction is because of the need to instantiate the [[security parameter]] - it is not enough to know that "sufficiently large" security parameters will do. An inefficient reduction results either in the success probability for the adversary or the  resource requirement of the scheme being greater than desired.
+Traditionally, [[provable security]] is '''asymptotic''': it classifies the hardness of computational problems using polynomial-time reducibility. Secure schemes are defined to be those in which the advantage of any [[computationally bounded adversary]] is [[negligible function (cryptography)|negligible]]. While such a theoretical guarantee is important, in practice one needs to know exactly how efficient a reduction is because of the need to instantiate the [[security parameter]] - it is not enough to know that "sufficiently large" security parameters will do. An inefficient reduction results either in the success probability for the adversary or the  resource requirement of the scheme being greater than desired.{{Citation needed|date=May 2021}}
-Concrete security parametrizes all the resources available to the adversary, such as running time and memory, and other resources specific to the system in question, such as the number of plaintexts it can obtain or the number of queries it can make to any [[oracle (cryptography)|oracles]] available. Then the advantage of the adversary is upper bounded as a function of these resources and of the problem size. It is often possible to give a lower bound (i.e, an adversarial strategy) matching the upper bound, hence the name exact security.
+Concrete security parametrizes all the resources available to the adversary, such as running time and memory, and other resources specific to the system in question, such as the number of plaintexts it can obtain or the number of queries it can make to any [[Oracle_attack|oracles]] available. Then the advantage of the adversary is upper bounded as a function of these resources and of the problem size. It is often possible to give a lower bound (i.e. an adversarial strategy) matching the upper bound, hence the name exact security.{{Citation needed|date=May 2021}}
-==References==
+== Examples ==
+Concrete security estimates have been applied to cryptographic algorithms:
-*  [[Mihir Bellare|M. Bellare]], A. Desai, E. Jokipii and [[Phillip Rogaway|P. Rogaway]]. [http://www-cse.ucsd.edu/users/mihir/papers/sym-enc.html  A Concrete Security Treatment of Symmetric Encryption: Analysis of the DES Modes of Operation].
-*  M. Bellare and P. Rogaway. [http://citeseer.ist.psu.edu/bellare96exact.html The Exact Security of Digital Signatures: How to Sign with RSA and Rabin]
+* In 1996, schemes for [[Digital signature|digital signatures]] based on the [[RSA (cryptosystem)|RSA]] and [[Rabin cryptosystem|Rabin]] cryptosystems were proposed, which were shown to be approximately as difficult to break as the original cryptosystems.<ref>{{Cite book|last1=Bellare|first1=Mihir|last2=Rogaway|first2=Philip|title=Advances in Cryptology — EUROCRYPT '96 |chapter=The Exact Security of Digital Signatures-How to Sign with RSA and Rabin |date=1996 |chapter-url=https://link.springer.com/content/pdf/10.1007/3-540-68339-9_34.pdf|series=Lecture Notes in Computer Science|volume=1070|publisher=[[Springer-Verlag]]|pages=399–416|doi=10.1007/3-540-68339-9_34|isbn=978-3-540-68339-1}}</ref>
-[[Category:Cryptography]]
+* In 1997, some notions of concrete security (''left-or-right indistinguishability'', ''real-or-random indistinguishability'', ''find-then-guess security'', and ''semantic-security'') for [[symmetric encryption]] algorithms were proved approximately equivalent in various [[Block cipher mode of operation|block cipher modes of operation]] such as CBC, CTR, and XOR (a stateless variant of CBC).<ref>{{Cite book|last1=Bellare|first1=Mihir|last2=Desai|first2=A.|last3=Jokipii|first3=E.|last4=Rogaway|first4=Philip|title=Proceedings 38th Annual Symposium on Foundations of Computer Science |chapter=A concrete security treatment of symmetric encryption |date=Oct 1997|chapter-url=http://cseweb.ucsd.edu/~mihir/papers/sym-enc.pdf|pages=394–403|doi=10.1109/SFCS.1997.646128|isbn=0-8186-8197-7|s2cid=42604387 }}</ref>{{Clarify|date=May 2021}}
+* In 2017, a thesis showed that lattice point enumeration and lattice block reduction algorithms could be used to attack [[lattice-based cryptography]].<ref>{{Cite journal|last=Walter|first=Michael|date=2017|title=On the Concrete Security of Lattice-Based Cryptography|url=https://escholarship.org/uc/item/5n51z56|journal=UC San Diego|access-date=6 May 2021}}</ref>
+* In 2021, "guess-and-determine" and "guess-and-decode"-type attacks{{Clarify|date=May 2021}} were demonstrated against a proposed [[pseudorandom generator]] in [[NC0]], where instances with parameter values previously claimed to have 128-bit security were solved in about <math>2^{78}</math> operations.<ref>{{Cite arXiv|last1=Yang|first1=Jian|last2=Guo|first2=Qian|last3=Johansson|first3=Thomas|last4=Lentmaier|first4=Michael|date=3 Mar 2021|title=Revisiting the Concrete Security of Goldreich's Pseudorandom Generator|class=cs.CR |eprint=2103.02668}}</ref>{{Better source needed|date=May 2021}}
+In addition, a software tool named the "Foundational Cryptography Framework", which embeds into [[Coq (software)|Coq]], is able to [[Formal verification|formally verify]] proofs of concrete security.<ref name=":0">{{Cite arXiv|last=Petcher|first=Adam|date=14 Oct 2014|title=The Foundational Cryptography Framework|class=cs.PL |eprint=1410.3735}}</ref> For example, it is able to verify the concrete security of [[ElGamal encryption]].<ref name=":0" />
+==References==
+{{Reflist}}
 [[Category:Theory of cryptography]]
+== External links ==
+*https://www.cs.purdue.edu/homes/jblocki/courses/555_Fall18/slides/Week2.pdf
+*https://crypto.stanford.edu/~dabo/cryptobook/draft_0_3.pdf
+*[https://crypto.stanford.edu/~dabo/cryptobook/draft_0_3.pdf https://eprint.iacr.org/2006/278.pdf]
+*https://www.baigneres.net/downloads/2007_provable_security.pdf
+*https://eprint.iacr.org/2020/1213.pdf
 {{crypto-stub}}