Computational cryptography › Public-key encryption and key exchange › Post-quantum public-key › Lattices
Trust or structural assumption

Ring/module structure gives no shortcut

In plain words

The bet that the extra structure used to shrink lattice keys doesn't give attackers a shortcut.

The idea: Structured lattices pack the problem into polynomials with symmetries, which is what makes ML-KEM's keys small. Symmetry can be a gift to attackers: algebraic tricks have broken related problems in special, weaker settings. The bet is that, for the parameters actually used, the structure saves space without saving the attacker any work.

Why it matters: If it did, ML-KEM and ML-DSA would weaken, but FrodoKEM wouldn't.

The details

Structured (ring and module) lattices use algebra to shrink keys a lot[1, 2]. The extra assumption is that this structure doesn't help attackers.

No known attack exploits it for the parameters in use. Attacks on ideal lattices exist only for much weaker settings than cryptography uses[3]. FrodoKEM avoids structure entirely[4] as the conservative option.

Rests on

If any of these breaks, this breaks too.

If it falls

If this breaks, these break with it.

Everything that falls with it (7 boxes)

References

  1. Vadim Lyubashevsky, Chris Peikert and Oded Regev. On Ideal Lattices and Learning with Errors over Rings. Journal of the ACM, 2013. doi:10.1145/2535925
  2. 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
  3. Ronald Cramer, Léo Ducas, Chris Peikert and Oded Regev. Recovering Short Generators of Principal Ideals in Cyclotomic Rings. Advances in Cryptology – EUROCRYPT 2016. doi:10.1007/978-3-662-49896-5_20
  4. Joppe Bos, Craig Costello, Leo Ducas et al. Frodo: Take Off the Ring! Practical, Quantum-Secure Key Exchange from LWE. Proceedings of the 2016 ACM SIGSAC Conference on Computer and Communications Security. doi:10.1145/2976749.2978425