One-Way Functions and Trapdoors

Symptom

You are asked, by someone reasonable, why they should believe their bank transfers are secure. You say the encryption cannot be broken. They ask how you know. You say the underlying problem is hard — factoring, discrete log, whatever the scheme uses.

Then they ask how you know that, and you find you cannot answer. Nobody has proved factoring is hard. Nobody has proved any of it. The honest answer is that a lot of clever people have tried for decades and failed, which is an argument from evidence and not from proof.

You reach for P vs NP as a fallback: surely if $\text{P} \neq \text{NP}$, then these problems are hard and everything is fine. It is not fine. That implication is false in a way that is worth understanding precisely, because it is the gap where all of modern cryptography actually lives.

Statement

One-way function. $f$ is one-way if it is computable in polynomial time, but for every probabilistic polynomial-time algorithm $A$, the probability that $A$ inverts $f$ on a random input is negligible:

$$\Pr_{x \gets \{0,1\}^n}\big[A(f(x)) \in f^{-1}(f(x))\big] < \frac{1}{p(n)}$$

for every polynomial $p$ and sufficiently large $n$.

Trapdoor function. A one-way function with auxiliary information $t$ that makes inversion easy. Hard for everyone; easy for whoever holds $t$.

The status. Whether one-way functions exist is open. Their existence implies $\text{P} \neq \text{NP}$. The converse is not known and is widely believed to need much more.

The two clauses that carry all the weight are on a random input and for every polynomial-time algorithm. $\text{P} \neq \text{NP}$ is a worst-case statement: it says some instances are hard. Cryptography needs almost every instance to be hard, for randomly generated keys, which is an average-case statement and a strictly stronger demand.

Argument

Why worst-case hardness is not enough, concretely. Consider a hypothetical world where SAT requires exponential time but only on a vanishingly thin set of instances, and a polynomial algorithm solves 99.9999% of instances drawn from any natural distribution. That world has $\text{P} \neq \text{NP}$ and no useful cryptography whatsoever, because your key generator would have to find the hard instances and it has no way to do so.

This is not a contrived scenario. Graph 3-colouring, knapsack, and many NP-complete problems are easy on average under natural distributions, and several proposed cryptosystems died exactly this way. The Merkle–Hellman knapsack cryptosystem was broken by Shamir in 1982 using lattice reduction, despite subset-sum being NP-complete, because the instances the key generator produced had special structure. NP-completeness was never the guarantee people took it for.

Impagliazzo’s five worlds, which is the right map. Each world is consistent with what is currently known.

Pessiland is the instructive one. In Pessiland there are hard problems whose solutions you cannot find, and yet no cryptography, because generating a hard instance together with its solution is a separate ability from generating a hard instance. A key generator must produce a puzzle it already knows the answer to. Hardness alone does not give you that.

We believe we live in Cryptomania, on evidence rather than proof.

What one-way functions buy, which is a remarkable amount. Nearly all of symmetric cryptography is equivalent to their existence — not merely implied by it. From a one-way function you can build:

• pseudorandom generators (Håstad, Impagliazzo, Levin, Luby),
• pseudorandom functions from PRGs (Goldreich, Goldwasser, Micali),
• symmetric encryption, MACs, digital signatures, commitment schemes, and zero-knowledge proofs for all of NP.

That chain is one of the great results of theoretical cryptography: a single minimal assumption yields the entire symmetric toolkit, and each implication is a constructive reduction rather than an existence claim. Minicrypt is a very comfortable world. What it lacks is key agreement between strangers.

Why public-key needs strictly more. Symmetric crypto only needs a function that is hard to invert. Public-key needs structure: a way to publish something that lets anyone encrypt while only you can decrypt. Impagliazzo and Rudich showed there is no black-box construction of key agreement from one-way functions, which is strong evidence that Minicrypt and Cryptomania are genuinely different worlds and that RSA-style cryptography rests on a heavier assumption than AES-style cryptography does.

The candidates, and what each is actually assuming.

Factoring underpins RSA. Best known classical algorithm is the general number field sieve at sub-exponential $\exp(O((\log N)^{1/3}(\log\log N)^{2/3}))$, which is why RSA keys must be so large — RSA-2048 is roughly comparable to a 112-bit symmetric key, not a 2048-bit one. Discrete log in finite fields and on elliptic curves underpins Diffie–Hellman, DSA, and ECDSA; elliptic curves have no known sub-exponential attack, which is why a 256-bit curve gives about 128-bit security and keys stay small.

Both fall to Shor’s algorithm on a sufficiently large quantum computer, in polynomial time. That is not a distant curiosity, it is the reason for the entire post-quantum standardization effort: NIST selected ML-KEM (Kyber) and ML-DSA (Dilithium) in 2024, both based on lattice problems, specifically Learning With Errors, which has a worst-case-to-average-case reduction — one of the very few assumptions in cryptography where average-case hardness follows from worst-case hardness of a related lattice problem. That reduction is the strongest theoretical foundation available in deployed cryptography, and it is still not a proof.

Why nobody can prove any of this. Proving one-way functions exist implies $\text{P} \neq \text{NP}$, so it is at least that hard. Worse, the known barriers (T030) apply: relativization and natural proofs both obstruct the available techniques, and Razborov and Rudich’s natural proofs barrier is itself stated in terms of the existence of pseudorandom functions. The assumption that makes cryptography possible is part of what makes proving it possible so difficult, which is an unusually direct form of circularity.

Forbids

Deducing practical security from $\text{P} \neq \text{NP}$. Worst-case hardness does not give average-case hardness, and cryptography needs the latter. Heuristica and Pessiland are both consistent with $\text{P} \neq \text{NP}$ and both have no cryptography.

Basing a cryptosystem on NP-completeness alone. Knapsack was the object lesson. NP-hardness of the underlying problem says nothing about the instances your key generator produces.

Unconditional security from short keys. That is Shannon (T075), and it stands regardless of complexity assumptions.

Proving a scheme secure without an assumption. Every security proof in modern cryptography is a reduction: if this problem is hard, then this scheme is secure. The conditional is not removable with current techniques.

Does not forbid

It does not mean cryptography is unjustified, which is the nihilistic misreading. The assumptions have survived enormous concentrated attack. Factoring has been studied since antiquity and seriously since 1977; RSA-250 was factored in 2020 with about 2700 core-years, exactly in line with predicted difficulty. Prediction accuracy over decades is real evidence even without proof, and it is the same kind of evidence physics runs on.

It does not mean a break is catastrophic and unrecoverable. Systems are built for cryptographic agility. TLS negotiates cipher suites; SSH, Signal, and WireGuard have versioned protocols; the migration off SHA-1 and off RC4 both happened at internet scale. The current post-quantum rollout — Chrome and Cloudflare have shipped hybrid X25519+ML-KEM key agreement — is the mechanism working ahead of the threat.

It does not require the same assumption everywhere. Diversity is deliberate. Signatures based on hash functions alone — SPHINCS+, also standardized by NIST — rest only on the security of a hash function, so they survive even a break of all number-theoretic assumptions, at the cost of large signatures.

It does not mean quantum computers break everything. Shor breaks factoring and discrete log. Grover only halves symmetric security, so AES-256 remains at 128-bit strength, and hash-based and lattice-based constructions are believed secure. The response is migration, not abandonment.

It does not mean provable security is worthless. The reductions are the whole value: they move all the trust into one clearly stated assumption that can be attacked directly. A scheme reduced to LWE fails only if LWE fails, which is a far better position than a scheme with no proof and many independent ways to break.

Boundary

• Existence is open. All of it. One-way functions may not exist.
• Asymptotic definitions. “Negligible” and “polynomial” say nothing about concrete parameters; a scheme secure asymptotically may be broken at 512 bits.
• Reductions have loss factors. A tight reduction and a loose one give very different real-world key sizes for the same claim.
• The model excludes the implementation. Timing, power, cache, and fault side channels break provably-secure schemes routinely, and Spectre-class attacks broke constant-time assumptions at the microarchitectural level.
• Quantum changes the landscape unevenly. The problem is not that hardness vanishes but that specific structured problems do.

The claim to carry: cryptography is an engineering discipline built on an unproven conjecture, and it works because the conjecture has been attacked harder than almost anything else in mathematics. Knowing which world you are assuming you live in is the difference between using cryptography and believing in it.

Read next