Computational cryptography › Public-key encryption and key exchange › Post-quantum public-key › Lattices
Hardness assumption

Module-SIS

In plain words

Find a short combination of vectors that adds up to zero. Hard in big lattices.

The idea: Given a big public matrix, find a combination of its columns, using only small numbers, that adds up to zero. With big numbers allowed it's basic algebra. Restricted to small numbers it's hard. In ML-DSA a valid signature is a small vector that satisfies the public equations, so forging one would amount to finding such a small solution.

Why it matters: Makes ML-DSA signatures impossible to forge.

The details

Short integer solution: find a short nonzero vector x with A × x = 0 (mod q)[1]. SIS gives collision-resistant hashing and signatures but not key exchange, so there is no KE tag.

The structured Module-SIS version underlies ML-DSA's unforgeability[2, 3].

Rests on

If any of these breaks, this breaks too.

If it falls

If this breaks, these break with it.

References

  1. M. Ajtai. Generating hard instances of lattice problems (extended abstract). Proceedings of the twenty-eighth annual ACM symposium on Theory of computing - STOC '96, 1996. doi:10.1145/237814.237838
  2. 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
  3. NIST. Module-lattice-based digital signature standard. NIST FIPS 204, 2024. doi:10.6028/NIST.FIPS.204