= Oded Regev
{c}
<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.<On Lattices, Learning with Errors, Random Linear Codes, and Cryptography by Oded Regev>[abstract and §1, main theorem and cryptosystem]{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.https://cims.nyu.edu/~regev/[Research, Mathematical and cryptographic aspects of lattices]{ref}
Back to article page
