← 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.

The honest caveat, stated plainly. "Provably secure" never means "unbreakable." It means "no easier to break than the underlying hard problem." If that problem falls, so does the scheme. The proof moves the risk; it doesn't erase it.
§1

The contrapositive machine

A reduction is an argument by contradiction. To show a scheme is at least as hard as factoring, you assume an attacker who breaks the scheme — and then use that attacker as a tool to factor. Since factoring is believed impossible-in-practice, the attacker must be too. Trace the logic below.

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

This is why the whole edifice hangs together. Each scheme reduces to a hard problem; break the scheme and you'd break the problem beneath it. The difficulty flows downhill from a small set of assumptions everyone watches closely.

  • RSAreduces tothe hardness of factoring large integers.
  • ECC · DHreduces tothe discrete logarithm problem in a group.
  • Kyber · Dilithiumreduces toworst-case lattice problems like the SVP.
A proof of security is a promise: to break me, you must first break something older and better-studied than me.
Where this touches your keys

Why anyone trusts a primitive

When a public-key scheme claims a security level, that claim is a reduction to one of the hard problems in this hall. It's also why assumptions matter more than cleverness: a scheme with a tight reduction to lattices is trusted not because it looks complex, but because its difficulty is anchored to a problem the world has failed to solve for decades.

Symmetric cryptography earns trust the other way, and the contrast is the honest end of this exhibit. There is no reduction proving AES secure — no hard problem underneath it to reduce to. What AES has instead is thirty years of the world's best cryptanalysts attacking it in public and failing to find anything close to practical. That is evidence, not proof, and it is a genuinely different currency from the arguments on this page. Both kinds of trust are load-bearing; neither is a substitute for the other.

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