Provable security

From Wikipedia, the free encyclopedia

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.

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.

Some proofs of the security are in given theoretical models such as the random oracle model, where real cryptographic hash functions are represented by an idealization. '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.

Recently Koblitz and Menezes have criticized aspects of provable security in their papers Another Look at "Provable Security" and Another Look at "Provable Security". II. These views are not shared by the majority of cryptographers.^{[citation needed]} A rebuttal, titled On Post-Modern Cryptography was posted by Oded Goldreich, who argues that the rigorous analysis methodology of provable security is the only one compatible with science.

Very recently AMS published a controversial article by Koblitz titled "The Uneasy Relationship Between Mathematics and Cryptography". Several rebuttals have been written and are available here and here.