On the Concrete Security of LWE with Small Secret
summary
Experimental evaluation embeds LWE into a larger lattice and reduces LWE→BDD→USVP, then runs BKZ 2.0 (fplll) for dimensions n=40–200, block sizes β∈{30,35,40,45}, 10 trials per point. Concrete parameter choices include ω balancing (ω=√2·σ for binary, √(2)/2·σ for ternary), and Chen/208/216 Hermite-factor estimates. Observation: the estimates break down for small β, and binary secrets become trivial (example: NewHope-like n=50, α=0.02 breaks in ~2h vs sieving 202h) while ternary needs slightly more (~2.5h); Gaussian secrets resist more.
AI-written summary · about
chapters (17)
- 0:00Intro
- 1:12Shortest Vector Problem (SVP)
- 1:24Algorithms to solve SVP
- 2:48Goal of this work
- 3:42BKZ algorithm for lattice reduction
- 4:55Root Hermite factor
- 7:18Learning With Errors (LWE)
- 8:31Unique Shortest Vector Problem (USVP)
- 9:51Reduction to BDD (Bounded Distance Decoding)
- 11:25Balancing the secret
- 12:12Estimating parameters
- 13:102008 Estimate (Gama and Nguyen)
- 14:432016 Estimate (New Hope)
- 18:43Experiments
- 22:08Observations
- 24:41Plot of running times
- 26:03TU Darmstadt LWE challenges for binary secrets
related talks
57mAlgorithms for Lattice Problems, in Practice
01h 04mUsing Lattices for Cryptanalysis
39mLattice Based Cryptography Primer
40mPost-Quantum
01h 40mHistorical Talk on Lattice-Based Cryptography
01h 04mThe Mathematics of Lattices II
56mContinuous LWE is as Hard as LWE
57mLattice Assumptions with Hints: Succinct LWE and its Applications