2 citations · 3 across the 2 of their papers we have counts for
9 papers
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-…
Constructive Post-Quantum Reductions
Nir Bitansky, Zvika Brakerski, Yael Tauman Kalai
Is it possible to convert classical cryptographic reductions into post-quantum ones? It is customary to argue that while this is problematic in the interactive setting, non-interac…
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 -…
Quantum Garbled Circuits
Zvika Brakerski, Henry Yuen
We present a garbling scheme for quantum circuits, thus achieving a decomposable randomized encoding scheme for quantum computation. Specifically, we show how to compute an encodin…
Simpler Proofs of Quantumness
Zvika Brakerski, Venkata Koppula, Umesh Vazirani +1
A proof of quantumness is a method for provably demonstrating (to a classical verifier) that a quantum device can perform computational tasks that a classical device with comparabl…
Impossibility of Quantum Virtual Black-Box Obfuscation of Classical Circuits
Gorjan Alagic, Zvika Brakerski, Yfke Dulek +1
Virtual black-box obfuscation is a strong cryptographic primitive: it encrypts a circuit while maintaining its full input/output functionality. A remarkable result by Barak et al.…