175 citations · 262 across the 24 of their papers we have counts for
25 papers
Undetectable Conversations Between AI Agents via Pseudorandom Noise-Resilient Key Exchange
Vinod Vaikuntanathan, Or Zamir
AI agents are increasingly deployed to interact with other agents on behalf of users and organizations. We ask whether two such agents, operated by different entities, can carry ou…
Separating Quantum and Classical Advice with Good Codes
John Bostanci, Andrew Huang, Vinod Vaikuntanathan
We show an unconditional classical oracle separation between the class of languages that can be verified using a quantum proof () and the class of languages that can…
A Simple and Efficient One-Shot Signature Scheme
Andrew Huang, Vinod Vaikuntanathan
One-shot signatures (OSS) are a powerful and uniquely quantum cryptographic primitive which allows anyone, given common reference string, to come up with a public verification key…
Improving Algorithmic Efficiency using Cryptography
Vinod Vaikuntanathan, Or Zamir
Cryptographic primitives have been used for various non-cryptographic objectives, such as eliminating or reducing randomness and interaction. We show how to use cryptography to imp…
A system capable of verifiably and privately screening global DNA synthesis
Carsten Baum, Jens Berlips, Walther Chen +28
Printing custom DNA sequences is essential to scientific and biomedical research, but the technology can be used to manufacture plagues as well as cures. Just as ink printers recog…
Quantum State Obfuscation from Classical Oracles
James Bartusek, Zvika Brakerski, Vinod Vaikuntanathan
A major unresolved question in quantum cryptography is whether it is possible to obfuscate arbitrary quantum computation. Indeed, there is much yet to understand about the feasibil…
Space-Efficient and Noise-Robust Quantum Factoring
Seyoon Ragavan, Vinod Vaikuntanathan
We provide two improvements to Regev's recent quantum factoring algorithm (Journal of the ACM 2025), addressing its space efficiency and its noise-tolerance. Our first contribution…
PEOPL: Characterizing Privately Encoded Open Datasets with Public Labels
Homa Esfahanizadeh, Adam Yala, Rafael G. L. D'Oliveira +8
Allowing organizations to share their data for training of machine learning (ML) models without unintended information leakage is an open problem in practice. A promising technique…
Revocable Cryptography from Learning with Errors
Prabhanjan Ananth, Alexander Poremba, Vinod Vaikuntanathan
Quantum cryptography leverages many unique features of quantum information in order to construct cryptographic primitives that are oftentimes impossible classically. In this work,…
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…
Does Fully Homomorphic Encryption Need Compute Acceleration?
Leo de Castro, Rashmi Agrawal, Rabia Yazicigil +4
Fully Homomorphic Encryption (FHE) allows arbitrarily complex computations on encrypted data without ever needing to decrypt it, thus enabling us to maintain data privacy on third-…
NeuraCrypt: Hiding Private Health Data via Random Neural Networks for Public Training
Adam Yala, Homa Esfahanizadeh, Rafael G. L. D' Oliveira +6
Balancing the needs of data privacy and predictive utility is a central challenge for machine learning in healthcare. In particular, privacy concerns have led to a dearth of public…
The Fine-Grained Hardness of Sparse Linear Regression
Aparna Gupte, Vinod Vaikuntanathan
Sparse linear regression is the well-studied inference problem where one is given a design matrix and a response vector $\mathbf{b} \in \mat…
Oblivious Transfer is in MiniQCrypt
Alex B. Grilo, Huijia Lin, Fang Song +1
MiniQCrypt is a world where quantum-secure one-way functions exist, and quantum communication is possible. We construct an oblivious transfer (OT) protocol in MiniQCrypt that achie…
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 -…
Data Structures Meet Cryptography: 3SUM with Preprocessing
Alexander Golovnev, Siyao Guo, Thibaut Horel +2
This paper shows several connections between data structure problems and cryptography against preprocessing attacks. Our results span data structure upper bounds, cryptographic app…
Computational Limitations in Robust Classification and Win-Win Results
Akshay Degwekar, Preetum Nakkiran, Vinod Vaikuntanathan
We continue the study of statistical/computational tradeoffs in learning robust classifiers, following the recent work of Bubeck, Lee, Price and Razenshteyn who showed examples of…
How to Subvert Backdoored Encryption: Security Against Adversaries that Decrypt All Ciphertexts
Thibaut Horel, Sunoo Park, Silas Richelson +1
We study secure and undetectable communication in a world where governments can read all encrypted communications of citizens. We consider a world where the only permitted communic…
Gazelle: A Low Latency Framework for Secure Neural Network Inference
Chiraag Juvekar, Vinod Vaikuntanathan, Anantha Chandrakasan
The growing popularity of cloud-based machine learning raises a natural question about the privacy guarantees that can be provided in such a setting. Our work tackles this problem…