One-Way Functions: The Bet All Cryptography Makes

A one-way function is easy to compute and infeasible to reverse. Multiply two large primes together and the answer lands instantly; hand that answer to someone and ask which primes made it, and they are stuck. Nobody has ever proved that such a function exists. Every padlock icon in your browser bets that they do.

Multiplying is easy. Factoring is not.

Take 6,701 and 6,047. Their product, 40,520,947, takes a computer well under a microsecond. Now go the other way. Start from 40,520,947 with no hint about where it came from, and finding the two primes means grinding through candidate divisors until one divides cleanly. On numbers that small a browser still wins in a blink. Add digits and the asymmetry opens up fast.

The demo above lets you feel the gap on your own machine. Multiplication is so quick that a single one cannot be timed against the browser’s clock at all, so the page runs two hundred thousand and divides. Then it turns round and factors the same number by trial division. Pick 12-digit primes and the search gives up after thirty seconds, a few million candidates into the several hundred billion it needed, while the answer sits on the screen above it in plain sight.

Cryptography textbooks reach for paint here. Stir blue into yellow and you get green in seconds; separating the green back out is another matter. The analogy is useful and slightly dishonest. Paint resists unmixing for thermodynamic reasons that are settled physics. Factoring might be easy, and we might simply be missing the trick. That difference is the whole subject.

What “one-way” actually means

Easy to compute is the simple half: some algorithm produces f(x) from x in polynomial time. The hard half is where loose definitions go wrong. It is not enough that inverting f is difficult in the worst case, because a cipher whose keys are drawn at random gains nothing from a few nasty instances buried in the input space. What cryptography needs is a function that resists inversion on typical inputs: pick x at random, compute y = f(x), hand y to any efficient algorithm you like, and its chance of finding any preimage of y must be negligible.

Average-case hardness is the interesting bit, and it is where most explanations go wrong. Plenty of problems are brutal in the worst case and trivial in practice. Linear programming was famously like that for decades under the simplex method. A one-way function has to be hard almost everywhere, on instances that are cheap to generate at random, which is a much heavier demand than “hard sometimes”.

Trapdoor functions: the shortcut that makes public keys possible

A pure one-way function is a locked door with no key: fine for hashing passwords, useless for sending secrets. If nobody can invert the function, the intended recipient cannot either.

What public-key cryptography needs is a trapdoor function, a one-way function with a secret shortcut. Everyone can compute it forwards. Reversing it is infeasible unless you hold one extra piece of information, the trapdoor, at which point going backwards is as cheap as going forwards.

Whitfield Diffie and Martin Hellman set out the idea in their 1976 paper New Directions in Cryptography, which named trapdoor one-way functions and showed what such a thing would buy: encryption without a shared secret, and signatures anyone could check. Their paper delivered a key exchange protocol built on the discrete logarithm problem. It did not deliver a trapdoor cipher. They described the shape of the missing object and left it open.

Two years later Ron Rivest, Adi Shamir and Leonard Adleman filled the gap. RSA, published in the Communications of the ACM in 1978, works like this. Pick two large primes p and q and publish only their product N, along with an exponent e. Anyone can encrypt a message m as m^e mod N. Decrypting needs a matching exponent d, and computing d needs p and q. Everyone walks through the door. Only the holder of the factors walks back.

That asymmetry is what “public key” means, and it is why the two terms are worth keeping apart. Ordinary one-way functions are enough for symmetric encryption, pseudorandom generators, commitments and digital signatures. Public-key encryption needs the trapdoor, a strictly stronger assumption.

RSA factoring: what the whole system rests on

Factor N into p and q and every key derived from it falls out. Strictly, RSA rests on a slightly weaker-looking problem, computing e-th roots modulo N, which nobody has proved is as hard as factoring. In practice factoring is the attack everyone measures.

RSA Security ran the RSA Factoring Challenge for years, publishing moduli with cash prizes attached and letting the world try. The prizes were withdrawn in 2007, but the numbers are still there and researchers still work on them. The current record is RSA-250: 250 decimal digits, 829 bits, factored on 28 February 2020 by Fabrice Boudot, Pierrick Gaudry, Aurore Guillevic, Nadia Heninger, Emmanuel Thomé and Paul Zimmermann. It took about 2,700 core-years spread across thousands of machines. RSA-260 has not fallen.

The pace tells you more than the record does. RSA-768, at 232 digits, went down in December 2009. Eleven years of algorithmic work and faster hardware bought roughly sixty more bits. Extrapolate that gently and 1024-bit RSA looks uncomfortable rather than safe, which is why it has been pushed out of new deployments. Today 2048 bits is the floor, and 3072 or 4096 is the recommendation for secrets that must survive into the 2030s.

Note what the record does not say. Nobody factored RSA-250 by trial division. The general number field sieve is far cleverer than that, which is why the last panel of the demo above refuses to take its own benchmark seriously. Your browser will happily report that trial-dividing a 2048-bit modulus takes something like 10^292 years. The real figure, using the best algorithm anyone has, is enormously smaller and still out of reach. Quoting the toy number as though it were the true one is the overclaiming that makes cryptography sound like magic. The demo shows the shape of the problem, not its size. Breaking Bitcoin runs the same arithmetic for digital currencies.

Why P versus NP decides half the question

If P equals NP, one-way functions cannot exist. Inverting f is a search problem whose answers are trivially checkable: hand me a candidate x, and I compute f(x) and compare. That puts inversion inside NP, so a world where P equals NP is a world where preimages are found as fast as they are verified, and every cipher, signature scheme and commitment protocol we have unwinds. This is the concrete version of the doom set out on our P versus NP page. It runs the other way too: proving any function one-way would prove P is not equal to NP, which is why nobody expects a proof soon.

The converse does not follow, and the reason repays a slow reading. Suppose P is not equal to NP. That is a statement about worst cases: some problem in NP has instances no polynomial algorithm handles. It says nothing about whether hard instances are common, or whether you can generate them on demand. A problem can be intractable on a vanishingly thin set of inputs and easy on everything you could actually sample. One-way functions need hardness on random inputs drawn from a cheaply samplable distribution, which is strictly stronger. P not equal to NP is necessary for cryptography. It is not sufficient, and closing that gap is an open problem in its own right.

Impagliazzo’s five worlds

Russell Impagliazzo laid this out in 1995 in a paper called A Personal View of Average-Case Complexity, and the picture has stuck. He described five possible worlds, exactly one of which we live in, and nobody knows which. In Algorithmica, P equals NP or something morally equivalent, and everything in NP is tractable. In Heuristica, NP problems are hard in the worst case but easy on average, so complexity theory is right and cryptography dies anyway. In Pessiland, hard-on-average problems exist but one-way functions do not, the worst of all worlds: no useful algorithms and no cryptography either. In Minicrypt, one-way functions exist but public-key encryption is impossible, leaving symmetric ciphers and signatures but no way for strangers to agree a secret. In Cryptomania, public-key cryptography works and the internet functions as advertised. Every https connection you make assumes Cryptomania. Nothing proves it.

Liu and Pass: one-way functions as a question about compression

For a long time the existence of one-way functions was tied to no particular problem, which made it an awkward thing to attack. That changed in 2020, when Yanyi Liu and Rafael Pass presented an equivalence at FOCS between one-way functions and the average-case hardness of time-bounded Kolmogorov complexity. The quantity K^t(x) is the length of the shortest program that prints x within t steps: a measure of how compressible x is under a time budget. Liu and Pass showed that for any polynomial t(n) at least (1+ε)n, one-way functions exist if and only if computing K^t is mildly hard on average, meaning every efficient algorithm fails on a noticeable fraction of random strings.

Be careful about what that buys, because it is a translation rather than an answer. Nothing here proves one-way functions exist and nothing here breaks them. What changes is the shape of the question: a vague existential claim about some function somewhere becomes a concrete question about one specific problem that mathematicians have been poking at since the 1960s. That is real progress towards a destination still out of sight.

What quantum computers actually break

Peter Shor’s 1994 algorithm factors integers and computes discrete logarithms in polynomial time on a quantum computer. Given a machine large enough to run it, RSA and Diffie-Hellman both fail, along with the elliptic curve schemes built on the same discrete logarithm structure.

That is a statement about specific trapdoors, not about one-way functions in general. Shor’s algorithm exploits the periodic structure sitting inside modular exponentiation. Hash functions offer no such structure, and the best general quantum attack, Grover’s algorithm, only takes the square root of the search space, turning 256 bits of security into 128. Lattice problems, the basis of the current post-quantum standards, are believed to resist quantum attack too. A working quantum computer would not show that one-way functions fail to exist. It would show that we picked the wrong ones, and we would pick others. Breaking Bitcoin covers what that means for digital currencies.

The oldest assumption in the field

Claude Shannon proved in 1949 that perfect secrecy is achievable, and priced it: the key must be as long as the message and can never be reused. Nobody runs the internet that way. Everything practical since has swapped that proof for an assumption, namely that certain functions run easily forwards and impossibly backwards.

Seventy years of failed attacks say the assumption is a good one. They do not say it is true. Multiplying took microseconds in the demo above; reversing it has no known fast method, and nobody has proved there isn’t one.