Provable security

Last updated

Provable security refers to any type or level of computer security that can be proved. It is used in different ways by different fields.

Contents

Usually, this refers to mathematical proofs, which are common in cryptography. In such a proof, the capabilities of the attacker are defined by an adversarial model (also referred to as attacker model): the aim of the proof is to show that the attacker must solve the underlying hard problem in order to break the security of the modelled system. Such a proof generally does not consider side-channel attacks or other implementation-specific attacks, because they are usually impossible to model without implementing the system (and thus, the proof only applies to this implementation).

Outside of cryptography, the term is often used in conjunction with secure coding and security by design, both of which can rely on proofs to show the security of a particular approach. As with the cryptographic setting, this involves an attacker model and a model of the system. For example, code can be verified to match the intended functionality, described by a model: this can be done through static checking. These techniques are sometimes used for evaluating products (see Common Criteria ): the security here depends not only on the correctness of the attacker model, but also on the model of the code.

Finally, the term provable security is sometimes used by sellers of security software that are attempting to sell security products like firewalls, antivirus software and intrusion detection systems. As these products are typically not subject to scrutiny, many security researchers consider this type of claim to be selling snakeoil.

In cryptography

In cryptography, a system has provable security if its security requirements can be stated formally in an adversarial model, as opposed to heuristically, with clear assumptions that the adversary has access to the system as well as enough computational resources. The proof of security (called a "reduction") is that these security requirements are met provided the assumptions about the adversary's access to the system are satisfied and some clearly stated assumptions about the hardness of certain computational tasks hold. An early example of such requirements and proof was given by Goldwasser and Micali for semantic security and the construction based on the quadratic residuosity problem. Some proofs of security are in given theoretical models such as the random oracle model, where real cryptographic hash functions are represented by an idealization.

There are several lines of research in provable security. One is to establish the "correct" definition of security for a given, intuitively understood task. Another is to suggest constructions and proofs based on general assumptions as much as possible, for instance the existence of a one-way function. A major open problem is to establish such proofs based on P ≠ NP, since the existence of one-way functions is not known to follow from the P ≠ NP conjecture.

Controversies

Several researchers have found mathematical fallacies in proofs that had been used to make claims about the security of important protocols. In the following partial list of such researchers, their names are followed by first a reference to the original paper with the purported proof and then a reference to the paper in which the researchers reported on flaws: V. Shoup; [1] [2] A. J. Menezes; [3] [4] A. Jha and M. Nandi; [5] [6] D. Galindo; [7] [8] T. Iwata, K. Ohashi, and K. Minematsu; [9] [10] M. Nandi; [11] [12] J.-S. Coron and D. Naccache; [13] [14] D. Chakraborty, V. Hernández-Jiménez, and P. Sarkar; [15] [16] P. Gaži and U. Maurer; [17] [18] S. A. Kakvi and E. Kiltz; [19] [20] and T. Holenstein, R. Künzler, and S. Tessaro. [21] [22]

Koblitz and Menezes have written that provable security results for important cryptographic protocols frequently have fallacies in the proofs; are often interpreted in a misleading manner, giving false assurances; typically rely upon strong assumptions that may turn out to be false; are based on unrealistic models of security; and serve to distract researchers' attention from the need for "old-fashioned" (non-mathematical) testing and analysis. Their series of papers supporting these claims [23] [24] have been controversial in the community. Among the researchers who have rejected the viewpoint of Koblitz–Menezes is Oded Goldreich, a leading theoretician and author of Foundations of Cryptography. [25] He wrote a refutation of their first paper "Another look at 'provable security'" [26] that he titled "On post-modern cryptography". Goldreich wrote: "... we point out some of the fundamental philosophical flaws that underlie the said article and some of its misconceptions regarding theoretical research in cryptography in the last quarter of a century." [27] : 1  In his essay Goldreich argued that the rigorous analysis methodology of provable security is the only one compatible with science, and that Koblitz and Menezes are "reactionary (i.e., they play to the hands of the opponents of progress)". [27] : 2 

In 2007, Koblitz published "The Uneasy Relationship Between Mathematics and Cryptography", [28] which contained some controversial statements about provable security and other topics. Researchers Oded Goldreich, Boaz Barak, Jonathan Katz, Hugo Krawczyk, and Avi Wigderson wrote letters responding to Koblitz's article, which were published in the November 2007 and January 2008 issues of the journal. [29] [30] Katz, who is coauthor of a highly regarded cryptography textbook, [31] called Koblitz's article "snobbery at its purest"; [29] : 1455  and Wigderson, who is a permanent member of the Institute for Advanced Study in Princeton, accused Koblitz of "slander". [30] : 7 

Ivan Damgård later wrote a position paper at ICALP 2007 on the technical issues, [32] and it was recommended by Scott Aaronson as a good in-depth analysis. [33] Brian Snow, former Technical Director of the Information Assurance Directorate of the U.S. National Security Agency, recommended the Koblitz-Menezes paper "The brave new world of bodacious assumptions in cryptography" [34] to the audience at the RSA Conference 2010 Cryptographers Panel. [35]

Practice-oriented provable security

Classical provable security primarily aimed at studying the relationship between asymptotically defined objects. Instead, practice-oriented provable security is concerned with concrete objects of cryptographic practice, such as hash functions, block ciphers, and protocols as they are deployed and used. [36] Practice oriented provable security uses concrete security to analyse practical constructions with fixed key sizes. "Exact security" or "concrete security" is the name given to provable security reductions where one quantifies security by computing precise bounds on computational effort, rather than an asymptotic bound which is guaranteed to hold for "sufficiently large" values of the security parameter.

Related Research Articles

<span class="mw-page-title-main">RIPEMD</span> Cryptographic hash function

RIPEMD is a family of cryptographic hash functions developed in 1992 and 1996. There are five functions in the family: RIPEMD, RIPEMD-128, RIPEMD-160, RIPEMD-256, and RIPEMD-320, of which RIPEMD-160 is the most common.

In cryptography, a random oracle is an oracle that responds to every unique query with a (truly) random response chosen uniformly from its output domain. If a query is repeated, it responds the same way every time that query is submitted.

<span class="mw-page-title-main">DES-X</span> Block cipher

In cryptography, DES-X is a variant on the DES symmetric-key block cipher intended to increase the complexity of a brute-force attack. The technique used to increase the complexity is called key whitening.

In cryptography, the strong RSA assumption states that the RSA problem is intractable even when the solver is allowed to choose the public exponent e (for e ≥ 3). More specifically, given a modulus N of unknown factorization, and a ciphertext C, it is infeasible to find any pair (M, e) such that C ≡ M e mod N.

Kleptography is the study of stealing information securely and subliminally. The term was introduced by Adam Young and Moti Yung in the Proceedings of Advances in Cryptology – Crypto '96. Kleptography is a subfield of cryptovirology and is a natural extension of the theory of subliminal channels that was pioneered by Gus Simmons while at Sandia National Laboratory. A kleptographic backdoor is synonymously referred to as an asymmetric backdoor. Kleptography encompasses secure and covert communications through cryptosystems and cryptographic protocols. This is reminiscent of, but not the same as steganography that studies covert communications through graphics, video, digital audio data, and so forth.

<span class="mw-page-title-main">Serge Vaudenay</span> French cryptographer

Serge Vaudenay is a French cryptographer and professor, director of the Communications Systems Section at the École Polytechnique Fédérale de Lausanne

In cryptography, a password-authenticated key agreement method is an interactive method for two or more parties to establish cryptographic keys based on one or more party's knowledge of a password.

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. It quantifies the security of a cryptosystem by bounding the probability of success for an adversary running for a fixed amount of time. Security proofs with precise analyses are referred to as concrete.

The Diffie–Hellman problem (DHP) is a mathematical problem first proposed by Whitfield Diffie and Martin Hellman in the context of cryptography. The motivation for this problem is that many security systems use one-way functions: mathematical operations that are fast to compute, but hard to reverse. For example, they enable encrypting a message, but reversing the encryption is difficult. If solving the DHP were easy, these systems would be easily broken.

A group signature scheme is a method for allowing a member of a group to anonymously sign a message on behalf of the group. The concept was first introduced by David Chaum and Eugene van Heyst in 1991. For example, a group signature scheme could be used by an employee of a large company where it is sufficient for a verifier to know a message was signed by an employee, but not which particular employee signed it. Another application is for keycard access to restricted areas where it is inappropriate to track individual employee's movements, but necessary to secure areas to only employees in the group.

Alfred Menezes is co-author of several books on cryptography, including the Handbook of Applied Cryptography, and is a professor of mathematics at the University of Waterloo in Canada.

Digital credentials are the digital equivalent of paper-based credentials. Just as a paper-based credential could be a passport, a driver's license, a membership certificate or some kind of ticket to obtain some service, such as a cinema ticket or a public transport ticket, a digital credential is a proof of qualification, competence, or clearance that is attached to a person. Also, digital credentials prove something about their owner. Both types of credentials may contain personal information such as the person's name, birthplace, birthdate, and/or biometric information such as a picture or a finger print.

Secure two-party computation (2PC) a.k.a. Secure function evaluation is sub-problem of secure multi-party computation (MPC) that has received special attention by researchers because of its close relation to many cryptographic tasks. The goal of 2PC is to create a generic protocol that allows two parties to jointly compute an arbitrary function on their inputs without sharing the value of their inputs with the opposing party. One of the most well known examples of 2PC is Yao's Millionaires' problem, in which two parties, Alice and Bob, are millionaires who wish to determine who is wealthier without revealing their wealth. Formally, Alice has wealth , Bob has wealth , and they wish to compute without revealing the values or .

Non-interactive zero-knowledge proofs are cryptographic primitives, where information between a prover and a verifier can be authenticated by the prover, without revealing any of the specific information beyond the validity of the statement itself. This function of encryption makes direct communication between the prover and verifier unnecessary, effectively removing any intermediaries. The core trustless cryptography "proofing" involves a hash function generation of a random number, constrained within mathematical parameters determined by the prover and verifier.

In cryptography, the Fiat–Shamir heuristic is a technique for taking an interactive proof of knowledge and creating a digital signature based on it. This way, some fact can be publicly proven without revealing underlying information. The technique is due to Amos Fiat and Adi Shamir (1986). For the method to work, the original interactive proof must have the property of being public-coin, i.e. verifier's random coins are made public throughout the proof protocol.

In cryptography, server-based signatures are digital signatures in which a publicly available server participates in the signature creation process. This is in contrast to conventional digital signatures that are based on public-key cryptography and public-key infrastructure. With that, they assume that signers use their personal trusted computing bases for generating signatures without any communication with servers.

<span class="mw-page-title-main">Amit Sahai</span> American cryptographer (born 1974)

Amit Sahai is an American computer scientist. He is a professor of computer science at UCLA and the director of the Center for Encrypted Functionalities.

Dmitry Khovratovich is a cryptographer, currently a Lead Cryptographer for the Dusk Network, researcher for the Ethereum Foundation, and member of the International Association for Cryptologic Research. He developed, together with Alex Biryukov, the Equihash proof-of-work algorithm which is currently being used as consensus mechanism for the Zcash cryptocurrency, and the Argon2 key derivation function, which won the Password Hashing Competition in July 2015.

Brent R. Waters is an American computer scientist, specializing in cryptography and computer security. He is currently a professor of Computer Science at the University of Texas at Austin.

<span class="mw-page-title-main">Orr Dunkelman</span> Israeli cryptographer and cryptanalyst

Orr Dunkelman is an Israeli cryptographer and cryptanalyst, currently a professor at the University of Haifa Computer Science department. Dunkelman is a co-director of the Center for Cyber Law & Privacy at the University of Haifa and a co-founder of Privacy Israel, an Israeli NGO for promoting privacy in Israel.

References

  1. ↑ Bellare, Mihir; Rogaway, Phillip (1995). "Optimal asymmetric encryption". Advances in Cryptology — EUROCRYPT'94. Lecture Notes in Computer Science. Vol. 950. pp. 92–111. doi: 10.1007/BFb0053428 . ISBN   978-3-540-60176-0.
  2. ↑ Shoup, Victor (2002), "OAEP reconsidered", Journal of Cryptology, 15 (4): 223–249, doi: 10.1007/s00145-002-0133-9 , S2CID   26919974
  3. ↑ Krawczyk, Hugo (2005). "HMQV: A High-Performance Secure Diffie-Hellman Protocol". Advances in Cryptology – CRYPTO 2005. Lecture Notes in Computer Science. Vol. 3621. pp. 546–566. doi: 10.1007/11535218_33 . ISBN   978-3-540-28114-6.
  4. ↑ Menezes, Alfred J. (2007), "Another look at HMQV", Journal of Mathematical Cryptology, 1: 47–64, doi: 10.1515/JMC.2007.004 , S2CID   15540513
  5. ↑ Bellare, Mihir; Pietrzak, Krzysztof; Rogaway, Phillip (2005). "Improved Security Analyses for CBC MACs". Advances in Cryptology – CRYPTO 2005. Lecture Notes in Computer Science. Vol. 3621. pp. 527–545. doi: 10.1007/11535218_32 . ISBN   978-3-540-28114-6.; and Pietrzak, Krzysztof (2006), "A Tight Bound for EMAC", Automata, Languages and Programming, Lecture Notes in Computer Science, vol. 4052, pp. 168–179, doi:10.1007/11787006_15, ISBN   978-3-540-35907-4
  6. ↑ Jha, Ashwin; Nandi, Mridul (2016), "Revisiting structure graphs: Applications to CBC-MAC and EMAC", Journal of Mathematical Cryptology, 10 (3–4): 157–180, doi:10.1515/jmc-2016-0030, S2CID   33121117
  7. ↑ Boneh, Dan; Franklin, Matthew (2003), "Identity-based encryption from the Weil pairing", SIAM Journal on Computing, 32 (3): 586–615, doi:10.1137/S0097539701398521
  8. ↑ Galindo, David (2005), "Boneh-Franklin Identity Based Encryption Revisited", Automata, Languages and Programming, Lecture Notes in Computer Science, vol. 3580, pp.  791–802, doi:10.1007/11523468_64, hdl: 2066/33216 , ISBN   978-3-540-27580-0, S2CID   605011
  9. ↑ McGrew, David A.; Viega, John (2004), "The Security and Performance of the Galois/Counter Mode (GCM) of Operation", Progress in Cryptology - INDOCRYPT 2004, Lecture Notes in Computer Science, vol. 3348, pp. 343–355, doi:10.1007/978-3-540-30556-9_27, ISBN   978-3-540-24130-0
  10. ↑ Iwata, Tetsu; Ohashi, Keisuke; Minematsu, Kazuhiko (2012). "Breaking and Repairing GCM Security Proofs". Advances in Cryptology – CRYPTO 2012. Lecture Notes in Computer Science. Vol. 7417. pp. 31–49. doi: 10.1007/978-3-642-32009-5_3 . ISBN   978-3-642-32008-8.
  11. ↑ Ristenpart, Thomas; Rogaway, Phillip (2007), "How to Enrich the Message Space of a Cipher", Fast Software Encryption, Lecture Notes in Computer Science, vol. 4593, pp. 101–118, doi: 10.1007/978-3-540-74619-5_7 , ISBN   978-3-540-74617-1
  12. ↑ Nandi, Mridul (2014). "XLS is Not a Strong Pseudorandom Permutation". Advances in Cryptology – ASIACRYPT 2014. Lecture Notes in Computer Science. Vol. 8874. pp. 478–490. doi: 10.1007/978-3-662-45611-8_25 . ISBN   978-3-662-45607-1.
  13. ↑ Bellare, Mihir; Garray, Juan A.; Rabin, Tal (1998). "Fast batch verification for modular exponentiation and digital signatures". Advances in Cryptology — EUROCRYPT'98. Lecture Notes in Computer Science. Vol. 1403. pp. 236–250. doi: 10.1007/BFb0054130 . ISBN   978-3-540-64518-4.
  14. ↑ Coron, Jean-Sébastien; Naccache, David (1999), Public Key Cryptography, Lecture Notes in Computer Science, vol. 1560, pp. 197–203, doi:10.1007/3-540-49162-7, ISBN   978-3-540-65644-9, S2CID   11711093
  15. ↑ McGrew, David A.; Fluhrer, Scott R. (2007), "The Security of the Extended Codebook (XCB) Mode of Operation", Selected Areas in Cryptography, Lecture Notes in Computer Science, vol. 4876, pp. 311–327, doi: 10.1007/978-3-540-77360-3_20 , ISBN   978-3-540-77359-7
  16. ↑ Chakraborty, Debrup; Hernández-Jiménez, Vicente; Sarkar, Palash (2015), "Another look at XCB", Cryptography and Communications, 7 (4): 439–468, doi:10.1007/s12095-015-0127-8, S2CID   17251595
  17. ↑ Bellare, Mihir; Rogaway, Phillip (2006). "The Security of Triple Encryption and a Framework for Code-Based Game-Playing Proofs". Advances in Cryptology - EUROCRYPT 2006. Lecture Notes in Computer Science. Vol. 4004. pp. 409–426. doi: 10.1007/11761679_25 . ISBN   978-3-540-34546-6.
  18. ↑ Gaži, Peter; Maurer, Ueli (2009). "Cascade Encryption Revisited". Advances in Cryptology – ASIACRYPT 2009. Lecture Notes in Computer Science. Vol. 5912. pp. 37–51. doi: 10.1007/978-3-642-10366-7_3 . ISBN   978-3-642-10365-0.
  19. ↑ Coron, Jean-Sébastien (2002). "Optimal Security Proofs for PSS and Other Signature Schemes". Advances in Cryptology — EUROCRYPT 2002. Lecture Notes in Computer Science. Vol. 2332. pp. 272–287. doi: 10.1007/3-540-46035-7_18 . ISBN   978-3-540-43553-2.
  20. ↑ Kakvi, Saqib A.; Kiltz, Eike (2012). "Optimal Security Proofs for Full Domain Hash, Revisited". Advances in Cryptology – EUROCRYPT 2012. Lecture Notes in Computer Science. Vol. 7237. pp. 537–553. doi: 10.1007/978-3-642-29011-4_32 . ISBN   978-3-642-29010-7.
  21. ↑ Coron, Jean-Sébastien; Patarin, Jacques; Seurin, Yannick (2008). "The Random Oracle Model and the Ideal Cipher Model Are Equivalent". Advances in Cryptology – CRYPTO 2008. Lecture Notes in Computer Science. Vol. 5157. pp. 1–20. doi: 10.1007/978-3-540-85174-5_1 . ISBN   978-3-540-85173-8.
  22. ↑ Holenstein, Thomas; Künzler, Robin; Tessaro, Stefano (2011), "The equivalence of the random oracle model and the ideal cipher model, revisited", Proceedings of the forty-third annual ACM symposium on Theory of computing, pp. 89–98, arXiv: 1011.1264 , doi:10.1145/1993636.1993650, ISBN   9781450306911, S2CID   2960550 {{citation}}: CS1 maint: date and year (link)
  23. ↑ Koblitz, Neal; Menezes, Alfred (2019). "Critical perspectives on provable security: Fifteen years of 'Another look' papers". Advances in Mathematics of Communications. 13 (4): 517–558. doi: 10.3934/amc.2019034 .
  24. ↑ These papers are all available at "Another look at provable security" . Retrieved 12 April 2018.
  25. ↑ Goldreich, Oded (2003). Foundations of Cryptography. Cambridge University Press. ISBN   9780521791724.
  26. ↑ Koblitz, Neal; Menezes, Alfred J. (2007), "Another look at "provable security"", Journal of Cryptology, 20 (1): 3–37, doi: 10.1007/s00145-005-0432-z , S2CID   7601573
  27. 1 2 "On post-modern cryptography" . Retrieved 12 April 2018.
  28. ↑ Koblitz, Neal (2007), "The uneasy relationship between mathematics and cryptography" (PDF), Notices Amer. Math. Soc., 54 (8): 972–979
  29. 1 2 "Letters to the Editor" (PDF), Notices Amer. Math. Soc., 54 (12): 1454–1455, 2007
  30. 1 2 "Letters to the Editor" (PDF), Notices Amer. Math. Soc., 55 (1): 6–7, 2008
  31. ↑ Katz, Jonathan; Lindell, Yehuda (2008). Introduction to Modern Cryptography. Chapman & Hall/CRC. ISBN   9781584885511.
  32. ↑ Damgård, I. (2007). "A "proof-reading" of Some Issues in Cryptography". Automata, Languages and Programming. Lecture Notes in Computer Science. Vol. 4596. pp. 2–11. doi:10.1007/978-3-540-73420-8_2. ISBN   978-3-540-73419-2.  preprint {{cite book}}: External link in |postscript= (help)CS1 maint: postscript (link)
  33. ↑ "Shtetl-Optimized". scottaaronson.com. September 2007.
  34. ↑ Koblitz, Neal; Menezes, Alfred J. (2010), "The brave new world of bodacious assumptions in cryptography" (PDF), Notices Amer. Math. Soc., 57: 357–365
  35. ↑ "RSA Conference 2010 USA: The Cryptographers Panel". YouTube . Archived from the original on 2021-12-22. Retrieved 9 April 2018.
  36. ↑ Rogaway, Phillip. "Practice-Oriented Provable Security and the Social Construction of Cryptography". Unpublished Essay Corresponding to an Invited Talk at EUROCRYPT 2009. May 6, 2009 preprint {{cite journal}}: External link in |postscript= (help)CS1 maint: postscript (link)
This page is based on this Wikipedia article
Text is available under the CC BY-SA 4.0 license; additional terms may apply.
Images, videos and audio are available under their respective licenses.