 Computational hardness assumption

A computational hardness assumption states that a specified computational task cannot be solved efficiently in a specified model and input distribution. A useful cryptographic statement identifies the parameter controlling size, the adversary's resources and the permitted success probability. Difficulty on occasional worst-case instances alone need not protect the instances produced by a key-generation algorithm.

For example, a proposed encryption scheme may reduce message recovery to solving learning with errors instances sampled in a particular way. The reduction says that a successful attack would yield a solver for those instances; security remains conditional on the hardness assumption and the implementation meeting the model. Oded Regev's lattice reduction makes this relationship unusually concrete, connecting a noisy average-case problem to worst-case lattice problems through a quantum reduction.^[ref]

A **computational hardness assumption** is a principle or conjecture in cryptography and computer science that posits certain mathematical problems are inherently difficult to solve in a reasonable amount of time, even with the best known algorithms and the most powerful computers available. These assumptions are foundational for the security of various cryptographic systems and protocols.