Provable security

From Wikipedia, the free encyclopedia

In cryptography, a system is said to have provable security if its security requirements are stated formally in an adversarial model, as opposed to heuristically, and there is a proof (called a "reduction") that these security requirements can be met provided that some well studied cryptographic primitive (such as RSA) is secure.

The name "provable security" is somewhat misleading because, usually the proofs only establish security up to some unproven assumptions, at best, or else, some theoretical model that cannot be true in practice, such as the random oracle model.

From the perspective of theoretical computer science, the security of most cryptographic primitives is not known to be reducible to P ≠ NP (the standard hardness conjecture in computational complexity theory), and P ≠ NP itself remains unproven, so the provable security may be regarded as two steps away from a complete proof.

Nowadays, given that cryptology is a practical more than a theoretical science, it is more widely realized that provable security results for small parameters are more important than asymptotic results about parameters tending to infinity. Therefore, under the name of 'exact' or 'concrete' security are considered more valuable than mere asymptotic results, which can hide a lot under the rug.

Koblitz and Menezes discuss aspects of and issues with provable security in their papers Another Look at "Provable Security" and Another Look at "Provable Security". II.