41 citations · 83 across the 6 of their papers we have counts for
5 papers · 1 filter
Hardness of the (Approximate) Shortest Vector Problem: A Simple Proof via Reed-Solomon Codes
Huck Bennett, Chris Peikert
We give a simple proof that the (approximate, decisional) Shortest Vector Problem is $\NP$-hard under a randomiz…
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 norm: Bounded Distance Decoding to within an factor of the minimum distance ($\mathrm{BDD}_{p…
Hardness of Bounded Distance Decoding on Lattices in Norms
Huck Bennett, Chris Peikert
$ \newcommand{\Z}{\mathbb{Z}} \newcommand{\eps}{\varepsilon} \newcommand{\cc}[1]{\mathsf{#1}} \newcommand{\NP}{\cc{NP}} \newcommand{\problem}[1]{\mathrm{#1}} \newcommand{\BDD}{\pro…
On the Lattice Smoothing Parameter Problem
Kai-Min Chung, Daniel Dadush, Feng-Hao Liu +1
The smoothing parameter of a Euclidean lattice , introduced by Micciancio and Regev (FOCS'04; SICOMP'07), is (informally) the smallest amount of Gau…
Classical Hardness of Learning with Errors
Zvika Brakerski, Adeline Langlois, Chris Peikert +2
We show that the Learning with Errors (LWE) problem is classically at least as hard as standard worst-case lattice problems, even with polynomial modulus. Previously this was only…