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]
On Lattices, Learning with Errors, Random Linear Codes, and Cryptography by Oded Regev. abstract and §1, scope of the quantum reduction
Articles by others on the same topic
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.