41 citations · 54 across the 19 of their papers we have counts for
5 papers · 1 filter
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.…
Scalable Pseudorandom Quantum States
Zvika Brakerski, Omri Shmueli
Efficiently sampling a quantum state that is hard to distinguish from a truly random quantum state is an elementary task in quantum information theory that has both computational a…