Provable security

This section includes a list of references, related reading, or external links, but its sources remain unclear because it lacks inline citations. Please help improve this section by introducing more precise citations. (September 2018) (Learn how and when to remove this message)

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

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 snake oil.

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.

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]

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.