Challenges in Evaluating Costs of known Lattice Attacks
summary
Claims that commonly used cost formulas for lattice attacks are unreliable: experiments and SAGE-scripted tests show the BKZ-beta delta is unreliable and the extrapolated sieving .292 exponent is unjustified. The talk demonstrates concrete lattice constructions (homogenization, Bi‑Galbraith/Cannon embeddings, projecting/fixing coefficients), compares sieving vs enumeration under realistic 2D-circuit and memory models, and recomputes NTRU‑Prime numbers; results produce different security bits and suggest hybrid attacks consistently improve costs. Lots of open questions and conservative tables of alternative estimates are provided.
AI-written summary · about
chapters (20)
- 0:00Introduction to lattice attacks
- 1:01Defining the core problems
- 4:50Mapping problems to crypto
- 7:40Analyzing system encryption
- 9:26Parameters and survey
- 11:23Primal attack overview
- 12:51Models of computation
- 15:32Hardware-based models
- 18:33Homogenizing the problems
- 22:35Exploiting algebraic structure
- 25:40Reducing lattice dimension
- 28:39Concrete parameter analysis
- 33:28Optimization and scaling
- 36:16BKZ algorithm analysis
- 38:52Flaws in standard analysis
- 42:30Need for better models
- 45:59Independence assumptions
- 47:28Cost of sieve vs enum
- 50:57Conclusion on security
- 55:58Session wrap-up
