Improved Hardness of BDD and SVP Under Gap-(S)ETH

Huck Bennett, Chris Peikert, Yi Tang

We show improved fine-grained hardness of two key lattice problems in the ${\ell }_p$ norm: Bounded Distance Decoding to within an $\alpha$ factor of the minimum distance ($\mathrm{BDD}_{p…