Lattice Cryptography — SIS, Trapdoor Sampling, and Signatures
Stub. Beyond the LWE assumption (already covered): integer lattices, the Short Integer Solution (SIS) problem and ring-LWE (an algebraically structured, more efficient variant of LWE), trapdoor sampling from a lattice (generating a lattice together with a hard-to-find short-vector trapdoor), and building digital signatures directly from lattice problems (GPV-style hash-and-sign using the trapdoor).
Corresponds to Chapter 17 (the LWE assumption itself, in both search and decisional form, is already covered in learning-with-errors-and-the-random-oracle-model). An integer lattice is a discrete subgroup of , and the Short Integer Solution (SIS) problem — find a short nonzero vector mapping to zero under a random linear map — is LWE’s “dual” hardness assumption, underlying collision-resistant hash functions and signatures rather than encryption. Ring-LWE restructures LWE over a polynomial ring instead of plain vectors, giving much more compact keys and faster arithmetic at the cost of extra (but still well-studied) algebraic structure — the basis of most practical post-quantum standards. Trapdoor sampling generates a lattice (public) together with a secret basis of unusually short vectors (the trapdoor), which is exactly the tool needed to build signatures from lattice problems: sign by using the trapdoor to find a short vector solving an SIS-style instance derived from the message, verifiable by anyone without the trapdoor. See fully-homomorphic-encryption-classical-and-quantum for lattice-based (GSW) fully homomorphic encryption, covered there from a quantum-crypto angle.
Outline (TODO — flesh out each)
- Integer lattices
- The Short Integer Solution (SIS) problem
- The ring-LWE problem
- Trapdoor sampling from a lattice
- Signatures from lattice problems
- Fun application: factoring integers using lattices