Algorithms for the k-List Problems

on YouTube ↗01h 06m

" summary

Reduction shows LWE samples map to extended dihedral-coset states when the number of shifts M and sample count L satisfy L ≈ Q^n / M, so small M forces many samples. The algorithm prepares a Gaussian-weighted superposition over shifts, rounds coordinates into boxes to isolate one lattice coset, then measures to produce DCP-like states. Final decoding uses Kuperberg-style list combining (pairwise merges that halve the effective modulus repeatedly) yielding a classical-time, classical-memory routine with exponential-but-square-root-like tradeoffs in the parameters.

AI-written summary · about

" chapters (4)

1. 0:00Introduction
2. 1:50Careless problem
3. 8:00Dihedral problem
4. 43:38Shape of Q

" related talks

• 57mAlgorithms for Lattice Problems, in PracticeElena Kirshanova, Pierre-Alain Fouque · Lattices: Algorithms, Complexity, and Cryptography Boot Camp 2020
• 01h 04mThe Mathematics of Lattices IIVinod Vaikuntanathan · Cryptography Boot Camp 2015
• 01h 29mLattices, Multilinear Maps and Program ObfuscationYilei Chen · Lattices: Algorithms, Complexity, and Cryptography Boot Camp 2020
• 52mFast list-decoding of univariate multiplicity and folded Reed-Solomon codesPrahladh Harsha · Advances in the Theory of Error-Correcting Codes
• 37mAlgebraic Algorithms for LWELudovic Perret · The Mathematics of Modern Cryptography
• 45mAn Exponential Lower Bound for Linear 3-Query Locally Correctable CodesPeter Manohar · Advances in the Theory of Error-Correcting Codes
• 39mLattice Based Cryptography PrimerBob Relyea · DevConf.CZ 2021
• 01h 06mLattice-based Zero-knowledge ProofsVadim Lyubashevsky · Quantum and Lattices Joint Reunion Workshop