41 citations · 54 across the 19 of their papers we have counts for
3 papers · 1 filter
Lattice Problems Beyond Polynomial Time
Divesh Aggarwal, Huck Bennett, Zvika Brakerski +6
We study the complexity of lattice problems in a world where algorithms, reductions, and protocols can run in superpolynomial time, revisiting four foundational results: two worst-…
On the Hardness of Average-case k-SUM
Zvika Brakerski, Noah Stephens-Davidowitz, Vinod Vaikuntanathan
In this work, we show the first worst-case to average-case reduction for the classical -SUM problem. A -SUM instance is a collection of integers, and the goal of the -…
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…