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 $\hat{I}\pm$ factor of the minimum distance ($\mathrm{BDD}_{…