One-Way Functions and Trapdoors

The padlock story asked for arithmetic that is easy forwards and hard backwards. This note makes that precise, in two steps. First the easy-forwards-hard-backwards part on its own, which is called a one-way function. Then the escape hatch that lets exactly one person go backwards anyway, which is called a trapdoor.

Before either, we need to be honest about what "easy" and "hard" mean, because in cryptography they are not opinions.

01.What "easy" and "hard" actually mean

Take a task whose input is a number with $b$ binary digits, and count how many basic arithmetic steps a computer needs to finish it.

If the count grows like $b$, or $b^2$, or $b^3$, the task is called polynomial time, and cryptographers call it easy. The reason is that doubling the input size multiplies the work by a fixed modest factor. For $b^2$, doubling $b$ makes the work four times larger. Four times a millisecond is still nothing.

If the count grows like $2^b$, the task is called exponential time, and cryptographers call it infeasible. Here adding a single bit to the input doubles the work. That sounds similar to the previous paragraph and it is not remotely similar.

Put numbers on it. Suppose a machine does one billion steps per second, which is roughly one modern processor core.

At $b = 40$, an exponential task takes $2^{40} \approx 1.1 \times 10^{12}$ steps, about eighteen minutes. Uncomfortable but fine.

At $b = 60$, it takes $2^{60} \approx 1.15 \times 10^{18}$ steps, about thirty-six years.

At $b = 80$, it takes $2^{80} \approx 1.2 \times 10^{24}$ steps, about thirty-eight million years.

At $b = 128$, it takes $2^{128} \approx 3.4 \times 10^{38}$ steps. If you had a billion such machines, running since the formation of the Earth, you would have completed a vanishing fraction of one percent.

That last line is why cryptographers speak of a "128-bit security level" as comfortable. It does not mean nobody has tried. It means that trying is not a strategy that finishes.

So when this chapter says a direction is infeasible, it is a statement about how the cost curve bends, not about anybody's budget. And when it says a direction is easy, it means the cost curve is flat enough that a phone does it while you wait.

One caution that matters for the rest of the chapter. Between polynomial and exponential there is a middle band called subexponential, which grows faster than any polynomial but slower than $2^b$. The best known attacks on the two classical problems live in that band. They are far too slow to be a threat at the sizes actually deployed, but they are the reason RSA keys have to be thousands of bits long while elliptic-curve keys can be a few hundred.

02.One-way functions

Set the key aside and look at a padlock lying on a table. Even with no key anywhere in the picture it already has a striking asymmetry. Snapping it shut takes a moment and no skill. Getting it open again without the key takes a saw and a long afternoon.

A function with the same asymmetry is called a one-way function: a function $f$ that is easy to compute and infeasibly hard to invert. Inverting means being handed a value $y$ and finding any input $x$ at all with $f(x) = y$.

Two everyday pictures carry the idea well. Stirring a tin of blue paint into a tin of yellow paint is a few seconds of work, and separating the green result back into the original two is not a harder version of the same job, it is a different job that nobody knows how to do. Dropping a wine glass is easy. Reassembling the pieces into a glass is not.

Here is something that surprises people the first time they hear it. Nobody has proved that one-way functions exist. Proving it would settle one of the deepest open questions in computer science. What we have instead is a small number of candidate functions that many clever people have attacked for fifty years without success. Cryptography runs on that evidence. It is strong evidence, and it is not a proof, and the distinction is exactly why this chapter has to be written at all: a candidate can fail, and Shor's algorithm is the story of two of them failing at once.

03.Why one-wayness alone is useless

Now put the key back on the table, and notice that a pure one-way function cannot be a cryptosystem.

If inverting $f$ is infeasible for everybody, then it is infeasible for Bob. Alice encrypts by computing $y = f(x)$, sends $y$, and Bob stares at a value he cannot invert either. The message is now hidden from its intended recipient just as thoroughly as from Eve. Perfect secrecy, zero communication.

What is needed is an asymmetry among people, not just among directions. Bob must be able to go backwards. Everybody else must not.

04.Trapdoors

A trapdoor one-way function is a one-way function built in a special way, so that its builder retains a piece of information that makes inversion easy again. That piece of information is the trapdoor.

The name is the right picture. A trapdoor in a stage floor is invisible and immovable if you do not know it is there. If you know where it is and have the catch, you go straight through.

In cryptographic language the trapdoor is the private key. Bob does not find $f$ lying around. He constructs it, and the construction leaves him holding a secret. He publishes a description of $f$, which is his public key, and keeps the secret.

Mapping the padlock picture onto this, one piece at a time. Computing $f(x)$ is snapping the padlock shut. The output $y = f(x)$ is the locked box. The public description of $f$ is the padlock everyone can obtain. The secret that inverts $f$ is the key in Bob's safe.

05.The contract, in three clauses

Collecting everything, a trapdoor one-way function is a function $f$ together with a secret $sk$ satisfying three properties.

1. Easy forward. Given $x$, computing $y = f(x)$ runs in polynomial time.
2. Hard backward without the secret. Given only $y$, finding any $x$ with $f(x) = y$ is infeasible. No known algorithm does it in less than subexponential time.
3. Easy backward with the secret. Given $y$ together with $sk$, recovering $x$ runs in polynomial time again.

Every public-key cryptosystem ever deployed is a recipe for building an object satisfying those three clauses out of some hard arithmetic problem. RSA is one. Diffie-Hellman key exchange is one. Elliptic-curve signatures are one. ML-KEM and ML-DSA, the post-quantum standards this book is heading towards, are two more.

The real schemes wrap the function in padding, randomness and integrity checks, and those wrappings are not decoration. Textbook RSA without padding is genuinely broken in practice. But the wrapping is not what carries the weight. Clause 2 is what carries the weight. If clause 2 fails, no amount of padding saves the scheme.

That is precisely what a quantum computer does to the two problems in the next two notes. It does not find a flaw in the padding. It makes clause 2 false.