Finding Short Generators of Principal Ideals

on YouTube ↗36m

" summary

Given a principal ideal presented by a bad basis, the result proves a classical polynomial‑time method to recover the short generator (up to trivial unit factors) for any prime‑power cyclotomic ring when the secret was sampled short (e.g. Gaussian), by reducing the task to bounded distance decoding on the log unit lattice. The construction uses cyclotomic unit bases (finite‑index sublattices from Dirichlet theory) and shows prior heuristics and experiments (Campbell, Groves, Shephard) are correct; it classically weakens several proposed ring‑key schemes.

AI-written summary · about

" chapters (7)

1. 0:00Introduction
2. 10:46General Problems
3. 18:15Technical Content
4. 25:09Unit Theorem
5. 27:29Finding G
6. 31:16Analysis
7. 34:27Conclusion

" related talks

• 01h 36mAlgorithms for Algebraic Lattices: Classical and QuantumLéo Ducas · Lattices: Algorithms, Complexity, and Cryptography Boot Camp 2020
• 01h 15mAlgebraic Lattices and Ring Learning with ErrorsChris Peikert · Lattices: Algorithms, Complexity, and Cryptography Boot Camp 2020
• 59mNew Reductions and Algorithms for Ideal Lattices via Arakelov Random WalksBenjamin Wesolowski, Léo Ducas · Lattices: Geometry, Algorithms and Hardness 2020
• 34mHigh-entropy dual functions and locally decodable codesFarrokh Labib, Jop Briet · ITCS 2021
• 57mEssentially Optimal Interactive Certificates in Linear AlgebraErich Kaltofen · Geometric Complexity Theory 2014
• 25mConstructing a Fast Prime-Order GroupHenry De Valence · Zcon1: Zero to Privacy Hero 2019
• 01h 04mUsing Lattices for CryptanalysisNadia Heninger · Lattices: Algorithms, Complexity, and Cryptography Boot Camp 2020
• 40mThe Hidden Subgroup Problem for Infinite GroupsGreg Kuperberg · Quantum and Lattices Joint Reunion Workshop