New Reductions and Algorithms for Ideal Lattices via Arakelov Random Walks
summary
Shows a worst-case to average-case reduction for Hermite-ideal SVP: if an oracle solves random ideal lattices of a ring, the reduction solves any ideal lattice over that ring with only about a √n loss in approximation under ERH and mild hypotheses. It builds a random walk on the Arakelov/Picard torus combining sparsification via prime ideals (discrete jumps, norm ≤ B) and a Gaussian continuous blur, analyzes mixing via the Hecke operator bounds on Hecke-character eigenvalues, and gives polynomial B so endpoints are ε-close to uniform.
AI-written summary · about
chapters (18)
- 0:00Introduction
- 1:20The Hermit VP problem
- 14:35Reductions
- 16:05Walks
- 18:50Discrete Walk
- 20:05Thank you
- 21:40Class groups
- 23:00Random walks in finite groups
- 26:50Choosing generating sets
- 28:40Adjacency operator
- 30:12Fourier analysis
- 32:35Jeremy Lin Venkat
- 39:45Oracle of Class Group
- 44:30Hecker Operator
- 46:13Picard Groups
- 47:49Bounds
- 50:10Final result
- 51:20Questions
related talks
01h 15mAlgebraic Lattices and Ring Learning with Errors
01h 36mAlgorithms for Algebraic Lattices: Classical and Quantum
01h 40mHistorical Talk on Lattice-Based Cryptography
01h 08mCryptography from Ideal Lattices
01h 08mThe Mathematics of Lattices I
01h 04mThe Mathematics of Lattices II
01h 42mMathematics of Lattices
01h 06mHardness of the Shortest Vector Problem: A Simplified Proof and a Survey