175 citations · 262 across the 24 of their papers we have counts for
6 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-…
FAB: An FPGA-based Accelerator for Bootstrappable Fully Homomorphic Encryption
Rashmi Agrawal, Leo de Castro, Guowei Yang +5
FHE offers protection to private data on third-party cloud servers by allowing computations on the data in encrypted form. However, to support general-purpose encrypted computation…
Succinct Classical Verification of Quantum Computation
James Bartusek, Yael Tauman Kalai, Alex Lombardi +5
We construct a classically verifiable succinct interactive argument for quantum computation (BQP) with communication complexity and verifier runtime that are poly-logarithmic in th…
Planting Undetectable Backdoors in Machine Learning Models
Shafi Goldwasser, Michael P. Kim, Vinod Vaikuntanathan +1
Given the computational cost and technical expertise required to train machine learning models, users may delegate the task of learning to a service provider. We show how a malicio…
Continuous LWE is as Hard as LWE & Applications to Learning Gaussian Mixtures
Aparna Gupte, Neekon Vafa, Vinod Vaikuntanathan
We show direct and conceptually simple reductions between the classical learning with errors (LWE) problem and its continuous analog, CLWE (Bruna, Regev, Song and Tang, STOC 2021).…
Quantum Advantage from Any Non-Local Game
Yael Kalai, Alex Lombardi, Vinod Vaikuntanathan +1
We show a general method of compiling any -prover non-local game into a single-prover interactive game maintaining the same (quantum) completeness and (classical) soundness guar…