41 citations · 83 across the 6 of their papers we have counts for
11 papers
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…
F1: A Fast and Programmable Accelerator for Fully Homomorphic Encryption (Extended Version)
Axel Feldmann, Nikola Samardzic, Aleksandar Krastev +6
Fully Homomorphic Encryption (FHE) allows computing on encrypted data, enabling secure offloading of computation to untrusted serves. Though it provides ideal security, FHE is expe…
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…
Lattice (List) Decoding Near Minkowski's Inequality
Ethan Mook, Chris Peikert
Minkowski proved that any -dimensional lattice of unit determinant has a nonzero vector of Euclidean norm at most ; in fact, there are such lattice vectors.…
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…
Outsourcing Computation: the Minimal Refereed Mechanism
Yuqing Kong, Chris Peikert, Grant Schoenebeck +1
We consider a setting where a verifier with limited computation power delegates a resource intensive computation task---which requires a computation tableau---to two pr…