Program

Abstract

Composition is a cornerstone of classical differential privacy, enabling strong end-to-end guarantees for complex algorithms through composition theorems such as basic and advanced composition. In the quantum setting, however, privacy is defined operationally against arbitrary measurements, and classical composition arguments based on scalar privacy-loss random variables no longer apply.

As a result, it has remained unclear when meaningful composition guarantees can be obtained for quantum differential privacy (QDP). We clarify both the limitations and possibilities of composition in the quantum setting. First, classical-style composition fails in full generality for POVM-based approximate QDP: even quantum channels that are individually perfectly private can completely lose privacy when combined through correlated joint implementations.

For tensor-product channels acting on product neighboring inputs, we introduce a quantum moments accountant based on an operator-valued notion of privacy loss and a matrix moment-generating function. Although the resulting Rényi-type divergence does not satisfy a data-processing inequality, controlling its moments suffices to bound measured Rényi divergence, yielding operational privacy guarantees against arbitrary measurements and advanced-composition-style bounds with the same leading-order behavior as in the classical theory.

The results show that meaningful composition theorems for quantum differential privacy require carefully articulated structural assumptions on channels, inputs, and adversarial measurements, and provide a framework for understanding which classical ideas do and do not extend to the quantum setting.

Abstract

Succinct arguments are cryptographic proofs with small communication complexity, and sometimes small verifier size. Quantum succinct arguments extend this notion by allowing the prover and verifier to be quantum algorithms exchanging quantum messages. This talk discusses a result showing that quantum succinct arguments in the random oracle model are as hard as constructing quantum interactive oracle proofs (QIOPs).

The proof gives an efficient transformation from quantum succinct arguments to QIOPs, showing that quantum succinctness implies quantum probabilistic checking. Along the way, the work introduces a new proximity test for compressed oracles and adapts locality properties of perfect hash functions to the quantum setting. Joint work with Alessandro Chiesa, Ignacio Manzur, and Thomas Vidick.

Abstract

The analysis of quantum algorithms that query random invertible permutations has been a long-standing challenge in cryptography. Many techniques for random oracles fail, or are not known to generalize, leaving foundational constructions involving permutations without quantum security proofs. This work develops and proves soundness of a compressed permutation oracle.

The construction shares key features of Zhandry’s compressed function oracle: the purification is a small list of input-output pairs that meaningfully reflects an algorithm’s knowledge of the oracle.

The framework shows that the seven-round Feistel construction is a strong quantum pseudorandom permutation, resolving an open question from Zhandry (2012). It also re-proves essentially all known quantum query lower bounds in the random permutation model—including collision and preimage resistance for Sponge and Davies–Meyer, hardness of double-sided zero search and sparse predicate search—and gives new lower bounds for cycle finding and the one-more problem.

Abstract

We show an unconditional classical-oracle separation between the class of languages verifiable with a quantum proof ($\mathsf{QMA}$) and the class verifiable with a classical proof ($\mathsf{QCMA}$). Compared with recent work of Bostanci, Haferkamp, Nirkhe, and Zhandry, the proof is conceptually simpler and readily extends to other oracle separations.

The techniques yield the first unconditional classical-oracle separation between languages decidable with quantum advice ($\mathsf{BQP/qpoly}$) and those decidable with classical advice ($\mathsf{BQP/poly}$), improving on earlier quantum-oracle and classically accessible classical-oracle separations.

The oracles are based on the code-intersection problem introduced by Yamakawa and Zhandry, combined with codes having extremely strong list-recovery properties. Joint work with John Bostanci and Vinod Vaikuntanathan.

Abstract

Polynomials are fundamental throughout theoretical computer science. In proof systems, a common verifier task is evaluating a degree-$d$ polynomial at $m$ distinct points. The best known algorithm performs $O((m+d)\log^2(m+d))$ field operations.

We present a concretely efficient $\mathsf{MA}$ protocol in which the verifier runs in linear time: the prover sends one message of $d-1$ field elements, and the verifier performs only $O(m+d)$ field operations. The protocol extends to evaluating multiple polynomials at multiple points, yielding an $\mathsf{AMA}$ protocol.

These protocols improve verifier time in several interactive proofs, notably sumcheck over a large summation domain and protocols using polynomial quotienting. A direct application reduces the verifier runtime in STIR (CRYPTO 2024) to match WHIR (EUROCRYPT 2025), despite WHIR being highly optimized for verification time.

As another application, any univariate polynomial commitment scheme can be transformed, in a black-box manner, into a scheme supporting efficient batch openings at multiple points, with only constant overhead relative to opening one point.

Abstract

We study hash functions that securely instantiate the Fiat–Shamir transformation against bounded-depth adversaries. The motivation is twofold.

First, recent work constructs cryptographic primitives against bounded-depth adversaries from worst-case complexity assumptions. Because Fiat–Shamir has rich applications, instantiating it in this setting could lead to further constructions—such as SNARGs for P or cryptographic hardness results for PPAD—under worst-case assumptions.

Second, we ask whether bounded adversarial depth can overcome the impossibility results for applying Fiat–Shamir to arguments. The results give both positive and negative answers.

On the positive side, for proofs with certain properties, weak worst-case assumptions suffice for explicit hash functions giving $\mathsf{AC}^0[2]$ soundness. In particular, we construct an $\mathsf{AC}^0[2]$-computable correlation-intractable hash family for constant-degree polynomials against $\mathsf{AC}^0[2]$ adversaries, assuming $\oplus\mathsf{L}/\mathsf{poly}\not\subseteq\widetilde{\mathsf{Sum}}_{n^{-c}}\circ\mathsf{AC}^0[2]$ for some $c>0$.

The construction is inspired by the Fiat–Shamir hash function of Peikert and Shiehian (CRYPTO 2019) and the fully homomorphic encryption scheme against bounded-depth adversaries of Wang and Pan (EUROCRYPT 2022).

On the negative side, Fiat–Shamir for arguments remains impossible against bounded-depth adversaries:

• Assuming an $\mathsf{AC}^0[2]$-computable collision-resistant hash function against probabilistic polynomial-time adversaries, every polynomial-size hash function fails to preserve $\mathsf{AC}^0[2]$ soundness for some probabilistic-polynomial-time-sound interactive argument.
• Assuming an $\mathsf{AC}^0[2]$-computable collision-resistant hash function against $\mathsf{AC}^0[2]$ adversaries, there is an $\mathsf{AC}^0[2]$-sound interactive argument for which no $\mathsf{AC}^0[2]$-computable hash function preserves soundness under Fiat–Shamir. This is a low-depth analogue of Goldwasser and Kalai.

Abstract

We study implications of weak zero-knowledge protocols for worst-case-hard languages. Such protocols may have non-negligible completeness, soundness, and zero-knowledge errors, denoted $\epsilon_c$, $\epsilon_s$, and $\epsilon_z$. Assuming worst-case-hard languages in $\mathsf{NP}$, we show:

• If every language in $\mathsf{NP}$ has a NIZK proof or argument satisfying $\epsilon_c+\epsilon_s+\epsilon_z<1$, then one-way functions exist. This covers every nontrivial combination of error rates. If $\epsilon_c$ is negligible, it also yields NIZKs with all errors negligible. Earlier results required the stronger condition $\epsilon_c+\sqrt{\epsilon_s}+\epsilon_z<1$.
• If every language in $\mathsf{NP}$ has a $k$-round public-coin zero-knowledge proof or argument satisfying $\epsilon_c+\epsilon_s+(2k-1)\epsilon_z<1$, then one-way functions exist.
• If, for some constant $k$, every language in $\mathsf{NP}$ has a $k$-round public-coin zero-knowledge proof or argument satisfying $\epsilon_c+\epsilon_s+k\epsilon_z<1$, then infinitely-often one-way functions exist.

Abstract

The inner-product extractor of Impagliazzo, Levin, and Luby (STOC 1989) takes a seed $h\in\mathbb{F}^{\gamma}$ and a source $x\in\{0,1\}^{\gamma}$ and outputs $\langle h,x\rangle$. Its known error bound grows with the square root of seed bias because prior analyses bound squared error using 2-universality; the extractor is not 4-universal.

Motivated by multiparty-computation applications, we prove much tighter bounds by bypassing universal hashing. An elevated general leftover hash lemma gives an $n$th-root bound for functions that are almost $n$-universal. Bounding where the inner-product extractor fails to be 4-universal yields a fourth-root dependence on seed bias for oblivious bit-fixing sources over an appropriate field-size range.

We then use matroid theory to analyze the $n$-way multicollision probability directly, obtaining an asymptotic bound for every even $n$. Concrete fourth-, sixth-, and eighth-root bounds show that no single choice of $n$ is always optimal.

Finally, we introduce seed-adaptive oblivious bit-fixing sources, extend the bounds to them, and use the extension to repair a bug in the proof of the oblivious linear evaluation protocol of Doerner et al. (IEEE S&P 2024).

Abstract

We continue the study of fast functions—computable by linear-size circuits—that share useful properties of random functions. Motivated by cryptographic applications, we obtain:

• For every constant $t$, a fast $t$-wise independent hash function of algebraic degree $\log_2 t$ over $\mathbb{F}_2$, simultaneously optimizing asymptotic circuit size and degree.
• A simpler and stronger family of fast codes with fast duals meeting the Gilbert–Varshamov bound, with negligible failure probability, general fields and rates, systematic encoding, and fast universal encoders.
• For every constant $t$, fast linear functions mapping every $t$ linearly independent inputs to uniform and statistically independent outputs, yielding stronger random-like properties such as optimal combinatorial list decoding. Previously this was known only for $t=1$.

Applications include the first nontrivial perfectly secure multiparty-computation protocols whose circuit complexity scales linearly with the number of parties, and protocols for encrypted matrix-vector products with optimal asymptotic circuit complexity.

Abstract

Additive masking is a widely used side-channel countermeasure in which a secret is split additively into random shares. Over binary fields, however, the Hamming weight of the shares leaks information about the secret. Inner-product masking has been proposed as a promising alternative.

We prove that inner-product masking over a binary extension field is secure against Hamming-weight leakage, which also yields security against arbitrary symmetric-function leakage from the shares. We give an efficiently computable score function for testing and certifying security against leakage.

We also relate the leakage resilience of inner-product and additive masking over arbitrary fields; roughly, inner-product masking is at least as secure. The proof is Fourier analytic and estimates spectral norms of the Hamming slice through Krawtchouk polynomials.

Abstract

We make progress on explicit evaluation places for leakage-resilient Shamir secret sharing over composite-order fields. Maji et al. (EUROCRYPT 2024) showed that random evaluation places over $\mathbb{F}_{p^d}$ yield statistical security against physical-bit leakage; Nguyen (EUROCRYPT 2025) later proved a dichotomy under which a linear code-based scheme is either statistically secure or completely insecure.

Building on the dichotomy, we partially derandomize the evaluation places in a restricted parameter regime. Instead of choosing $n$ independent points, we use iterates $x_j=\Phi^j(x_0)$ of a fixed simple rational function $\Phi$, with only the initial point $x_0\in\mathbb{F}_{p^d}^{*}$ chosen at random. Randomness drops from $nd\log p$ bits to $d\log p$ bits.

The construction applies when $n=O(d/\log_p d)$ and for every reconstruction threshold $k\ge 2$; it achieves perfect security against single-block leakage. The proof uses a partial-fraction non-degeneracy argument exploiting the distinct poles of the rational iterates.

Abstract

This talk surveys recent and not-so-recent theoretical work on attacks against data privacy. The central thesis is that such attacks play a role in privacy-preserving algorithm design analogous to cryptanalysis in secure encryption: they provide natural lower bounds for frameworks such as differential privacy and help explain why nontrivial protections are necessary at all.

Based on joint work with, among others, Mahdi Haghifam and Jon Ullman (2025); Gavin Brown, Mark Bun, Vitaly Feldman, and Kunal Talwar (2021–2022); and Cynthia Dwork, Thomas Steinke, Jon Ullman, and Salil Vadhan (2015).

Abstract

How does the choice of training data influence an AI model? This question is central to interpretability, privacy, data attribution, and basic science. At its core is the data-deletion problem: after a reasonable amount of precomputation, quickly predict how a model would behave if a specified subset of its training data had been deleted.

The talk presents a data-deletion scheme capable of predicting model outputs to arbitrary precision in the deep-learning setting. Its error can be bounded from a simple stability assumption that, unlike prior assumptions, appears fully compatible with deep learning.

The method opens new possibilities for theory in AI, including the first machine-unlearning scheme with provable security in the deep-learning setting.

Abstract

Garbled-circuit techniques secure in the adaptive setting—where inputs are chosen after a garbled program is sent—are motivated by practice but difficult to achieve. Prior adaptive garbling is either impractically expensive or encrypts the garbled program with the output of a programmable random oracle, introducing both a strong model and computational overhead.

We give a simple framework for proving adaptive security in the non-programmable random-oracle model, a milder assumption close to that used by the widely deployed Free XOR extension. The framework applies to several existing garbled-circuit techniques without modifying them and therefore without added overhead.

As the main application, we construct adaptively secure garbling for tri-state circuits, a model capturing Boolean circuits and RAM programs. For a tri-state circuit $C$, the garbling has at most $|C|\lambda$ bits. This yields adaptively secure Boolean garbling matching the concrete performance of half-gates, and garbled RAM in which a $T$-step program has size $O(T\log^3T\log\log T\,\lambda)$.

Abstract

We revisit secure compression of multiparty correlations using only symmetric cryptography. A linear correlation $\mathcal{C}$, defined by a linear subspace $C\subseteq\mathbb{F}^n$, samples a secret random vector $\mathbf{c}\in C$ and assigns each party a fixed subset of its entries.

Gilboa and Ishai (CRYPTO 1999) and Cramer, Damgård, and Ishai (TCC 2005) gave a general method for compressing many independent samples by replicating pseudorandom-function keys among the parties. This yields a pseudorandom correlation function whose key size scales with the number of minimal-support codewords in the defining code.

We observe that the method generalizes to other target correlations $\mathcal{C}_T$ using a secret replication pattern obtained from a random secret assignment of source parties to target parties.

Corollaries include a new derivation of two-party PCFs for VOLE and subfield VOLE over small domains, as well as new multiparty PCFs for small-domain VOLE-style correlations, including scalar-vector multiplication triples and authenticated variants, with applications to secure computation.

Abstract

We study which multiparty distributions can be securely sampled with information-theoretic security against passive corruption when there is neither setup nor an honest majority.

For four-party distributions with Boolean outputs, we prove secure samplability if and only if every two-party distribution obtained by partitioning the parties into two groups is securely samplable. This extends an analogous characterization previously known for three-party distributions.

Abstract

The shuffle model is a noninteractive anonymous-communication abstraction. Parties with private inputs $x_1,\ldots,x_n$ send messages that reach an evaluator in random order; the evaluator should compute a joint function while learning nothing else about the inputs.

The model is increasingly important in both cryptography and differential privacy, where it lies between the high-privacy, low-utility local model and the lower-privacy, high-utility central-curator model. A central open question has been which functions admit statistical security in the shuffle model, with a common conjecture that even simple functions do not.

We refute this conjecture: every function can be computed in the shuffle model with statistical security. Consequently, any differentially private central-curator mechanism can be realized in the shuffle model with essentially the same utility while revealing nothing beyond the central-model output.

The result constructs a statistically secure additive randomized encoding (ARE) for every function. An ARE maps individual inputs to group elements whose sum reveals only the output. The construction is efficient for functions in $\mathsf{NC^1}$ or $\mathsf{NL}$; from one-way functions it gives computationally secure AREs for all polynomial-time functions. More generally, any information-theoretic or computational garbling scheme can be converted to an ARE with constant-factor size overhead.

Joint work with Nir Bitansky, Rachit Garg, and Yuval Ishai.

Abstract

What is the relative computational power of time and space? Low-space algorithms for tree evaluation have become central to this question, especially after Williams (STOC 2025) used the problem to obtain a landmark simulation of time by square-root space.

One approach is the Cook–Mertz algorithm (STOC 2024), which uses $O(\log n\log\log n)$ space and superpolynomial time. Another uses catalytic computing: an algorithm may use a large pre-filled hard drive, provided it restores the drive to its initial state. Buhrman et al. (STOC 2014) gave a polynomial-time tree-evaluation algorithm with $O(\log n)$ free space and polynomial catalytic space.

We improve the catalytic-space bound, giving polynomial-time tree evaluation with $O(\log n)$ free space and subpolynomial catalytic space $2^{\log^{\epsilon}n}$ for every $\epsilon>0$. This opens a new route toward placing tree evaluation in logspace and immediately improves time-to-catalytic-space simulations via Williams’s reduction.

The key conceptual connection is private information retrieval (PIR): both PIR and catalytic computation evaluate a function on a masked input. In catalytic computing, the mask comes from the initial drive contents; in PIR, the client samples it to guarantee privacy. The Cook–Mertz algorithm can be viewed through Reed–Muller PIR, while this result uses matching-vector PIR.

No prior knowledge of catalytic algorithms or tree evaluation is assumed. Joint work with Alexandra Henzinger and Edward Pyne (ePrint 2026/265).

Abstract

We build two-server private information retrieval with information-theoretic security and strong double-efficiency guarantees. For a database of $n>10^6$ bits, each server stores a preprocessed structure of approximately $1.5\sqrt{\log_2 n}\,n$ bits and answers a query by probing $12n^{0.82}$ bits.

To our knowledge, this is the first information-theoretic PIR with a constant number of servers, quasilinear server storage $n^{1+o(1)}$, and polynomially sublinear server time $n^{1-\Omega(1)}$.

The protocol is also concretely efficient. For an 11 GB database with one-byte records, it encodes the database into a 1 TB structure—about 4.5 million times smaller than prior two-server preprocessing schemes at comparable query costs. A query reads and returns 4.4 MB, requiring 2,560 times fewer memory accesses than linear-time PIR.

The work builds on the PIR-with-preprocessing protocol of Beimel, Ishai, and Malkin (CRYPTO 2000). The key improvement is a compact data structure for evaluating a multivariate polynomial and its derivatives, using finite differences to compute Hasse derivatives on the fly.

Joint work with Alexandra Henzinger (EUROCRYPT 2026; ePrint 2025/2008).

Abstract

Private constrained pseudorandom functions hide the predicate circuit from the constrained key. Despite many constructions and applications, their relationship to basic primitives such as one-way functions and public-key encryption has remained unclear.

For example, it is unknown whether one-way functions imply private constrained PRFs for general predicates, or whether one-key-secure private constrained PRFs for all polynomial-size predicates imply public-key primitives such as public-key encryption or secret-key agreement.

We prove the first black-box separation for private constrained PRFs: there is an oracle relative to which one-key-secure private constrained PRFs exist for every predicate while secret-key agreement does not. The proof builds on the simulation framework of Impagliazzo and Rudich (STOC 1989).

The main obstacle is that Eve’s simulation can be unfaithful to the real world because the oracle is more complicated than a random oracle. We introduce a weighting technique that overcomes this issue within the Impagliazzo–Rudich framework.

Abstract

The Ethereum Foundation recently announced the Proximity Prize, which targets open questions important to succinct code-based proof systems. This talk defines the core questions, surveys the current state of knowledge, and explains why resolving them matters for proof-system design.

Joint work with Gal Arnon and Giacomo Fenzi; available as ePrint 2026/680.

Abstract

A subspace design is a collection of linear subspaces with a pseudorandomness property: no low-dimensional subspace has a large total intersection dimension with the collection. Subspace designs were introduced as a derandomization tool in coding theory, where they precode algebraic codes to improve list decodability, and they later found applications across linear-algebraic pseudorandomness.

Near-optimal designs are themselves built from algebraic codes such as folded Reed–Solomon and multiplicity codes. Recent work has uncovered a reverse connection: because of their subspace-design properties, these codes achieve optimal list-size bounds for list decoding, optimal proximity gaps, and random-like local behavior. The proximity-gap questions are especially relevant to modern proof systems, including IOPs and SNARKs.

The talk also touches on a surprising appearance of subspace designs in an NC algorithm for bipartite perfect matching, and surveys how they have become a unifying derandomization tool in coding theory and theoretical computer science.

Abstract

This talk surveys recent error-correcting codes with parameters better than information-theoretically possible when the error pattern is restricted to polynomial-time computation:

• A simple construction over large constant-size alphabets with essentially optimal parameters under minimal hardness assumptions, correcting a fraction $p<1/2$ of errors at rate $R=1-p$ (ITCS 2025).
• Binary unique decoding with essentially the same parameters as the best information-theoretic list-decodable codes, under standard cryptographic assumptions (EUROCRYPT 2025; FOCS 2025).
• Binary unique decoding at Shannon capacity $R=1-H(p)$ for a fraction $p<1/4$ of errors, under strong but plausible cryptographic assumptions (CRYPTO 2026).

Together, the results show that worst-case computationally bounded errors can admit essentially the same parameters as random errors, subject to the inherent limits of one-quarter errors over the binary alphabet and one-half over large alphabets.

Based on joint work with Jad Silbak and George Lu.

Abstract

This talk gives an overview of succinct matrix commitments and the advanced cryptographic capabilities they have recently enabled from lattice assumptions. Applications include broadcast encryption, silent threshold encryption, functional commitments, secure group messaging protocols, and more.