Ring-LWE and Module Lattices
Examine how Ring-LWE and Module-LWE achieve better efficiency while retaining LWE hardness properties.
From LWE to Ring-LWE
Standard LWE requires large matrix-vector products, leading to large key sizes. Ring-LWE, introduced by Lyubashevsky, Peikert, and Regev in 2010, replaces vectors and matrices with polynomials in a ring R_q = Z_q[X]/(f(X)). This structured setting enables much more compact keys and faster arithmetic, making Ring-LWE the practical foundation for real-world lattice cryptography.
The Cyclotomic Polynomial
The polynomial f(X) used in Ring-LWE is typically f(X) = X^n + 1, where n is a power of 2. This is the 2n-th cyclotomic polynomial. It is chosen because it is irreducible over Z, ensures the ring R_q has good algebraic properties, and enables the Number Theoretic Transform (NTT) for efficient multiplication. Cyclotomic rings have been deeply studied and are believed to be secure.