Back to Events

Seminar Series

December 05

Multi-Key Homomorphic Secret Sharing: From Theory To Practice

Kevin He (MIT) and Lali Devadas (MIT)

Part Of

10:30A
- 12:00P

Location

32-D463
STAR
Add to Calendar 2025-12-05 10:30:00 2025-12-05 12:00:00 America/New_York Multi-Key Homomorphic Secret Sharing: From Theory To Practice Homomorphic secret sharing (HSS) enables efficient, low-communication secure computation without the use of fully homomorphic encryption. In all existing HSS schemes, parties participate in a correlated setup phase or a public-key infrastructure, then exchange shares of their inputs and perform local computations to obtain additive shares of the output.In the first part of the talk, we define multi-key homomorphic secret sharing (MKHSS), which replaces the setup in HSS with only a common reference string, and construct MKHSS for NC1 circuits from the decisional composite residuosity (DCR) assumption. This implies the first realization of succinct two-round secure computation for NC1 circuits without lattice-based assumptions.In the second part of the talk, we present optimizations to speed up the MKHSS construction by 45x. Crucial to this speedup is an insight that reduces the largest modulus from N^4 to N^2. As a bonus, we discover a structural simplification that is of independent interest to other HSS schemes.A practical application of MKHSS is a non-interactive conditional key exchange protocol, where two parties obtain the same key only if their inputs satisfy some predicate, which can be an arbitrary branching program. We give practical instantiations for two concrete predicates—geolocation proximity and fuzzy password matching—and achieve a total running time in a few seconds for realistic parameters.Joint works with Geoffroy Couteau (Université Paris Cité, CNRS, IRIF), Srini Devadas (MIT), Aditya Hedge (Johns Hopkins University), Abhishek Jain (Johns Hopkins University and NTT Research), and Sacha Servan-Schreiber (Tinfoil). TBD

November 21

Two-Server Private Information Retrieval in Sublinear Time and Quasilinear Space

Alexandra Henzinger & Seyoon Ragavan
MIT

Part Of

10:30A
- 12:00P

Location

32-G882
Add to Calendar 2025-11-21 10:30:00 2025-11-21 12:00:00 America/New_York Two-Server Private Information Retrieval in Sublinear Time and Quasilinear Space In this talk, we build two-server private information retrieval (PIR) that achieves information-theoretic security and strong double-efficiency guarantees. On a database of n > 10^6 bits, the servers store a preprocessed data structure of size 1.5 * sqrt(log n) * n bits and then answer each PIR query by probing 12 n^0.82 bits in this data structure. To our knowledge, this is the first information-theoretic PIR with any constant number of servers that has quasilinear server storage n^{1 + o(1)} and polynomially sublinear server time n^{1 - \Omega(1)}. We describe connections to new data structures and locally decodable codes.Joint work with Seyoon Ragavan (eprint.iacr.org/2025/2008). TBD

November 14

Charles River Crypto Day @ MIT (STAR ROOM D463)

Jad Silbak(MIT), Saroja Erabelli(NYU), Aparna Gupte(MIT), Jesko Dujmovic(BU and Northeastern)

Part Of

9:30A
- 4:00P

Location

32-D463
Add to Calendar 2025-11-14 9:30:00 2025-11-14 16:00:00 America/New_York Charles River Crypto Day @ MIT (STAR ROOM D463) When: Friday, November 14Where: MIT Stata Center, Star Room (D463)Organizers: Ran Canetti, Henry Corrigan-Gibbs, Yael Kalai, Eran Tromer, Vinod Vaikuntanathan and Daniel WichsProgram :9:30am–10:00am: Coffee/Welcome 10:00am - 11:00am: Jad Silbak (MIT)"Extractors for Samplable Distributions with Low Min-Entropy"11:30am - 12:30pm: Saroja Erabelli (NYU)"Shuffling is Universal: Statistical Additive Randomized Encodings for All Functions"12:30pm - 1:30pm: Lunch (provided)1:30pm - 2:30pm: Aparna Gupte (MIT)"Classical Obfuscation of Quantum Circuits via Publicly-Verifiable QFHE"3:00pm - 4:00pm: Jesko Dujmovic (BU and Northeastern)"When Simple Permutations Mix Poorly: Limited Independence Does Not Imply Pseudorandomness"*****Abstracts for hour long talks*****Title: Extractors for Samplable Distributions with Low Min-EntropySpeaker: Jad SilbakAbstract: Trevisan and Vadhan (FOCS 2000) introduced the notion of seedless extractors for samplable distributions—that is, deterministic extractors for sources that can be generated by an efficient sampling algorithm.They showed that, under strong complexity theoretic (derandomization) hardness assumption, there are extractors for samplable distributions with large min-entropy of 𝑘 = (1 − 𝛾) · 𝑛, for some small constant 𝛾>0. Recent work by Ball, Goldin, Dachman-Soled and Mutreja (FOCS 2023) weakened the hardness assumption. However, since the original paper by Trevisan and Vadhan, there has been no improvement in the min-entropy threshold 𝑘.In this talk, I will survey recent developments on this problem. In particular, I will present a construction for samplable distributions with low min-entropy of 𝑘 = 𝑛^{1−𝛾} for some constant 𝛾>0, achieving 𝑘<𝑛/2 (which is a barrier for the construction of Trevisan and Vadhan).Our approach builds on the technique of Trevisan and Vadhan, while introducing new objects and ideas. We introduce and construct two objects: an errorless (seedless) condenser for samplable distributions, and functions that are hard to compute on every samplable distribution with sufficient min-entropy. We use techniques by Shaltiel and Silbak (STOC 2024), as well as additional tools and ideas, to construct the two new objects, under hardness assumptions. We then show how to modify the construction of Trevisan and Vadhan, using these new objects, so that the barrier of 𝑘=𝑛/2 can be bypassed, and we can achieve an extractor for samplable distributions with low min-entropy.This is a joint work with Marshall Ball and Ronen Shaltiel.Title: Shuffling is Universal: Statistical Additive Randomized Encodings for All FunctionsSpeaker: Saroja ErabelliAbstract: The shuffle model is a widely used abstraction for non-interactive anonymous communication. It allows $n$ parties holding private inputs $x_1,\dots,x_n$ to simultaneously send messages to an evaluator, so that the messages are received in a random order. The evaluator can then compute a joint function $f(x_1,\dots,x_n)$, ideally while learning nothing else about the private inputs. The model has become increasingly popular both in cryptography, as an alternative to non-interactive secure computation in trusted setup models, and even more so in differential privacy, as an intermediate between the high-privacy, little-utility local model and the little-privacy, high-utility central curator model.The main open question in this context is which functions $f$ can be computed in the shuffle model with {\em statistical security.} While general feasibility results were obtained using public-key cryptography, the question of statistical security has remained elusive. The common conjecture has been that even relatively simple functions cannot be computed with statistical security in the shuffle model.We refute this conjecture, showing that all functions can be computed in the shuffle model with statistical security. In particular, any differentially private mechanism in the central curator model can also be realized in the shuffle model with essentially the same utility, and while the evaluator learns nothing beyond the central model result.This feasibility result is obtained by constructing a statistically secure additive randomized encoding (ARE) for any function. An ARE randomly maps individual inputs to group elements whose sum only reveals the function output. Similarly to other types of randomized encoding of functions, our statistical ARE is efficient for functions in $NC^1$ or $NL$. Alternatively, we get computationally secure ARE for all polynomial-time functions using a one-way function. More generally, we can convert any (information-theoretic or computational) “garbling scheme” to an ARE with a constant-factor size overhead.Joint work with Nir Bitansky, Rachit Garg, and Yuval Ishai.Title: Classical Obfuscation of Quantum Circuits via Publicly-Verifiable QFHESpeaker: Aparna GupteAbstract: A classical obfuscator for quantum circuits is a classical program that, given the classical description of a quantum circuit Q, outputs the classical description of a functionally equivalent quantum circuit Q’ that hides as much as possible about Q. Previously, the only known feasibility result for classical obfuscation of quantum circuits (Bartusek and Malavolta, ITCS 2022) was limited to “nul” security, which is only meaningful for circuits that always reject. On the other hand, if the obfuscator is allowed to compile the quantum circuit Q into a quantum state |Q’>, there exist feasibility results for obfuscating much more expressive classes of circuits: All pseudo-deterministic quantum circuits (Bartusek, Kitagawa, Nishimaki and Yamakawa, STOC 2023, Bartusek, Brakerski and Vaikuntanathan, STOC 2024), and even all unitaries (Huang and Tang, FOCS 2025).We show that (relative to a classical oracle) there exists a classical obfuscator for all pseudo-deterministic quantum circuits. As our main technical step, we give the first construction of a compact quantum fully-homomorphic encryption (QFHE) scheme that supports public verification of (pseudo-deterministic) quantum evaluation, relative to a classical oracle.To construct our QFHE scheme, we improve on an approach introduced by Bartusek, Kitagawa, Nishimaki and Yamakawa (STOC 2023), which previously required ciphertexts that are both quantum and non-compact due to a heavy use of quantum coset states and their publicly-verifiable properties. As part of our core technical contribution, we introduce new techniques for analyzing coset states that can be generated “on the fly”, by proving new cryptographic properties of the one-shot signature scheme of Shmueli and Zhandry (CRYPTO 2025). Our techniques allow us to produce QFHE ciphertexts that are purely classical, compact, and publicly-verifiable. This additionally yields the first classical verification of quantum computation protocol for BQP that simultaneously satisfies blindness and public-verifiability.Joint work with James Bartusek, Saachi Mutreja and Omri Shmueli.Title: When Simple Permutations Mix Poorly: Limited Independence Does Not Imply PseudorandomnessSpeaker: Jesko DujmovicAbstract: Over the past two decades, several works have used (almost) $k$-wise independence as a proxy property for block ciphers, since it guarantees resistance against broad classes of statistical attacks. For example, even the case $k = 2$ already implies security against differential and linear cryptanalysis. Hoory, Magen, Myers, and Rackoff (ICALP ’04; TCS ’05) formulated an appealing conjecture: if the sequential composition of $T$ independent local randomized permutations is (close to) four-wise independent, then it should also be a pseudorandom permutation. Here, “local” means that each output bit depends on only a constant number of input bits. This conjecture offers a potential strong justification for analyses of block ciphers that establish (almost) $k$-wise independence of this type of constructions. In this work, we disprove the conjecture in full generality by presenting an explicit local randomized permutation whose sequential composition is four-wise independent, but not a pseudorandom permutation. Our counterexample in fact extends to $k$-wise independence for any constant~$k$.Joint work with Angelos Pelecanos and Stefano Tessaro. TBD

November 07

Efficiently Batching Unambiguous Interactive Proofs

Rohan Goyal
MIT

Part Of

10:30A
- 12:00P

Location

32-G882
Add to Calendar 2025-11-07 10:30:00 2025-11-07 12:00:00 America/New_York Efficiently Batching Unambiguous Interactive Proofs We show that if a language $\mathcal{L}$ admits a public-coin unambiguous interactive proof (UIP) with round complexity $\ell$, where $a$ bits are communicated per round, then the \emph{batch language} $\mathcal{L}^{\otimes k}$, i.e. the set of $k$-tuples of statements all belonging to $\cL$, has an unambiguous interactive proof with round complexity $\ell\cdot\mathsf{polylog}(k)$, per-round communication of $a\cdot \ell\cdot\mathsf{polylog}(k) + \poly(\ell)$ bits, assuming the verifier in the $\UIP$ has depth bounded by $\mathsf{polylog}(k)$.  Prior to this work, the best known batch $\UIP$ for $\mathcal{L}^{\otimes{k}}$ required communication complexity at least $(\mathsf{poly}(a)\cdot k^{\epsilon} + k) \cdot \ell^{1/\epsilon}$ for any arbitrarily small constant $\epsilon>0$ (Reingold-Rothblum-Rothblum, STOC 2016).As a corollary of our result, we obtain a \emph{doubly efficient proof system}, that is, a proof system whose proving overhead is polynomial in the time of the underlying computation, for any language computable in polynomial space and in time at most $n^{O\left(\sqrt{\frac{\log n}{\log\log n}}\right)}$.  This expands the state of the art of doubly efficient proof systems:  prior to our work, such systems were known for languages computable in polynomial space and in time $n^{({\log n})^\delta}$ for a small $\delta>0$ significantly smaller than $1/2$ (Reingold-Rothblum-Rothblum, STOC 2016).Based on joint work with Bonnie Berger, Matthew Hong, and Yael Kalai.  TBD

October 24

Gödel in Cryptography: Zero-Knowledge for NP With No Interaction, No Setup, and Perfect Soundness

Rahul Ilango
IAS

Part Of

10:30A
- 12:00P

Location

32-G882
Add to Calendar 2025-10-24 10:30:00 2025-10-24 12:00:00 America/New_York Gödel in Cryptography: Zero-Knowledge for NP With No Interaction, No Setup, and Perfect Soundness Gödel showed that there are true but unprovable statements. This was bad news for Hilbert, who hoped that every true statement was provable. In this talk, I’ll describe why Gödel’s result is, in fact, good news for cryptography. Specifically, Gödel’s result allows for the following strange scenario: a cryptographic system S is insecure, but it is impossible to prove that S is insecure. As I will explain, in this scenario (defined carefully), S is secure for nearly all practical purposes.Leveraging this idea, we effectively construct — under longstanding assumptions — a classically-impossible cryptographic dream object: “zero-knowledge proofs for NP with no interaction, no setup, and perfect soundness”. As an application, our result lets one give an ordinary mathematical proof that a Sudoku puzzle is solvable without revealing how to solve it. Previously, it was not known how to do this (i.e. how to construct "non-interactive witness hiding proofs"). TBD

October 17

Parallel Repetition for Post-Quantum Arguments

Andrew Huang (MIT)
CSAIL

Part Of

10:30A
- 12:00P

Location

32-G882
32-G882
Add to Calendar 2025-10-17 10:30:00 2025-10-17 12:00:00 America/New_York Parallel Repetition for Post-Quantum Arguments We show that parallel repetition of public-coin interactive arguments reduces the soundness error at an exponential rate even in the post-quantum setting. Moreover, we generalize this result to hold for threshold verifiers, where the parallel repeated verifier accepts if and only if at least t of the executions are accepted (for some threshold t). Prior to this work, these results were known only when the cheating prover was assumed to be classical.We also prove a similar result for three-message private-coin arguments. Previously, Bostanci, Qian, Spooner, and Yuen (STOC 2024) proved such a parallel repetition result in the more general setting of quantum protocols, where the verifier and communication may be quantum. We consider only protocols where the verifier is classical, but obtain a simplified analysis, and for the more general setting of threshold verifiers. TBD

October 10

The Sponge is Quantum Indifferentiable

Joseph Carolan
University of Maryland

Part Of

10:30A
- 12:00P

Location

32-G882
Add to Calendar 2025-10-10 10:30:00 2025-10-10 12:00:00 America/New_York The Sponge is Quantum Indifferentiable The sponge is a cryptographic construction that turns a public permutation into a hash function. When instantiated with the Keccak permutation, the sponge forms the NIST SHA-3 standard. SHA-3 is a core component of most post-quantum public-key cryptography schemes slated for worldwide adoption.While one can consider many security properties for the sponge, the ultimate one is \emph{indifferentiability from a random oracle}, or simply \emph{indifferentiability}. The sponge was proved indifferentiable against classical adversaries by Bertoni et al. in 2008. Despite significant efforts in the years since, little is known about sponge security against quantum adversaries, even for simple properties like preimage or collision resistance beyond a single round. This is primarily due to the lack of a satisfactory quantum analog of the lazy sampling technique for permutations.In this work, we develop a specialized technique that overcomes this barrier in the case of the sponge. We prove that the sponge is in fact indifferentiable from a random oracle against quantum adversaries. Our result establishes that the domain extension technique behind SHA-3 is secure in the post-quantum setting. TBD

September 26

Succinct Non-interactive Arguments of Proximity

Liyan Chen
MIT

Part Of

10:30A
- 12:00P

Location

32-G882
Add to Calendar 2025-09-26 10:30:00 2025-09-26 12:00:00 America/New_York Succinct Non-interactive Arguments of Proximity We study succinct non-interactive arguments of proximity (SNAP), which allow a prover to convince a verifier that a statement is true through a short message. Moreover, the verifier reads only a sublinear number of bits of the statement, and soundness is required to hold against polynomial-time adversaries when the statement is 𝜀-far from any true statements. SNAPs can be seen as the natural analog of property testing in the context of succinct non-interactive arguments (SNARGs). We obtain both positive and negative results for SNAPs.• Adaptive SNAPs for P and NP: For any 𝜀 ∈ (0, 1), we construct the first adaptively sound SNAPs for P with 𝜀-proximity based on standard assumptions: LWE or subexponential DDH or DLIN over bilinear maps. Our proof size, verifier’s query complexity, and verification time are 𝑛^{1/2+𝑜(1)} poly(𝜆), where 𝑛 is the length of the statement and 𝜆 is the security parameter. By additionally assuming sub-exponentially secure indistinguishability obfuscation, we upgrade this result to SNAPs for NP with essentially the same parameters.• Lower Bound: We show that our parameters in the adaptive soundness setting are nearly optimal, up to an 𝑛^{𝑜(1)}poly(𝜆) factor. Our lower bound is unconditional.• Fully Succinct Non-adaptive SNAPs for NP: For any constant 𝜀 ∈ (0, 1), we construct the first non-adaptively sound SNAPs for NP with 𝜀-proximity, based on learning with errors and indistinguishability obfuscation. The proof size, verifier’s query complexity, and verification time in our constructions are fixed polynomials in the security parameter. We also show that restricting such SNAPs to just P would already imply non-adaptively sound SNARGs for NP.Central to our SNAP constructions is a new notion of commitment of proximity, which enables sublinear-time verification of the commitment. To derive our unconditional lower bound, we adopt and generalize theorems from oracle-presampling techniques in the random oracle literature. Both techniques may be of independent interest.Joint work with Zhengzhong Jin and Daniel Wichs (Northeastern University). TBD

September 19

How to Verify Any (Reasonable) Distribution Property: Computationally Sound Argument Systems for Distributions

Tal Herman
UC Berkeley

Part Of

10:30A
- 12:00P

Location

32-G882
Add to Calendar 2025-09-19 10:30:00 2025-09-19 12:00:00 America/New_York How to Verify Any (Reasonable) Distribution Property: Computationally Sound Argument Systems for Distributions  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 $\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

September 12

Succinct Witness Encryption for Batch Languages and Applications

Lalita Devadas
MIT

Part Of

10:30A
- 12:00P

Location

32-G882
Add to Calendar 2025-09-12 10:30:00 2025-09-12 12:00:00 America/New_York Succinct Witness Encryption for Batch Languages and Applications 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, ... , 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 -> {0,1} over the K instances. In this case, decryption is possible only if there exists w_1, ... , 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). TBD

September 05

Breaking Verifiable Delay Functions in the Random Oracle Model

Ziyi Guan, EPFL

Part Of

10:30A
- 12:00P

Location

32-G882
Add to Calendar 2025-09-05 10:30:00 2025-09-05 12:00:00 America/New_York Breaking Verifiable Delay Functions in the Random Oracle Model 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.Based on https://eprint.iacr.org/2024/766, joint work with Artur Riazanov and Weiqiang Yuan.  TBD