Computational hardness assumption

A computational hardness assumption is the conjecture that a specific computational problem cannot be solved efficiently — typically, in polynomial time — by a given model of computation. The security of nearly all modern public-key cryptography rests on such assumptions: the RSA algorithm assumes that integer factorization is hard for classical computers; the Diffie-Hellman Key Exchange assumes that the Discrete Logarithm Problem is hard; lattice-based systems assume that finding short vectors in high-dimensional lattices is hard.

These assumptions are not theorems. They are empirical hypotheses about the limits of computation, sustained by decades of failed attempts to find efficient algorithms. The history of cryptography is a graveyard of hardness assumptions: problems once thought intractable have fallen to unexpected algorithmic insights or to new physical models of computation, as Shor's algorithm demonstrated for factoring and discrete logarithms on quantum computers. A hardness assumption is therefore not a foundation but a wager — a bet that the next mathematical insight will not arrive before the infrastructure it protects needs replacing.

The most famous unproved hardness assumption is the P ≠ NP conjecture, which underlies not only cryptography but the entire field of computational complexity theory. If P = NP, then every problem whose solution can be efficiently verified can also be efficiently solved, and public-key cryptography as we know it would collapse entirely.