= 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.<On Lattices, Learning with Errors, Random Linear Codes, and Cryptography by Oded Regev>[abstract and §1, scope of the quantum reduction]{ref}
Back to article page
