View source for 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 versus NP problem|P ≠ NP]] conjecture, which underlies not only cryptography but the entire field of [[Computational Complexity|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.

[[Category:Computational Complexity]]
[[Category:Cryptography]]