Algorithms for Algebraic Lattices: Classical and Quantum
summary
Claim: quantum procedures turn ideal-SVP on cyclotomic rings from seemingly exponential hardness into an approx exp(√n) drop (and even polynomial beyond that threshold) by combining two concrete tools: a quantum class-group discrete-log routine (a continuous hidden subgroup style algorithm building on Eisenträger/Hallgren/Kitaev/Song and Biasse–Song) to make a nonprincipal ideal principal, and a logarithmic-embedding + CVP routine over the unit lattice (using explicit cyclotomic units and Stickelberger relations) to shrink generators. The pieces are proven correct in theory, require heavy quantum subroutines with nontrivial polynomial exponents (generic analyses give high-degree bounds), and do not yet break recommended practical parameters but open specific, implementable attack paths and several concrete complexity questions.
AI-written summary · about
chapters (15)
- 0:00Introduction
- 1:30Why do we care
- 4:10The problem
- 9:56Ideal lattices
- 18:54Ideal lattice geometry
- 19:58Algebraic norm
- 22:54Class group
- 28:58Formal definition
- 30:08logarithmic embedding
- 40:59Reducing modular lattice
- 42:59Cyclotomic number fields
- 48:01Closed principle multiple problem
- 49:55Discrete logarithm problem
- 52:04Cali Cali graph
- 57:05Cyclotomic lattice
related talks
01h 08mCryptography from Ideal Lattices
01h 08mThe Mathematics of Lattices I
01h 40mHistorical Talk on Lattice-Based Cryptography
58mQuantum 2
59mNew Reductions and Algorithms for Ideal Lattices via Arakelov Random Walks
40mPost-Quantum
52mAn LLL Algorithm for Module Lattices
01h 06mHardness of the Shortest Vector Problem: A Simplified Proof and a Survey