Hardness Assumptions

The Integer Factorization Problem

The previous page argued that public-key encryption rests on a trapdoor one-way function: a map easy to evaluate, hard to invert, yet easy to invert for whoever holds a piece of secret information. That argument was deliberately abstract. It named no function and exhibited no concrete instance, because the framework does not depend on any particular one. But a framework that never produces an instance is a promissory note. Somewhere there must be a computation that is genuinely easy in one direction and genuinely hard in the other, or the whole construction is vacuous. This page examines the candidates that have actually filled that role, and the sense in which their hardness is assumed rather than proved.

The candidate with the longest history as a mathematical problem is the one every reader already knows in part. Multiplying two integers is easy, while recovering the factors from the product is, for suitably chosen integers, hard. We make the second half precise.

Two features of this problem deserve immediate emphasis, because both are easy to overlook and both are essential to its cryptographic use. The first is that deciding whether \(n\) is prime or composite is a genuinely different and far easier task than producing its factors. One can certify that an integer is composite, and indeed that it is prime, without exhibiting a single factor. The asymmetry is not merely empirical. Measured in the length of \(n\), primality testing belongs to the class of problems solvable in polynomial time, a result due to Agrawal, Kayal, and Saxena (2002) whose proof lies beyond this page. No such algorithm is known for factoring. So the relevant gap is not between an easy problem and an unsolved one. It is between a problem we know to be tractable and a problem we merely believe to be intractable.

The second feature is that factoring reduces to the simpler-sounding task of splitting: finding any non-trivial factorization \(n = ab\) with \(1 \lt a \lt n\) and \(1 \lt b \lt n\), where \(a\) and \(b\) need not themselves be prime. Once a splitting is found, the factors can be tested for primality, a polynomial-time step as just noted. The splitting procedure is then applied again to whichever of them is composite, and recursion completes the prime factorization. This is why cryptographic constructions can afford to work with a modulus that is a product of exactly two primes, \(n = pq\). To break such a scheme it is enough to split \(n\) once, which recovers \(p\) and \(q\), so the scheme can be secure only if that single split is hard.

How hard is the split? Here the honest answer is a moving target, and saying so is part of the mathematics rather than a hedge around it. The naïve method is trial division by every integer from \(2\) up to \(\sqrt{n}\). It succeeds but costs on the order of \(\sqrt{n}\) divisions in the worst case, which is exponential in the length of \(n\), so the method is useless at cryptographic sizes.

Every improvement since the naïve method has chipped away at that exponent without reaching a polynomial-time algorithm. The methods that succeed in practice are not polynomial. The best of them run in time that grows faster than any polynomial in the length of \(n\) yet far slower than the trial-division exponential, and this intermediate regime is called subexponential. The precise running times, and the ingenuity behind the algorithms that achieve them, are a subject in their own right. What matters here is the shape of the curve, not its equation. No known classical procedure factors a general large integer in polynomial time, and that single negative fact is the entire foundation on which a factoring-based trapdoor stands.

And this foundation has a known expiry condition. It is, after all, a wager: that \(p, q \mapsto pq\) is easy, which is plainly true, and that its inverse is hard, which is a conjecture supported by evidence but unproven. Everything said so far concerns classical computation, that is, algorithms running on the kind of machine the earlier pages took for granted. The factoring problem is not hard in an absolute sense. It is hard relative to that model.

A quantum computer running Shor's algorithm factors integers in polynomial time and so collapses the asymmetry between multiplication and factoring on which the entire construction depends. The subexponential difficulty that protects a factoring-based trapdoor is a property of the classical world alone. The hardness of factoring is real and useful, but against a sufficiently capable adversary it is temporary: one of the two oldest assumptions a public-key scheme can be built on, named here with its limit already in view.

The Discrete Logarithm Problem

Factoring is one source of a one-way asymmetry, but it is not the only one, and tying every public-key construction to a single problem would be a fragile design. A second source comes from a place the reader has already visited: the structure of a finite cyclic group. Inside such a group, exponentiation runs easily in one direction and, on the right groups, resists inversion in the other. Naming that resistance precisely is the goal of this section, and the naming will expose something the algebraic pages could not have shown on their own.

Fix a finite cyclic group \(G\) of order \(n\) with generator \(\alpha\). Every element of \(G\) is a power of \(\alpha\), so for each \(\beta \in G\) there is an exponent that produces it. Reading that exponent off from \(\beta\) is the problem.

The forward direction is cheap. Given \(x\), computing \(\alpha^x\) takes a number of group operations proportional to the length of \(x\), by repeated squaring. The reverse direction, finding \(x\) from \(\beta\), is the one cryptography wants to be hard. The most obvious method simply forms \(\alpha^0, \alpha^1, \alpha^2, \dots\) until \(\beta\) appears, which settles the problem in at most \(n\) multiplications and is hopeless once \(n\) is large. As with factoring, better methods narrow that cost without, in the general case, reaching polynomial time. The standing belief has the same form. In a suitably chosen group, no efficient classical algorithm is known to recover \(x\).

Now comes the observation that makes this problem worth isolating, and it runs against what the algebra alone would predict. Take \(G\) to be a group in which the discrete logarithm is believed hard, and let \(n\) be its order. The multiplicative group modulo a prime, a setting cryptography actually uses, is an example. The earlier pages established that the integers modulo \(n\) form a cyclic group under addition, and that any two cyclic groups of the same order are isomorphic, that is, structurally identical and differing only in how their elements are written. So \(G\) is isomorphic to the additive group \(\mathbb{Z}_n\) of the same order. One might expect a problem defined purely in terms of group structure to be exactly as hard in isomorphic copies. It is not.

Write \(a\) and \(b\) for the images of \(\alpha\) and \(\beta\) under an isomorphism from \(G\) to \(\mathbb{Z}_n\). In the additive group, the "exponentiation" \(\alpha^x\) becomes the repeated addition \(x a\), so the discrete logarithm problem asks for \(x\) with \(x a \equiv b \pmod n\). This is a linear congruence, and it is easy. Because \(\alpha\) generates \(G\), its additive image \(a\) generates \(\mathbb{Z}_n\), so \(\gcd(a, n) = 1\) by the characterization of the generators of \(\mathbb{Z}_n\), and the congruence \(x a \equiv b \pmod n\) has a unique solution modulo \(n\) for every \(b\). The extended Euclidean algorithm produces it directly, in time polynomial in the length of \(n\). The discrete logarithm in the additive presentation is solved almost as soon as it is stated.

Yet in \(G\) itself, the isomorphic copy where exponents are written multiplicatively, the same problem of finding the exponent is the conjectured-hard one cryptography relies on. The isomorphism between \(G\) and \(\mathbb{Z}_n\) is real, and so is the disparity in difficulty between them. The resolution is that an isomorphism preserves group structure but need not preserve computational cost. The step that would carry the hard instance into the easy presentation, and let the linear-congruence method finish it, is the translation of an element of \(G\) into its image in \(\mathbb{Z}_n\). That translation is itself the discrete logarithm problem. The map exists, but computing it is exactly the work we are trying to avoid. Two groups can be the same as algebraic objects and worlds apart as computational ones, because difficulty attaches to the representation of the elements, not to the abstract structure they share.

The same closing caution applies, for the same reason. The hardness of the discrete logarithm is a conjecture about classical computation, and Shor's algorithm computes discrete logarithms in polynomial time as well, in any finite cyclic group whose group operation can be computed efficiently. The two oldest hardness assumptions in public-key cryptography thus fall to the same machine. That coincidence is worth examining, but not yet. For now we have two candidate hardness assumptions rather than one, and the immediate question is how they relate.

Relating One Problem to Another

We now have two hardness assumptions standing side by side, factoring and the discrete logarithm, each a candidate foundation, each conjectural, each classical. A natural question for anyone building on them is how they relate. If a scheme's security rests on the difficulty of some task, it matters whether that task is at least as hard as a problem we already trust, or whether it might secretly be easier. The tool for asking such questions precisely is one the earlier complexity pages already built: reduction. There it compared decision problems. Here we put the same idea to work comparing the search problems that cryptography actually poses, and the shift in setting is worth marking rather than glossing.

The problem we want to relate to the discrete logarithm is the one that underlies key agreement. Suppose two parties have each raised a common base to a private exponent and published the result. An eavesdropper sees both public values but neither exponent. Can the eavesdropper compute the value the base would take if raised to the product of the two private exponents, which is the quantity the parties will share as a secret? That task is a problem in its own right.

The Diffie-Hellman problem and the discrete logarithm problem are plainly related, since both live in the same group and both turn on exponents one cannot see directly. The relationship can be made exact. Suppose someone possesses an efficient method for the discrete logarithm in \(G\). Then, handed the values \(\alpha\), \(\alpha^a\), \(\alpha^b\) of a Diffie-Hellman instance, they first apply that method to \(\alpha^a\) to recover the exponent \(a\). Knowing \(a\), they raise the other public value to it, computing \((\alpha^b)^a = \alpha^{ab}\), which is exactly the Diffie-Hellman answer. A solver for the discrete logarithm yields a solver for Diffie-Hellman, at the cost of one logarithm computation and one exponentiation.

The argument just given is the proof. It computes \(a' = \log_\alpha(\alpha^a)\) with the assumed solver and then returns \((\alpha^b)^{a'}\). Since \(a'\) differs from \(a\) by a multiple of the order of \(G\), this value equals \((\alpha^b)^a = \alpha^{ab}\). Exponentiation by repeated squaring uses a number of group operations polynomial in the length of the group order, and each operation takes polynomial time, so the whole procedure is a polynomial-time computation that calls the discrete-logarithm solver once. That structure, a polynomial-time procedure that invokes a solver for one problem to settle another, is precisely a reduction. Its consequence is an ordering of difficulty. Breaking Diffie-Hellman is at most as hard as computing discrete logarithms. The converse reduction, from the discrete logarithm to Diffie-Hellman, is not known in general. Diffie-Hellman might therefore be strictly easier, in the sense that one could solve it without being able to take logarithms, and the equivalence of the two problems remains open.

The direction of this particular reduction also carries a warning. Diffie-Hellman is no harder than the discrete logarithm, so anything that solves the discrete logarithm dissolves Diffie-Hellman along with it. The quantum attack that breaks the logarithm therefore breaks the key-agreement problem built on it with no separate effort, as the reduction guarantees. An ordering of hardness is a convenience while the problems stand and a liability once the harder one falls, because everything below it falls too. This is one structural reason the collapse of the classical assumptions is wholesale rather than piecemeal, and it explains why the search for replacements has had to begin from problems that no known reduction connects to factoring or to logarithms at all.

A Landscape Built on Conjecture

Stepping back, the one-way asymmetry that the previous page required in the abstract has been given concrete shape three times over. Factoring supplies one asymmetry, the discrete logarithm a second, and the Diffie-Hellman problem a third that the reduction places beneath the logarithm in difficulty. These are the classical foundations of public-key cryptography, and they have carried it for decades. But the honest summary of this page is not a list of solved problems. It is an inventory of assumptions, and an account of exactly how much weight each one can bear.

Two features run through every assumption examined here. The first is that none of them is a theorem. We have no proof that factoring is hard, no proof that discrete logarithms resist efficient computation, no proof that the Diffie-Hellman value cannot be extracted from the public ones. We have forward maps that are demonstrably easy and inverse maps that have demonstrably resisted every efficient method anyone has found. Cryptography on these foundations is cryptography that has converted a wager on open mathematical problems into a guarantee of secrecy. The move is productive, but its terms should not be forgotten. The hardness is conjectured, the security is conditional, and the condition is the continued difficulty of problems that mathematicians are actively trying to make easy.

The second feature, which the earlier pages insisted on and this page has met at every turn, is that hardness is relative to a model of computation. Factoring and the discrete logarithm are intractable for the classical machine the analysis assumed throughout, and tractable in polynomial time for a quantum machine running the appropriate algorithm. The two problems fall to the same attack, and the reduction ensures the Diffie-Hellman problem falls with them.

None of this is a distant prospect to be filed under future work. The threat does not wait for a quantum computer large enough to run these attacks at cryptographic sizes. Ciphertexts recorded before such a machine exists can be stored and broken once it is built, so the threat to long-lived secrets is present rather than deferred. For the same reason, a public standardization process for replacement schemes opened in 2016 and published its first standards in 2024.

The quantum threat is sharp but not universal, and precision matters here as much as it did in the definitions. What the quantum attack dismantles is the specific structure these number-theoretic problems carry, namely the abelian arithmetic that makes a single efficient quantum procedure apply to both factoring and logarithms. Symmetric-key encryption and hash functions, which do not rest on that structure, face, as far as is known, only a generic quantum speedup that searches an unstructured space quadratically faster, an erosion answered by enlarging keys rather than by abandoning the design. The collapse documented here is a collapse of the public-key assumptions built on hidden abelian structure, not of cryptography as a whole. That distinction is what makes a replacement conceivable.

If the danger is that factoring and the discrete logarithm share an algebraic structure a quantum computer exploits, the response is to look for hard problems that do not carry that structure. These are problems for which no efficient quantum algorithm is known, and on which no known reduction from factoring or logarithms bears. One major family of candidates comes from the geometry of high-dimensional integer lattices, where the task of finding a shortest or nearest vector appears to resist quantum and classical attack alike. The trapdoor survives the transition, but the problem it is built from does not.