Cryptography and Information Security Seminar

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.

Based on https://eprint.iacr.org/2024/766, joint work with Artur Riazanov and Weiqiang Yuan.

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.

Succinct Non-interactive Arguments of Proximity

Liyan Chen (MIT)

September 26, 2025

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

Joseph Carolan (University of Maryland)

October 10, 2025

TBD

TBD

Andrew Huang (MIT)

October 17, 2025

TBD

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

TBD

Kevin He and Lalita Devadas (MIT)

December 5, 2025

TBD

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.

Based on joint work with Divesh Aggarwal, Thomas Espitau, and Spencer Peters, which appeared in SOSA 2025.

(Authenticated) BitGC for (Active) Rate-one 2PC

Xiao Wang (Northwestern University)

March 14, 2025

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.

[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.

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.

Binary Error-Correcting Codes with Minimal Noiseless Feedback

Rachel Zhang (MIT)

September 15, 2023

Abstract placeholder: Add seminar abstract here.

An Efficient Quantum Factoring Algorithm

Oded Regev (NYU)

October 6, 2023

Abstract placeholder: Add seminar abstract here.

Hard Languages in NP ∩ coNP and NIZK Proofs from Unstructured Assumptions

Alexis Korb (UCLA)

October 13, 2023

Abstract placeholder: Add seminar abstract here.

Universal Amplification of KDM Security

Daniel Wichs (Northeastern)

October 27, 2023

Abstract placeholder: Add seminar abstract here.

Private Web Search with Tiptoe

Alexandra Henzinger (MIT)

November 3, 2023

Abstract placeholder: Add seminar abstract here.

SNARGs, Propositional Proofs, and Local Unsatisfiability

Alex Lombardi (Princeton)

December 8, 2023

Abstract placeholder: Add seminar abstract here.

The Cost of Statistical Security in Interactive Proofs for Repeated Squaring

Cody Freitag

September 9, 2022

Abstract placeholder: Add seminar abstract here.

On the Computational Hardness Needed for Quantum Cryptography

Luowen Qian

September 30, 2022

Abstract placeholder: Add seminar abstract here.

The Pseudorandom Oracle Model and Ideal Obfuscation

Ji Luo

October 21, 2022

Abstract placeholder: Add seminar abstract here.

Revisiting Time-Space Tradeoffs for Function Inversion

Spencer Peters

November 18, 2022

Abstract placeholder: Add seminar abstract here.

MacORAMa: Optimal Oblivious RAM with Integrity

Neekon Vafa

December 9, 2022

Abstract placeholder: Add seminar abstract here.

Computational Hardness of Optimal Fair Computation

Hemanta Maji

September 10, 2021

Abstract placeholder: Add seminar abstract here.

A Logarithmic Lower Bound for Oblivious RAM (for all parameters)

Ilan Komargodski

September 17, 2021

Abstract placeholder: Add seminar abstract here.

Classical Verification of Quantum Computational Advantage

Gregory Meyer

October 8, 2021

Abstract placeholder: Add seminar abstract here.

Sumcheck Arguments and their Applications

Katerina Sotiraki

October 22, 2021

Abstract placeholder: Add seminar abstract here.

Hidden Cosets and Applications to Unclonable Cryptography

Qipeng Liu

October 29, 2021

Abstract placeholder: Add seminar abstract here.

Tighter Security for Schnorr Identification and Signatures

Lior Rotem

November 5, 2021

Abstract placeholder: Add seminar abstract here.

Classical proofs of quantum knowledge

Tina Zhang

February 5, 2021

Abstract placeholder: Add seminar abstract here.

On One-way Functions and Kolmogorov Complexity

Rafael Pass

February 19, 2021

Abstract placeholder: Add seminar abstract here.

Fiat-Shamir via List-Recoverable Codes

Alex Lombardi

March 5, 2021

Abstract placeholder: Add seminar abstract here.

Local Proofs Approaching the Witness Length

Ron Rothblum

April 2, 2021

Abstract placeholder: Add seminar abstract here.

Average-Case Hardness of NP from Exponential Worst-Case Hardness Assumptions

Shuichi Hirahara

April 30, 2021

Abstract placeholder: Add seminar abstract here.

Information-Theoretic 2-Round MPC without Round Collapsing

Tianren Liu

October 23, 2020

Abstract placeholder: Add seminar abstract here.

Candidate Obfuscation via Oblivious LWE Sampling

Daniel Wichs

October 30, 2020

Abstract placeholder: Add seminar abstract here.

Indistinguishability Obfuscation from Circular Security

Romain Gay

November 20, 2020

Abstract placeholder: Add seminar abstract here.

Noninteractive Zero Knowledge for NP from Learning With Errors

Christopher Peikert

October 18, 2019

Abstract placeholder: Add seminar abstract here.

Perfect Zero Knowledge for Quantum Multiprover Interactive Proofs

Henry Yuen

October 25, 2019

Abstract placeholder: Add seminar abstract here.

Mixed Functional Encryption: A New Stepping Stone Towards Efficient Tracing

Rishab Goyal

November 8, 2019

Abstract placeholder: Add seminar abstract here.

Extracting Randomness from Extractor-Dependent Sources

Daniel Wichs

November 15, 2019

Abstract placeholder: Add seminar abstract here.

Securing Secret Sharing Against Leakage and Tampering

Ashutosh Kumar

November 22, 2019

Abstract placeholder: Add seminar abstract here.

On Distributional Collision Resistant Hashing

Eylon Yogev (Weizmann Institute)

September 14, 2018

Abstract placeholder: Add seminar abstract here.

Covert Security with Public Verifiability

Xiao Wang (MIT)

October 12, 2018

Abstract placeholder: Add seminar abstract here.

Quantum Lightning Never Strikes the Same State Twice

Mark Zhandry (Princeton)

November 2, 2018

Abstract placeholder: Add seminar abstract here.

Secure Search in the Cloud: Homomorphic Encryption Meets Coresets

Adi Akavia

September 15, 2017

Abstract placeholder: Add seminar abstract here.

A New Approach to Round-Optimal Secure Multiparty Computation

Prabhanjan Ananth

October 6, 2017

Abstract placeholder: Add seminar abstract here.

Fiat-Shamir and Correlation Intractability / Fast Secure PSI

Yilei Chen / Peter Rindal

December 8, 2017

Abstract placeholder: Add seminar abstract here.

Structure vs Hardness Through the Pbfuscation Lens

Akshay Degwekar (MIT)

September 30, 2016

Abstract placeholder: Add seminar abstract here.

Proof of Space from Stacked Expanders

Ling Ren (MIT)

October 21, 2016

Abstract placeholder: Add seminar abstract here.

Rethinking Large-Scale Consensus through Blockchains

Rafael Pass (Cornell)

December 2, 2016

Abstract placeholder: Add seminar abstract here.

Solving SVP (and CVP) in $2^n$ Time via Discrete Gaussian Sampling

Noah Stephens-Davidowitz

September 25, 2015

Abstract placeholder: Add seminar abstract here.

Quantum Homomorphic Encryption for Circuits of Low T-Gate Complexity

Anne Broadbent

October 30, 2015

Abstract placeholder: Add seminar abstract here.

Avoiding Sub-Exponential Loss in Obfustopia

Sanjam Garg

December 11, 2015

Abstract placeholder: Add seminar abstract here.