Charles River Crypto Day @ MIT (STAR ROOM D463)

When: Friday, November 14

Where: MIT Stata Center, Star Room (D463)

Organizers: Ran Canetti, Henry Corrigan-Gibbs, Yael Kalai, Eran Tromer, Vinod Vaikuntanathan and Daniel Wichs

Program :

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-Entropy

Speaker: Jad Silbak

Abstract: 
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 Functions

Speaker: Saroja Erabelli

Abstract: 
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 QFHE

Speaker: Aparna Gupte

Abstract: 
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 Pseudorandomness

Speaker: Jesko Dujmovic

Abstract:
 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.