Join us for weekly talks on cryptography organized by Yael Kalai and Vinod Vaikuntanathan.
If you would like to be on the mailing list for this seminar series, please contact Meenu Tiwari.
đ Where: Stata Center Room 32G-882
đ When: Fridays 10:30-noon
Fall 2025
Breaking Verifiable Delay Functions in the Random Oracle Model
Ziyi Guan (EPFL)
September 5, 2025
A VDF is a cryptographic primitive that requires a long time to compute (even with parallelization), but produces a unique output that is efficiently and publicly verifiable. We prove that VDFs do not exist in the random oracle model. This also rules out black-box constructions of VDFs from other cryptographic primitives, such as one-way functions, one-way permutations and collision-resistant hash functions.
Succinct Witness Encryption for Batch Languages and Applications
Lalita Devadas (MIT)
September 12, 2025
Witness encryption allows one to encrypt a message to an NP relation $R$ and a statement $x$. The corresponding decryption key is any valid NP witness $w$. In a succinct witness encryption scheme, we require that the size of the ciphertext be sublinear in the size of the NP relation. Prior to this work, all realizations of succinct witness encryption for NP rely on strong assumptions such as pseudorandom obfuscation, extractable witness encryption, or differing-inputs obfuscation. Notably, none of these notions are known from standard assumptions.
We consider a relaxation of succinct witness encryption for NP to the setting of batch NP. In this setting, one encrypts to an NP relation $R$ together with $K$ statements $x_1, ... , x_K$. In the basic version, one can decrypt if they have a witness $w_1, \ldots , w_K$ for all $K$ statements. The succinctness requirement is that the size of the ciphertext should be sublinear in the number of instances $K$, but is allowed to grow with the size of the NP relation (i.e., the size of a single instance). More generally, we can also impose a (monotone) policy $P : \{0,1\}^K \to \{0,1\}$ over the $K$ instances. In this case, decryption is possible only if there exists $w_1, \ldots , w_K$ such that $P(R(x_1, w_1), ... , R(x_K, w_K)) = 1$.
In this work, we initiate a systematic study of succinct witness encryption for batch languages. We start with two simple constructions that support CNF and DNF policies based on plain witness encryption in conjunction with a somewhere statistically sound batch argument for NP or a function-binding hash function. Then, using indistinguishability obfuscation, we show how to support policies that can be computed by read-once bounded-space Turing machines. The latter construction is in fact a unique witness map for monotone-policy batch NP, and as such, also gives a SNARG for monotone-policy batch NP where the size of the common reference string is sublinear in the number of instances.
Finally, we demonstrate some immediate applications of succinct witness encryption for batch languages. We construct new succinct computational secret sharing schemes for CNFs, DNFs, and weighted threshold policies. We also show how to build distributed monotone-policy encryption, a notion that generalizes recent trustless primitives like distributed broadcast encryption and threshold encryption with silent setup.
Joint work with Abhishek Jain (NTT Research), Brent Waters (NTT Research and UT Austin), and David J. Wu (UT Austin).
How to Verify Any (Reasonable) Distribution Property: Computationally Sound Argument Systems for Distributions
Tal Herman (UC Berkeley)
September 19, 2025
As statistical analyses become increasingly central, there is a growing need to ensure their results are correct. Approximate correctness can be verified by replicating the entire analysis, but can we verify without replication? We focus on distribution testing problems: given samples from an unknown distribution, the goal is verifying that the distribution is close to having a claimed property. Our main contribution is an interactive protocol between a verifier and an untrusted prover who both have sampling access to the unknown distribution. Our protocol can be used to verify a very rich class of properties: the only requirement is that, given a full and explicit description of a distribution, it should be possible to approximate its distance from the property in polynomial time. For any such property, if the distribution is at statistical distance $\varepsilon$ from having the property, then the verifier rejects with high probability. This soundness property holds against any polynomial-time strategy that a cheating prover might follow, assuming the existence of collision-resistant hash.
For distributions over a domain of size $N$, the protocol consists of $4$ messages and the communication complexity and verifier runtime are roughly $\widetilde{O}\left(\sqrt{N} / \varepsilon^2 \right)$. The verifier's sample complexity is $\widetilde{O}\left(\sqrt{N} / \varepsilon^2 \right)$, and this is optimal up to $\mathsf{polylog}(N)$ factors (for any protocol, regardless of its communication complexity).
Even for simple properties, approximately deciding whether an unknown distribution has the property can require quasi-linear sample complexity and running time. For any such property, our protocol provides a quadratic speedup over replicating the analysis.
TBD
Liyan Chen (MIT)
September 26, 2025
TBD
No Seminar
Theory Student Retreat
October 3, 2025
TBD
Rahul Ilango (IAS)
October 24, 2025
TBD
TBD
Alexandra Henzinger (MIT)
November 7, 2025
TBD
Charles River Crypto Day
November 14, 2025
TBD
Mi-Ying Miriam Huang (USC)
November 21, 2025
TBD
Spring 2025
Near-Optimal Time-Sparsity Trade-Offs for Solving Noisy Linear Equations
Kiril Bangachev (MIT EECS)
February 21, 2025
We present a polynomial-time reduction from solving noisy linear equations over a finite field F with a uniformly random coefficient matrix to noisy linear equations over F where each row of the coefficient matrix has uniformly random support of size k. This allows us to deduce the hardness of sparse problems from their dense counterparts. In particular, under popular cryptographic assumptions, we demonstrate that learning with errors and learning parity with noise with uniformly random k-sparse public matrices in dimension n are hard in time n^o(k). These results are nearly tight as both sparse problems can be solved in time n^k given sufficiently many samples.
Our reduction allows us to derive several consequences in cryptography and the computational complexity of statistical problems. In addition, as a new application, we give a reduction from k-sparse LWE to noisy tensor completion of a low-rank order-k tensor. As a result, we obtain a nearly optimal lower bound for the problem based on standard lattice-theoretic assumptions.
This talk is based on a joint work with Stefan Tiegel, Vinod Vaikuntanathan, and Guy Bresler.
Recursive lattice reduction â A simple framework for finding short lattice vectors
Noah Stephens-Davidowitz (Cornell University)
March 7, 2025
We'll present a new framework called recursive lattice reduction for finding short non-zero vectors in a lattice. This gives new algorithms for solving the computational problem whose hardness underlies the security of lattice-based cryptography. These new algorithms are much simpler than prior work, and they provably match the state of the art. The analysis of the algorithms is also quite simple, and in particular, the analysis provides a much clearer explanation of why the algorithms perform as they do (i.e., the amount of time needed for these algorithms to find vectors of a given length, which is the key quantity that governs the security of lattice-based cryptography in practice).
The framework is based entirely on the following idea: in order to find a short non-zero vector in an $n$-dimensional lattice, one should first find a dense $\ell$-dimensional sublattice for some $\ell < n$ and then recursively solve the $\ell$-dimensional problem of finding short non-zero vectors in this sublattice. After doing this repeatedly, we are eventually left with the problem of finding short non-zero vectors in a $k$-dimensional sublattice for $k$ small enough that we can simply find an optimal solution. One obtains a family of algorithms depending on how $k$ and $\ell$ are chosen.
This talk introduces BitGC, a computationally efficient rate-one garbling scheme based on ring-RLWE with key-dependent message security. The garbling consists of a SWHE-encrypted seed and one-bit per gate stitching information. The computation requires homomorphically expanding the seed using a low-depth PRG and then two additional levels of multiplication to assemble the garbled tables. As a result, it does not require bootstrapping operations needed for FHE.
Second, I will describe a rate-one constant-round active two-party computation protocol by authenticating BitGC. We show efficient ways to distributively garble BitGC and to authenticate its correctness. In practice, the total cost in addition to BitGC is sublinear for layered circuits and one bit per gate for generic circuits.
Finally, I will discuss some ongoing efforts and remarks on their concrete efficiency.
BitGC will appear in Eurocrypt 2025, available here. Authenticated BitGC is available here. Both results are joint work with Hanlin Liu, Kang Yang, and Yu Yu.
Thesis Defense: Succinct Cryptography via Propositional Proofs
Surya Mathialagan (MIT)
May 2, 2025
The goal in modern cryptography is to obtain security while minimizing the use of computational resources. In recent years, we have been incredibly successful in our pursuit for efficiency, even for cryptographic tasks that were thought to be âscience fictionâ. For example, we have constructions of fully homomorphic encryption and indistinguishability obfuscation for circuits from standard, falsifiable cryptographic assumptions.
However, there are still some tasks in cryptography where achieving the âidealâ efficiency from standard assumptions has evaded us. In this thesis, we study the problem of achieving efficiency in the form succinctness in two such settings:
* Can we construct succinct non-interactive arguments (SNARGs) for all of NP?
* Can we construct indistinguishability obfuscation (IO) for Turing machines? In particular, can we achieve an obfuscation size which is independent of the input length?
While the problems seem unrelated at first glance, the root difficulty seems to stem from a similar place: both primitives have non-falsifiable security notions. In fact, this type of barrier exists for many other cryptographic primitives, including witness encryption. This leads to a central question: how can we construct non-falsifiable primitives from falsifiable assumptions?
In this talk, we show how to leverage âpropositional proofsâ to overcome the non-falsifiability barrier, and make substantial progress in the goal of achieving succinctness in both of these settings. Our results include universal constructions of both SNARGs and IO for Turing machines from standard assumptions. We then show that these constructions are secure as long as there exists some construction for the respective primitive that has a âpropositional proofâ of its correctness property. We also demonstrate a general template for constructing adaptively sound SNARGs for NP, and give an instantiation via subexponential IO and LWE. We further apply our techniques to improve succinctness in other cryptographic settings such as secret sharing. Our results establish propositional proofs as a foundational tool for achieving succinctness across a broad range of cryptographic settings.
Quantum One-Time Programs, Revisited
Aparna Gupte (MIT)
May 9, 2025
One-time programs (Goldwasser, Kalai and Rothblum, CRYPTO 2008) are functions that can be run on any single input of a user's choice, but not on a second input. Classically, they are unachievable without trusted hardware, but the destructive nature of quantum measurements seems to provide a quantum path to constructing them. Unfortunately, Broadbent, Gutoski and Stebila showed that even with quantum techniques, a strong notion of one-time programs, similar to ideal obfuscation, cannot be achieved for any non-trivial quantum function. On the positive side, Ben-David and Sattath (Quantum, 2023) showed how to construct a one-time program for a certain (probabilistic) digital signature scheme, under a weaker notion of one-time program security. There is a vast gap between achievable and provably impossible notions of one-time program security, and it is unclear what functionalities are one-time programmable under the achievable notions of security.
In this work, we present new, meaningful, yet achievable definitions of one-time program security for probabilistic classical functions. We show how to construct one time programs satisfying these definitions for all functions in the classical oracle model and for constrained pseudorandom functions in the plain model. Finally, we examine the limits of these notions: we show a class of functions which cannot be one-time programmed in the plain model, as well as a class of functions which appears to be highly random given a single query, but whose one-time program form leaks the entire function even in the oracle model.
This talk is based on joint work with Jiahui Liu, Justin Raizes, Bhaskar Roberts and Vinod Vaikuntanathan.
Fall 2024
[TBD]
Crypto Day at MIT
September 13, 2024
Abstract placeholder: Add seminar abstract here.
Batching Adaptively-Sound SNARGs for NP
Lali Devadas (MIT)
September 20, 2024
A succinct non-interactive argument (SNARG) for NP allows a prover to convince a verifier that an NP statement is true with a proof whose size is sublinear in the length of its NP witness. Moreover, a SNARG is adaptively sound if the adversary can choose the statement it wants to prove after seeing the scheme's public parameters. Recently, Waters and Wu (STOC 2024) showed how to construct adaptively-sound SNARGs for NP in the plain model from falsifiable assumptions (specifically, sub-exponentially secure indistinguishability obfuscation, sub-exponentially secure one-way functions, and polynomial hardness of the discrete log assumption).
We consider the batch setting where the prover wants to certify a collection of statements and its goal is to construct a proof whose size is sublinear in both the size of a single witness and the number of statements. All existing adaptively-sound constructions either require the size of the public parameters to scale linearly with the number of statements or have proof size that scales linearly with the size of a single NP witness. In this work, we show that under the same set of assumptions as those underlying the Waters-Wu adaptively-sound SNARG, we can obtain an adaptively-sound SNARG for batch-NP where the size of the proof is poly(k) and the size of the public parameters is $\mathsf{poly}(k+|C|)$, where $k$ is a security parameter and $|C|$ is the size of the circuit that computes the associated NP relation.
We give two approaches for batching adaptively-sound SNARGs for NP. Our first approach builds directly on top of the Waters-Wu construction and relies on indistinguishability obfuscation and a homomorphic re-randomizable one-way function. Our second approach shows how to combine ideas from the Waters-Wu SNARG with the chaining-based approach by Garg, Sheridan, Waters, and Wu (TCC 2022) and avoids relying on a structure like homomorphism.
Joint work with Brent Waters (UT Austin and NTT Research) and David J. Wu (UT Austin).
Indistinguishability Obfuscation from Bilinear Maps and LPN Variants
Seyoon Ragavan (MIT)
September 27, 2024
We construct an indistinguishability obfuscation (IO) scheme from the sub-exponential hardness of the decisional linear problem on bilinear groups together with two variants of the learning parity with noise (LPN) problem, namely large-field LPN and (binary-field) sparse LPN. This removes the need to assume the existence pseudorandom generators (PRGs) in $\mathsf{NC}^0$ with polynomial stretch from the state-of-the-art construction of IO (Jain, Lin, and Sahai, EUROCRYPT 2022). As an intermediate step in our construction, we abstract away a notion of structured-seed polynomial-stretch PRGs in $\mathsf{NC}^0$ which suffices for IO and is implied by both sparse LPN and the existence of polynomial-stretch PRGs in $\mathsf{NC}^0$.
As immediate applications, from the sub-exponential hardness of the decisional linear assumption on bilinear groups, large-field LPN, and sparse LPN, we get alternative constructions of (a) fully homomorphic encryption (FHE) without lattices or circular security assumptions (Canetti, Lin, Tessaro, and Vaikuntanathan, TCC 2015), and (b) perfect zero-knowledge adaptively-sound succinct non-interactive arguments (SNARGs) for NP (Waters and Wu, STOC 2024).
Joint work with Neekon Vafa (MIT) and Vinod Vaikuntanathan (MIT).
Simple Constructions of Linear-Depth $t$-Designs and Pseudorandom Unitaries
Alexander Poremba (MIT)
October 11, 2024
Uniformly random unitaries, i.e. unitaries drawn from the Haar measure, have many useful properties, but cannot be implemented efficiently. This has motivated a long line of research into random unitaries that "look" sufficiently Haar random while also being efficient to implement. Two different notions of derandomisation have emerged: $t$-designs are random unitaries that information-theoretically reproduce the first $t$ moments of the Haar measure, and pseudorandom unitaries (PRUs) are random unitaries that are computationally indistinguishable from Haar random. In this work, we take a unified approach to constructing $t$-designs and PRUs. For this, we introduce and analyse the "PFC ensemble", the product of a random computational basis permutation P, a random binary phase operator F, and a random Clifford unitary C. We show that this ensemble reproduces exponentially high moments of the Haar measure. We can then derandomise the PFC ensemble to show the following:
(1) Linear-depth $t$-designs. We give the first construction of a (diamond-error) approximate $t$-design with circuit depth linear in $t$. This follows from the PFC ensemble by replacing the random phase and permutation operators with their $2t$-wise independent counterparts.
(2) Non-adaptive PRUs. We give the first construction of PRUs with non-adaptive security, i.e. we construct unitaries that are indistinguishable from Haar random to polynomial-time distinguishers that query the unitary in parallel on an arbitary state. This follows from the PFC ensemble by replacing the random phase and permutation operators with their pseudorandom counterparts.
(3) Adaptive pseudorandom isometries. We show that if one considers isometries (rather than unitaries) from $n$ to $n+\omega(\log n)$ qubits, a small modification of our PRU construction achieves general adaptive security.
This is based on joint work with Tony Metger (ETH Zurich), Makrand Sinha (UIUC) and Henry Yuen (Columbia).
More Efficient Approximate $k$-wise Independent Permutations
Angelos Pelecanos (UC Berkeley)
November 1, 2024
We prove that the permutation computed by a reversible circuit with $\widetilde{O}(nk\cdot \log(1/\epsilon))$ random $3$-bit gates is $\epsilon$-approximately $k$-wise independent.
Our bound improves on currently known bounds in the regime when the approximation error $\epsilon$ is not too small and is optimal up to logarithmic factors when $\epsilon$ is a constant. We obtain our results by analyzing the log-Sobolev constants of appropriate Markov chains rather than their spectral gaps.
A corollary of our result concerns the incompressibility of random reversible circuits as pointed out by concurrent work of Chen et al., who showed that a linear-in-$k$ bound for a multiplicative approximation to a $k$-wise independent permutation implies the linear growth of circuit complexity (a generalization of Shannon's argument).
Error Detection and Correction in a Computationally Bounded World
Daniel Wichs (Northeastern)
November 8, 2024
We study error detection and error correction in a computationally bounded world, where errors are introduced by an arbitrary polynomial time adversarial channel. To take advantage of this restriction, we consider randomized codes that rely on a public random seed and consider different variants depending on (1) whether the seed needs to be known only to the encoder (self-seeded) or to both the encoder and decoder (seeded), (2) whether the adversary can choose the messages being encoded adaptively depending on the seed or only selectively ahead of time.
In the case of a large constant-size alphabet we essentially give a complete characterization of such codes. Recall that the parameters of standard codes for worst-case (inefficient) errors are limited by the Singleton bound: for rate $R$ it is not possible to detect more than a $1-R$ fraction of errors, or uniquely correct more than a $(1-R)/2$ fraction of errors. In the computationally bounded setting, we show that going beyond the Singleton bound implies one-way functions for selective security or collision-resistant hash functions for adaptive. We construct self-seeded codes under these respective minimal assumptions with essentially optimal parameters:
* Detection: the codes have a rate $R \approx 1$ while detecting a $\rho \approx 1$ fraction of errors.
* Correction: for any $\rho < 1/2$, the codes uniquely correct a $\rho$ fraction of errors with rate $R \approx 1-\rho$.
In the case of the binary alphabet, we construct selectively secure seeded codes under LWE. For error detection, our codes achieve essentially optimal rate $R \approx 1$ and relative error tolerance $\rho \approx 1/2$. For error correction, they can uniquely correct $\rho < 1/4$ relative errors with a rate $R$ that essentially matches that of the best list-decodable codes with error tolerance $\rho$. We also construct adaptively secure seeded codes with similar parameters based on a "crypto dark matter" hardness assumption that mixes linear functions over different moduli. Giving a full characterization of what parameters are possible and under what assumptions in the binary alphabet setting remains as a fascinating open problem.
Based on joint works with Jad Silbak.
Spring 2024
Unconditionally secure quantum commitments with preprocessing
Luowen Qian (Boston University)
February 16, 2024
Abstract placeholder: Add seminar abstract here.
Adaptively Sound Zero-Knowledge SNARKs for UP
Surya Mathialagan (MIT EECS)
March 15, 2024
Abstract placeholder: Add seminar abstract here.
Learning from Nisan's natural proofs
Ari Karchmer (Boston University)
March 22, 2024
Abstract placeholder: Add seminar abstract here.
Lattice-Based SNARKs: Publicly Verifiable, Preprocessing, and Recursively Composable
Valerio Cini (NTT Research)
April 5, 2024
Abstract placeholder: Add seminar abstract here.
How to Construct Quantum FHE, Generically
Aparna Gupte (MIT)
May 3, 2024
Abstract placeholder: Add seminar abstract here.
Fall 2023
Binary Error-Correcting Codes with Minimal Noiseless Feedback