Improved Hardness of BDD and SVP Under Gap-(S)ETH
summary
Shows fine-grained hardness reductions from SAT to lattice problems using locally dense gadgets and two-point counts, proving BDD cannot be solved in 2^{o(n)} time for any norm when the relative distance alpha ≥ ≈0.98 under non-uniform gap-ETH, and giving SETH-type lower bounds that BDD needs ≥2^{n/c} time for alpha>alpha_dagger and SVP needs ≥2^{n/c} time for p≳2.1 and some γ>1 under randomized gap-SETH. Key tool: gadgets with N_close ≥ ν·N_short where ν is exponential 2^{C_kn n} (C_kn≈0.02), improving prior BP20/AS'18 bounds and extending exact-SVP hardness to γ=1+ε.
AI-written summary · about
chapters (9)
- 0:00Intro
- 0:13Preliminaries: Lattices
- 0:55Preliminaries: Lattice-Based Cryptography
- 1:58Preliminaries: Shortest Vector Problem (SVP)
- 4:05Preliminaries: Exponential Time Hypothesis (ETH)
- 6:03Our Results: SETH-Type Hardness of SVP
- 11:47Main Theorem for BDD
- 13:22Gadgets We Use
- 14:27Instantiating the Main Theorem
related talks
01h 03mComplexity of Lattice Problems
01h 06mHardness of the Shortest Vector Problem: A Simplified Proof and a Survey
01h 13mAlgorithms for Lattice Problems
30mOn the Concrete Security of LWE with Small Secret
01h 04mExplicit SoS Lower Bounds from (Small-Set) High Dimensional Expanders
59mSome Recent Results Showing that Lattice Problems Are (sort of) Equivalent in All Norms
01h 04mUsing Lattices for Cryptanalysis
19mProvable Sieving Algorithms for SVP and CVP in the l_p norm