Skip to main content
Add to Calendar
2025-10-17 10:30:00
2025-10-17 12:00:00
America/New_York
Compiling Any MIP* into a (Succinct) Classical Interactive Argument
We present a generic compiler that converts any MIP* protocol into a succinct interactive argument where the communication and the verifier are classical, and where post-quantum soundness relies on the post-quantum sub-exponential hardness of the Learning with Errors (LWE) problem. Prior to this work, such a compiler for MIP* was given by Kalai, Lombardi, Vaikuntanathan and Yang (STOC 2022), but the post-quantum soundness of this compiler is still under investigation.More generally, our compiler can be applied to any QIP protocol which is sound only against semi-malicious provers which follow the prescribed protocol, but with possibly malicious initial state. Our compiler consists of two steps. We first show that if a language L has a QIP with semi-malicious soundness, where the prover runs in time T, then L is in QMATIME(T). We then construct a succinct classical argument for any such language, where the communication complexity grows only poly-logarithmically with T, under the post-quantum sub-exponential hardness of LWE.The result is joint work with Yael Kalai.
TBD
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
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
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
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
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
