About

Amit Sahai is a professor of computer science at the UCLA Samueli School of Engineering and the director of the Center for Encrypted Functionalities, a National Science Foundation Frontiers Center. His research interests are in the foundations of computer security and cryptography, with particular focus on hiding secrets in software, secure program obfuscation, cryptographic proofs, and secure multiparty computation. Sahai is a co-inventor of attribute-based encryption, functional encryption, and indistinguishability obfuscation. He holds the Symantec Endowed Chair in Computer Science and has been recognized as a Simons Investigator and Fellow of the Royal Society of Arts, ACM, and IACR. Prior to UCLA, he was on the faculty at Princeton University, and he earned his Ph.D. from MIT in 2000. Sahai has published over 150 technical research papers and serves as an editor for the Journal of Cryptology. His work has been widely covered in the media, and he has received numerous awards for his contributions to cryptography and computer security.

Research topics

• Computer Science
• Computer Security
• Programming language
• Artificial Intelligence
• Theoretical computer science
• Mathematics
• Discrete mathematics
• Operating system
• Algorithm

Selected publications

• Continued fractions with telescoping periods

  Combinatorics and Number Theory · 2026-05-10

  articleSenior author
  PublisherDOI

• Using the Planted Clique Conjecture for Cryptography: Public-Key Encryption from Planted Clique and Noisy 𝑘-LIN over Expanders

  2025-06-15

  articleSenior author
  PublisherDOI

• Sandcastles in the Storm: Revisiting the (Im)possibility of Strong Watermarking

  ArXiv.org · 2025-05-11

  preprintOpen accessSenior author

  Watermarking AI-generated text is critical for combating misuse. Yet recent theoretical work argues that any watermark can be erased via random walk attacks that perturb text while preserving quality. However, such attacks rely on two key assumptions: (1) rapid mixing (watermarks dissolve quickly under perturbations) and (2) reliable quality preservation (automated quality oracles perfectly guide edits). Through large-scale experiments and human-validated assessments, we find mixing is slow: 100% of perturbed texts retain traces of their origin after hundreds of edits, defying rapid mixing. Oracles falter, as state-of-the-art quality detectors misjudge edits (77% accuracy), compounding errors during attacks. Ultimately, attacks underperform: automated walks remove watermarks just 26% of the time -- dropping to 10% under human quality review. These findings challenge the inevitability of watermark removal. Instead, practical barriers -- slow mixing and imperfect quality control -- reveal watermarking to be far more robust than theoretical models suggest. The gap between idealized attacks and real-world feasibility underscores the need for stronger watermarking methods and more realistic attack models.

  PublisherOA PDFDOI

• Quantum Advantage via Solving Multivariate Polynomials

  ArXiv.org · 2025-09-08

  preprintOpen accessSenior author

  In this work, we propose a new way to (non-interactively, verifiably) demonstrate quantum advantage by solving the average-case $\mathsf{NP}$ search problem of finding a solution to a system of (underdetermined) constant degree multivariate equations over the finite field $\mathbb{F}_2$ drawn from a specified distribution. In particular, for any $d \geq 2$, we design a distribution of degree up to $d$ polynomials $\{p_i(x_1,\ldots,x_n)\}_{i\in [m]}$ for $m 2$, it is classically hard to find one based on a thorough review of existing classical cryptanalysis. Our work thus posits that degree three functions are enough to instantiate the random oracle to obtain non-relativized quantum advantage. Our approach begins with the breakthrough Yamakawa-Zhandry (FOCS 2022) quantum algorithmic framework. In our work, we demonstrate that this quantum algorithmic framework extends to the setting of multivariate polynomial systems. Our key technical contribution is a new analysis on the Fourier spectra of distributions induced by a general family of distributions over $\mathbb{F}_2$ multivariate polynomials -- those that satisfy $2$-wise independence and shift-invariance. This family of distributions includes the distribution of uniform random degree at most $d$ polynomials for any constant $d \geq 2$. Our analysis opens up potentially new directions for quantum cryptanalysis of other multivariate systems.

  PublisherOA PDFDOI

• Post-quantum PKE from Unstructured Noisy Linear Algebraic Assumptions: Beyond LWE and Alekhnovich’s LPN

  Lecture notes in computer science · 2025-01-01

  book-chapter
  PublisherDOI

• Indistinguishability Obfuscation from Well-Founded Assumptions

  Journal of the ACM · 2025-12-12 · 20 citations

  preprintOpen accessSenior author

  Indistinguishability obfuscation, introduced by [Barak et. al. Crypto’2001], aims to compile programs into unintelligible ones while preserving functionality. It is a fascinating and powerful object that has been shown to enable a host of new cryptographic goals and beyond. However, constructions of indistinguishability obfuscation have remained elusive, with all other proposals relying on heuristics or newly conjectured hardness assumptions. In this work, we show how to construct indistinguishability obfuscation from subexponential hardness of four well-founded assumptions. We prove: Suppose there exists any set of constants \(\tau \in (0,\infty), \delta \in (0,1), \epsilon \in (0,1)\) such that the sub-exponential security of the following assumptions hold: — the Learning With Errors ( \(\mathsf {LWE}\) ) assumption with subexponential modulus-to-noise ratio \(2^{k^\epsilon }\) and noises of magnitude polynomial in k , where k is the dimension of the \(\mathsf {LWE}\) secret, — the Learning Parity with Noise ( \(\mathsf {LPN}\) ) assumption over general prime fields \(\mathbb {Z}_p\) with polynomially many \(\mathsf {LPN}\) samples and error rate \(1/\ell ^\delta\) , where \(\ell\) is the dimension of the \(\mathsf {LPN}\) secret, — the existence of a Boolean Pseudo-Random Generator ( \(\mathsf {PRG}\) ) in \(\mathsf {NC}^0\) with stretch \(n^{1+\tau }\) , where n is the length of the \(\mathsf {PRG}\) seed, — the Decision Linear ( \(\mathsf {DLIN}\) ) assumption on symmetric bilinear groups of prime order. Then, (subexponentially secure) indistinguishability obfuscation for all polynomial-size circuits exists. Furthermore, assuming only polynomial security of the aforementioned assumptions, there exists collusion resistant public-key functional encryption for all polynomial-size circuits.

  PublisherOA PDFDOI

• Adaptively Secure Streaming Functional Encryption

  Lecture notes in computer science · 2025-12-01

  book-chapterOpen accessSenior author
  PublisherOA PDFDOI

• Dynamic Bounded-Collusion Streaming Functional Encryption from Minimal Assumptions

  Lecture notes in computer science · 2025-01-01 · 1 citations

  book-chapterSenior author
  PublisherDOI

• Sandcastles in the Storm: Revisiting the (Im)possibility of Strong Watermarking

  2025-01-01

  articleOpen accessSenior author

  Fabrice Y Harel-Canada, Boran Erol, Connor Choi, Jason Liu, Gary Jiarui Song, Nanyun Peng, Amit Sahai. Proceedings of the 63rd Annual Meeting of the Association for Computational Linguistics (Volume 1: Long Papers). 2025.

  PublisherOA PDFDOI

• SVP$_p$ is Deterministically NP-Hard for all $p > 2$, Even to Approximate Within a Factor of $2^{\log^{1-\varepsilon} n}$

  ArXiv.org · 2025-11-06

  preprintOpen accessSenior author

  We prove that SVP$_p$ is NP-hard to approximate within a factor of $2^{\log^{1 - \varepsilon} n}$, for all constants $\varepsilon > 0$ and $p > 2$, under standard deterministic Karp reductions. This result is also the first proof that \emph{exact} SVP$_p$ is NP-hard in a finite $\ell_p$ norm. Hardness for SVP$_p$ with $p$ finite was previously only known if NP $\not \subseteq$ RP, and under that assumption, hardness of approximation was only known for all constant factors. As a corollary to our main theorem, we show that under the Sliding Scale Conjecture, SVP$_p$ is NP-hard to approximate within a small polynomial factor, for all constants $p > 2$. Our proof techniques are surprisingly elementary; we reduce from a \emph{regularized} PCP instance directly to the shortest vector problem by using simple gadgets related to Vandermonde matrices and Hadamard matrices.

  PublisherOA PDFDOI

Recent grants

• ITR: New Directions in Software Security

  NSF · $374k · 2004–2008

• TC: Small: New Directions in Encryption

  NSF · $495k · 2011–2015

• CT-ISG: New Directions in Cryptographic Proof Systems

  NSF · $350k · 2006–2010

• TWC: Medium: Collaborative Research: Transformative New Approaches to Efficient Secure Computation

  NSF · $600k · 2012–2017

• AF: Small: A Theory of Cryptography and the Physical World

  NSF · $400k · 2009–2013

Frequent coauthors

• Yuval Ishai

  72 shared

• Brent Waters

  61 shared

• Aayush Jain

  50 shared

• Vipul Goyal

  Regional Cancer Center, Thiruvananthapuram

  48 shared

• Rafail Ostrovsky

  44 shared

• Manoj Prabhakaran

  Dhanalakshmi Srinivasan Group of Institutions

  39 shared

• Dakshita Khurana

  37 shared

• Abhishek Jain

  Johns Hopkins University

  31 shared

Education

• Ph.D., Computer Science

  Massachusetts Institute of Technology (MIT)

  2000

• B.S.

  Princeton University

Awards & honors

• Simons Investigator Award (2021)
• Fellow of the Royal Society of Arts (2021)
• Fellow of the ACM (2018)
• Fellow of the IACR (2019)
• Alfred P. Sloan Foundation Research Fellow (2002)