Provable Security
Provable security reduces the security of a cryptographic scheme to a widely believed computationally hard problem: if a polynomial-time attacker breaks the scheme, a polynomial-time algorithm for the hard problem can be built.
Purpose
It gives cryptographic schemes mathematical security guarantees rather than heuristic analysis, the design paradigm of modern cryptography.
Mechanism
A security reduction is constructed: assuming attacker A breaks the scheme with advantage ε, algorithm B is built that uses A as a subroutine to solve the hard problem (e.g., DDH, LWE) with related advantage. Since the hard problem is assumed to have no polynomial-time solution, A cannot exist.
Use cases
- Security proofs of cryptographic schemes
- Protocol design
- Post-quantum scheme evaluation