Crypto Wiki

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.

Koblitz and Menezes have criticized aspects of provable security research in their papers Another Look at "Provable Security" and Another Look at "Provable Security". II. These views have been controversial in the community. 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.

In 2007 Koblitz published "The Uneasy Relationship Between Mathematics and Cryptography" in the Notices of the American Mathematical Society. Several rebuttals have been written and are available here and here.

de:Beweisbare Sicherheit fr:Preuve de sécurité ko:안전성 증명 it:Sicurezza dimostrabile ja:証明可能安全性を持つ暗号