Oded Regev introduced learning with errors as a foundation for lattice-based cryptography. His paper connects appropriately parameterized noisy modular linear equations to worst-case lattice problems through a quantum reduction, and constructs a classical public-key encryption scheme from that learning assumption.[ref]
The distinction between a quantum reduction and a classical cryptosystem matters: the encryption and decryption procedures need not run on a quantum computer, even though the reduction establishing the hardness connection uses quantum computation. The work also makes the error distribution part of the problem definition. Removing the errors gives ordinary modular linear equations and changes the computational task fundamentally. Regev's research homepage identifies this lattice-based work among his contributions.[ref]
Articles by others on the same topic
There are currently no matching articles.