An LLL Algorithm for Module Lattices
summary
An LLL-style algorithm produces short vectors in module lattices over any number field, giving an approximation factor roughly 2^{rank} (quasi‑polynomially dependent on the field degree) by reducing rank‑2 to rank‑n and solving rank‑2 via a log‑embedding/CVP construction. It relies on a CVP oracle in a fixed lattice of dimension ~d^2 (uses units for free, heuristic covering‑radius assumptions, and quantum subroutines to compute units), shows small experimental CVP runs (dims ≈150), and is currently impractical compared to BKZ.
AI-written summary · about
chapters (14)
- 0:00An LLL algorithm for module lattices
- 10:31What is small in K?
- 15:10Previous works and result
- 19:25Outline of the talk
- 20:42High-level overview of LLL
- 23:39Inner product over R
- 26:21QR factorization over R
- 29:40Euclidean division
- 35:29Using the Log space
- 37:14Idea of the algorithm
- 41:21Heuristic
- 47:44Under the carpet
- 48:02Summary and impact
- 50:31Open problems
related talks
01h 04mUsing Lattices for Cryptanalysis
01h 36mAlgorithms for Algebraic Lattices: Classical and Quantum
01h 08mThe Mathematics of Lattices I
01h 42mMathematics of Lattices
57mAlgorithms for Lattice Problems, in Practice
01h 40mHistorical Talk on Lattice-Based Cryptography
01h 16mMultilinear Maps Over the Integers: From Design to Security
01h 03mComplexity of Lattice Problems