Computational cryptography › Public-key encryption and key exchange › Post-quantum public-key › Lattices
Hardness assumptionKE: gives key exchangeTD: gives trapdoor functions

Module-LWE / Ring-LWE

In plain words

A more structured, efficient version of LWE that keeps keys small.

The idea: Plain LWE needs a big matrix of random numbers, which makes keys large. Module-LWE uses polynomials instead: one polynomial with 256 coefficients stands for a whole structured 256-by-256 block of the matrix. Keys shrink to about a kilobyte and the math gets fast. The bet is that this tidy structure doesn't hand attackers a shortcut.

Why it matters: Behind NIST's main quantum-safe standards, ML-KEM and ML-DSA.

The details

LWE with algebraic structure, matrices over polynomial rings[1], which makes keys and computations much smaller and faster. Security additionally relies on that structure giving attackers no shortcut.

It underlies ML-KEM (Kyber), ML-DSA (Dilithium)[2, 3] and fully homomorphic encryption schemes such as BGV, BFV and CKKS[4, 5, 6] (KE).

Rests on

If any of these breaks, this breaks too.

If it falls

If this breaks, these break with it.

About the tags

KE
This assumption gives key exchange on its own, so it needs more than one-way functions and falls if public-key encryption is impossible.
TD
This assumption gives trapdoor functions on its own (computable by anyone, invertible only with a secret), so it falls if trapdoor functions don't exist. Schemes built on it need not use a trapdoor: ElGamal doesn't.

References

  1. Adeline Langlois and Damien Stehlé. Worst-case to average-case reductions for module lattices. Designs, Codes and Cryptography, 2015. doi:10.1007/s10623-014-9938-4
  2. Joppe Bos, Leo Ducas, Eike Kiltz et al. CRYSTALS - Kyber: A CCA-Secure Module-Lattice-Based KEM. 2018 IEEE European Symposium on Security and Privacy (EuroS&P). doi:10.1109/eurosp.2018.00032
  3. Léo Ducas, Eike Kiltz, Tancrède Lepoint et al. CRYSTALS-Dilithium: A Lattice-Based Digital Signature Scheme. IACR Transactions on Cryptographic Hardware and Embedded Systems, 2018. doi:10.46586/tches.v2018.i1.238-268
  4. Zvika Brakerski, Craig Gentry and Vinod Vaikuntanathan. (Leveled) fully homomorphic encryption without bootstrapping. Proceedings of the 3rd Innovations in Theoretical Computer Science Conference, 2012. doi:10.1145/2090236.2090262
  5. Somewhat Practical Fully Homomorphic Encryption. IACR Cryptology ePrint Archive, Paper 2012/144. eprint.iacr.org/2012/144
  6. Jung Hee Cheon, Andrey Kim, Miran Kim and Yongsoo Song. Homomorphic Encryption for Arithmetic of Approximate Numbers. Advances in Cryptology – ASIACRYPT 2017. doi:10.1007/978-3-319-70694-8_15