Security Reduction
A security reduction is the core technique of provable security: it converts an efficient attack on a cryptographic scheme into an efficient algorithm for a hard problem, proving security by contradiction.
Purpose
It builds the mathematical bridge from a security assumption to scheme security, the formal tool of provable security.
Mechanism
Given a scheme attacker A, a hard-problem solver B is constructed: B receives a problem instance, embeds it into the scheme parameters, and extracts the hard-problem solution using A’s attack capability. The reduction loss quantifies the efficiency gap between B and A.
Use cases
- Cryptographic security proofs
- Reduction-efficiency analysis
- Protocol security assessment