← Hall of Foundations Exhibit 148 · A ≤ B
What "Provably Secure" Actually Claims

Standing on a
borrowed difficulty

Cryptographers rarely prove a scheme is hard to break. They prove something subtler and stronger: that breaking it would let you solve a problem everyone already believes is hard. Security is borrowed from a difficulty we trust — and the loan is made by a reduction.

A conditional claim. A proof names an assumption, adversary model and quantitative reduction loss. It neither proves that assumption nor licenses reversing the reduction arrow.
§1

The contrapositive machine

Suppose a precisely defined reduction could turn a successful scheme-breaker into a solver for a specified hard problem. If the transformation preserved sufficient running time and success probability, the problem's assumed hardness would bound the attacker. The animation is a hypothetical logic diagram, not an implementation or a proof that RSA inversion is equivalent to factoring.

Suppose a break exists…
Read it as a machine: feed a hard factoring instance in, wrap it as a fake scheme challenge, let the hypothetical breaker crack it, and read the factors back out. If the breaker is fast, factoring is fast — a contradiction.
§2

The chain of trust

The direction of the implication matters. A reduction using an attacker to solve a problem supports a conditional security claim. The opposite direction—using a problem solver to break a scheme—shows a possible attack but is not that security proof. A broken assumption can invalidate a proof without automatically yielding an attack on every scheme.

  • RSAknown attack directionfactoring the modulus breaks RSA. General RSA inversion is not known to be equivalent to factoring.
  • ECC · DHscheme-specific assumptionsCDH, DDH or other group assumptions, according to the protocol and security goal. A discrete-log solver is enough to break DH.
  • ML-KEM · ML-DSAmodule-lattice assumptionsspecific Module-LWE and Module-SIS-related problems and additional construction assumptions; not an equivalence to arbitrary exact SVP.
A reduction says how an attacker would imply a solver under stated conditions. It does not require an attacker to literally run that solver first.
Where this touches your keys

Why anyone trusts a primitive

Public-key security estimates combine formal definitions, conditional reductions and concrete cryptanalysis. A reduction has an attack model, parameter restrictions and a loss in time or success probability; it may not be tight. No reduction proves the underlying hardness assumption itself.

AES is supported by decades of public cryptanalysis rather than a proof from an independently established hard problem. Higher-level symmetric constructions can still have reductions to assumptions about their block cipher or hash. Both the mathematical model and practical attack evidence matter.

Foundations referenced here: One-Way Functions, Lattices & the SVP.

Sources and scope: Boneh and Shoup, A Graduate Course in Applied Cryptography, v0.6, Chapter 10; NIST FIPS 203 and FIPS 204.