Opening Learning With Errors (LWE) and Public Key Encryption
Learning With Errors (LWE) and Public Key Encryption
- Length
- 26 min
- Level
- Graduate
- Recorded
- Carnegie Mellon University2020
Chapter 1 of 4: Public key encryption and quantum security
O'Donnell builds Regev's one-bit public key scheme from noisy linear equations mod and proves decryption correct.
The Learning With Errors (LWE) assumption states that no polynomial-time algorithm can recover a secret vector from noisy linear equations over a finite field. O'Donnell starts from public key encryption and its one-bit security definition, then notes that Shor's quantum algorithm breaks RSA. He contrasts trapdoor one-way permutations and average-case number-theoretic assumptions with lattice problems, where Regev's 2005 reduction ties average-case LWE to worst-case gap SVP. Regev's encryption scheme is then built step by step, with a secret vector and public noisy equations carrying one bit. Decryption is shown correct as long as the summed Gaussian errors stay below a fraction of . Lecture 25d of CMU's graduate course A Theorist's Toolkit, it assumes modular arithmetic, Gaussians and polynomial-time complexity.
The Learning With Errors (LWE) assumption states that no polynomial-time algorithm can recover a secret vector from noisy linear equations over a finite field. O'Donnell starts from public key encryption and its one-bit security definition, then notes that Shor's quantum algorithm breaks RSA. He contrasts trapdoor one-way permutations and average-case number-theoretic assumptions with lattice problems, where Regev's 2005 reduction ties average-case LWE to worst-case gap SVP. Regev's encryption scheme is then built step by step, with a secret vector and public noisy equations carrying one bit. Decryption is shown correct as long as the summed Gaussian errors stay below a fraction of . Lecture 25d of CMU's graduate course A Theorist's Toolkit, it assumes modular arithmetic, Gaussians and polynomial-time complexity.
Regev 2005 paper
Regev's 2005 paper
Peikert's paper

This lecture
Lecture 82 of 89 of A Theorist's Toolkit.
Choose a node to see how it connects to this lecture. What comes before is on the leftat the top. What comes after is on the rightat the bottom. The ring is what it teaches. People and places are above. Other lectures and books are below.
Press a chosen node again to open it.
Your comment is kept while you sign up.Sign in