Cryptographic Hardness

Cryptographic hardness refers to the unproven computational assumptions that underlie the security of modern cryptographic systems. A cryptographic scheme is secure if and only if breaking it requires solving a problem believed to be computationally hard — meaning no efficient algorithm is known, and strong evidence suggests none exists. The canonical assumptions include the hardness of integer factoring (RSA security), the discrete logarithm problem (Diffie-Hellman, DSA, elliptic curve cryptography), and lattice problems (post-quantum cryptography). These are not proven to be hard: they are conjectured to be hard based on decades of failed attempts to find efficient algorithms. The entire security of internet communications, financial transactions, and authenticated identity rests on these conjectures — which is to say, on the complexity-theoretic belief that P ≠ NP and that specific problems are outside P.

The Structure of Hardness Assumptions

Cryptographic hardness is not a single claim but a hierarchy of assumptions with varying strength and varying evidence:

Factoring integers (basis of RSA): Given a large composite number N = p × q where p and q are prime, find p and q. No polynomial-time classical algorithm is known. The best known algorithm, the General Number Field Sieve, has superpolynomial but subexponential complexity — approximately exp((64/9)^(1/3) × (ln N)^(1/3) × (ln ln N)^(2/3)). This is slow enough for practical security at key sizes of 2048 bits or larger, but it is not exponential. The assumption is weaker than P ≠ NP: factoring is in NP but is not known to be NP-complete. It could be intermediate in difficulty.

The discrete logarithm problem (basis of Diffie-Hellman, ElGamal, DSA): Given a prime p, a generator g of the multiplicative group modulo p, and an element h = g^x mod p, find x. This problem is closely related to factoring, and algorithms that break one often illuminate the other. Elliptic curve variants replace the multiplicative group with the group of points on an elliptic curve, where the discrete logarithm problem appears to be harder for currently known algorithms — allowing smaller key sizes for equivalent security.

Lattice problems (basis of post-quantum cryptography): The Learning With Errors (LWE) problem and the Shortest Vector Problem (SVP) in high-dimensional lattices. These problems have a remarkable property: some variants are as hard as the worst-case instances of related problems, not merely average-case. This worst-case-to-average-case reduction, proved by Ajtai (1996) and extended by Regev (2005), makes lattice-based cryptography qualitatively different from factoring-based cryptography: the hardness assumption is not merely 'we have not found an algorithm' but 'finding an algorithm for the average case would imply an algorithm for the worst case, which we believe does not exist.'

Quantum Threats and Post-Quantum Transition

Shor's algorithm (1994) solves integer factoring and discrete logarithm in polynomial time on a quantum computer. This is not a marginal improvement. It is a complexity-class shift: problems believed to require superpolynomial time on classical computers require polynomial time on quantum computers. The threat is not immediate — current quantum computers have too few qubits and too much noise to run Shor's algorithm at cryptographically relevant scales — but it is structural. If large-scale fault-tolerant quantum computing becomes possible, RSA, Diffie-Hellman, and elliptic curve cryptography become insecure.

This has driven the development of post-quantum cryptography: cryptographic schemes based on problems believed to be hard even for quantum computers. Lattice-based, hash-based, code-based, and multivariate-polynomial schemes are the main candidates. NIST standardized its first post-quantum algorithms in 2024, and the transition is underway — but it will take decades, because cryptographic infrastructure is embedded in hardware, protocols, and institutional practices that change slowly.

The deeper question: are lattice problems actually hard for quantum computers? We do not know. There is no proof that LWE is hard for quantum computers, only the absence of known quantum algorithms. The post-quantum transition is a bet on the continued failure of quantum algorithm research, not a guarantee.

The Epistemic Asymmetry

Cryptographic hardness reveals a deep asymmetry between proof and security. We cannot prove our systems are secure. We can only prove that their insecurity would require solving problems we believe are hard. This is not a limitation of current mathematical knowledge. It is a structural feature: proving that a problem is hard is at least as difficult as solving it, and in many cases equivalent to proving lower bounds in computational complexity theory — a field in which fundamental progress has been slow.

The asymmetry has practical consequences. Cryptographic systems are deployed on the basis of confidence, not certainty. Confidence is built through accumulated failure of attack attempts, through reduction proofs that show 'if you can break this scheme, you can solve this hard problem,' and through standardization processes that subject schemes to public scrutiny. But none of these provide the kind of guarantee that a proof of P ≠ NP would provide.

The situation is analogous to the status of induction in science: we cannot prove that the future will resemble the past, but we proceed on the basis of a confidence built from accumulated past success. Cryptographic hardness is the computational analog: we cannot prove that factoring is hard, but we proceed on the basis of a confidence built from decades of failed attempts.

Cryptographic Hardness in the Systems View

From a systems perspective, cryptographic hardness is not merely a mathematical property. It is an ecological property: the hardness of a problem depends on the computational resources available to the attacker, the time horizon of the attack, and the value of the information being protected. A problem that is hard for an individual with a laptop may not be hard for a nation-state with a supercomputing center. A problem that is hard today may not be hard in twenty years if algorithmic progress continues. Cryptographic security is therefore not a static property of a scheme but a dynamic property of the interaction between scheme, attacker, and environment.

This dynamical view is uncomfortable for the cryptographic community, which prefers the clarity of asymptotic complexity classes. But it is the view that corresponds to actual practice. Key sizes are increased over time not because the mathematics changed but because the computational ecology changed. The post-quantum transition is not a mathematical necessity but an ecological anticipation: the quantum computer is not yet a threat, but the ecosystem is being prepared for its possible emergence.

The entire edifice of digital security rests on conjectures. The conjectures are well-supported. They are not proven. The difference between a conjecture and a theorem is the difference between confidence and certainty — and in the domain of cryptographic hardness, certainty may be permanently unavailable.\n\n