The paper introduces a new cryptographic primitive called *ring-LWE* (Learning with Errors over Rings), which is an algebraic variant of the well-known *learning with errors* (LWE) problem. The authors prove that ring-LWE enjoys strong hardness guarantees, specifically that it is pseudorandom under the assumption that worst-case lattice problems on ideal lattices are hard for polynomial-time quantum algorithms. This result has several important implications: 1. **Efficiency**: The use of ring-LWE can significantly reduce the key sizes and improve the efficiency of cryptographic schemes based on LWE, making them more practical for real-world applications. 2. **Cryptographic Applications**: The paper demonstrates how to construct a practical lattice-based public-key cryptosystem using ring-LWE, which is the first such system with an efficient security reduction. Additionally, many other applications of LWE can be made more efficient by using ring-LWE. 3. **New Cryptographic Applications**: The algebraic structure of ring-LWE may lead to new cryptographic applications that were not previously known to be based on LWE. The main technical contributions of the paper include: - Proving the hardness of the search problem in ring-LWE under worst-case assumptions on ideal lattices. - Establishing a search/decision equivalence for ring-LWE, which allows for the construction of cryptographic schemes. - Introducing new techniques for working with rings of integers and their ideal lattices, including the use of the Chinese Remainder Theorem and properties of cyclotomic number fields. The paper also discusses related work, including a concurrent and independent effort by Stehlé, Steinfeld, Tanaka, and Xagawa, and provides a detailed comparison of their approaches and outcomes.The paper introduces a new cryptographic primitive called *ring-LWE* (Learning with Errors over Rings), which is an algebraic variant of the well-known *learning with errors* (LWE) problem. The authors prove that ring-LWE enjoys strong hardness guarantees, specifically that it is pseudorandom under the assumption that worst-case lattice problems on ideal lattices are hard for polynomial-time quantum algorithms. This result has several important implications: 1. **Efficiency**: The use of ring-LWE can significantly reduce the key sizes and improve the efficiency of cryptographic schemes based on LWE, making them more practical for real-world applications. 2. **Cryptographic Applications**: The paper demonstrates how to construct a practical lattice-based public-key cryptosystem using ring-LWE, which is the first such system with an efficient security reduction. Additionally, many other applications of LWE can be made more efficient by using ring-LWE. 3. **New Cryptographic Applications**: The algebraic structure of ring-LWE may lead to new cryptographic applications that were not previously known to be based on LWE. The main technical contributions of the paper include: - Proving the hardness of the search problem in ring-LWE under worst-case assumptions on ideal lattices. - Establishing a search/decision equivalence for ring-LWE, which allows for the construction of cryptographic schemes. - Introducing new techniques for working with rings of integers and their ideal lattices, including the use of the Chinese Remainder Theorem and properties of cyclotomic number fields. The paper also discusses related work, including a concurrent and independent effort by Stehlé, Steinfeld, Tanaka, and Xagawa, and provides a detailed comparison of their approaches and outcomes.