Program
Time table
Title: Copy-Protection from Unclonable Puncturable Obfuscation
Abstract: Quantum copy-protection is a functionality-preserving compiler that transforms a classical program into an unclonable quantum program. This primitive has emerged as a foundational topic in quantum cryptography, with significant recent developments. However, characterizing the functionalities that can be copy-protected is still an active and ongoing research direction. In this talk, I will present new feasibility results of copy-protection based on a new abstraction called Unclonable Puncturable Obfuscation (UPO). In particular, using this framework, we establish the plain-model existence of copy-protection for various classes of functionalities, including puncturable cryptographic functionalities and subclasses of evasive functionalities, under well-studied assumptions, namely, the existence of indistinguishability obfuscation and the Learning With Errors (LWE) assumption. I will also discuss new and stronger security definitions of copy-protection that are satisfied by our constructions, highlighting the conceptual advantages of building copy-protection based on UPO. At the heart of these results lies a plain-model instantiation of UPO, obtained by leveraging recently introduced techniques from [Kitagawa and Yamakawa, TCC'25], which may be of independent interest beyond copy-protection. The talk is based on joint works with Prabhanjan Ananth, Zikuan Huang, Fuyuki Kitagawa, and Takashi Yamakawa.
Title: One-Shot Signatures: Paradigms, Applications & Construction
Abstract: In this talk we will give an overview on one-shot signatures, a quantum cryptographic object first defined by Amos, Georgiou, Kiayias and Zhandry (STOC 2020). We will explain what are one-shot signatures and see where they sit in the map of quantum cryptography, and why they seem to present a new type of quantum cryptographic functionalities. We will go over some of the applications of one-shot signatures, and its previous, single existing design paradigm. We will then present our recent construction of one-shot signatures (Shmueli and Zhandry, CRYPTO 2025) and some of the intuition behind the security proof. Based on joint work with Mark Zhandry (https://eprint.iacr.org/2025/486).
Title: Building Primitives in the Haar Random Oracle Model
Title: Magic and Private Simultaneous Messages
Title: Cryptomania v.s. Minicrypt in a Quantum World
Abstract: The seminal work by Impagliazzo and Rudich (STOC'89) demonstrated the impossibility of constructing classical public key encryption (PKE) from one-way functions (OWF) in a black-box manner. However, the question remains: can quantum PKE (QPKE) be constructed from quantumly secure OWF? A recent line of work has shown that it is indeed possible to build QPKE from OWF, but with one caveat -- they rely on quantum public keys, which cannot be authenticated and reused. In this work, we re-examine the possibility of perfect complete QPKE in the quantum random oracle model (QROM), where OWF exists. Our first main result: QPKE with classical public keys, secret keys and ciphertext, does not exist in the QROM. Previous discussions (Austrin et al. CRYPTO'22) on the impossibility of QPKE from OWF rely on a seemingly strong conjecture. Our work makes a significant step towards a complete and unconditional quantization of Impagliazzo and Rudich's results. Our second main result extends to QPKE with quantum public keys. The second main result: QPKE with quantum public keys, classical secret keys and ciphertext, does not exist in the QROM, if the key generation only makes classical queries and the quantum public key is either pure or ``efficiently clonable''. The result is tight due to all existing QPKEs constructions. Our result further gives evidence on why existing QPKEs lose reusability. To achieve these results, we use a novel argument based on conditional mutual information and quantum Markov chain by Fawzi and Renner (Communications in Mathematical Physics). We believe the techniques used in the work will find other usefulness in separations in quantum cryptography/complexity. The talk is a merge of a series of research.
Title: Cloning Games, Black Holes, and Cryptography
Title: Private proofs of when and where
Title: How to Verify that a Small Device is Quantum, Unconditionally
Abstract: A proof of quantumness (PoQ) allows a classical verifier to efficiently test if a quantum machine is performing a computation that is infeasible for any classical machine. In this work, we propose a new approach for constructing PoQ protocols where soundness holds unconditionally assuming a bound on the memory of the prover, but otherwise no restrictions on its runtime. In this model, we propose two protocols: 1. A simple protocol with a quadratic gap between the memory required by the honest parties and the memory bound of the adversary. The soundness of this protocol relies on Raz's (classical) memory lower bound for matrix inversion (Raz, FOCS 2016). 2. A protocol that achieves an exponential gap, building on techniques from the literature on the bounded storage model (Dodis et al., Eurocrypt 2023). Both protocols are also efficiently verifiable. Despite having worse asymptotics, our first protocol is conceptually simple and relies only on arithmetic modulo 2, which can be implemented with one-qubit Hadamard and CNOT gates, plus a single one-qubit non-Clifford gate.
Title: CountCrypt: Quantum Cryptography between QCMA and PP
Title: Quantum Generic Group Model and Lower Bounds
Title: LWE with Quantum Amplitudes
Abstract: One of the recent attempts of quantumly solving LWE tries to consider LWE with quantum amplitudes, where the LWE error distributions are encoded as quantum amplitudes. I will survey a few recent papers that explore several algorithms, hardness results and applications of LWE with quantum amplitudes, and explain the interesting findings behind the use of complex Gaussian as the LWE amplitudes.
Title: Complexity Theory for Quantum Promise Problems
Title: Impersonating Quantum Secrets over Classical Channels
Abstract: Abstract: We show that a simple eavesdropper listening in on classical communication channels will eventually be able to impersonate any of the parties. Furthermore, the attack is efficient if one-way puzzles do not exist. As a direct consequence, one-way puzzles are implied by reusable authentication schemes over classical channels with quantum pre-shared secrets that are potentially evolving. As an additional application, we show that any quantum money scheme that can be verified through only classical queries to any oracle cannot be information theoretically secure. This significantly generalizes the prior work by Ananth, Hu, and Yuen (ASIACRYPT 23) where they showed the same but only for the specific case of random oracles. Our result thus shows that verifying quantum money inherently requires making quantum queries to the underlying cryptographic tools. Joint work with Mark Zhandry.
Title: An efficient quantum parallel repetition theorem
Title: On the Cryptographic Foundations of Interactive Quantum Advantage
Title: Quantum Group Actions
Title: On the Need for (Quantum) Memory with Short Outputs
Abstract: In this work, we establish the first separation between computation with bounded and unbounded space, for problems with short outputs (i.e., working memory can be exponentially larger than output size), both in the classical and the quantum setting. Towards that, we construct a hash function, for which collisions can be found with N^{1/3} quantum queries using N^{1/3} space, yet any quantum algorithm lacking sufficient space requires at least N^{0.35} queries.
Title: A New Approach to Argument of Quantum Knowledge
Title: On the Limitations of Pseudorandom Unitaries
Abstract: Pseudorandom unitaries (PRUs), one of the key quantum pseudorandom notions, are efficiently computable unitaries that are computationally indistinguishable from Haar random unitaries. While there is evidence to believe that PRUs are weaker than one-way functions, so far its relationship with other quantum cryptographic primitives (that are plausibly weaker than one-way functions) has not been fully established. In this work, we focus on quantum cryptographic primitives with classical communication, referred to as QCCC primitives. Our main result shows that QCCC bit commitments and QCCC key agreement, cannot be constructed from pseudorandom unitaries in a black-box manner. Our core technical contribution is to show (in a variety of settings) the difficulty of distinguishing identical versus independent Haar unitaries by separable channels. Our result strictly improves upon prior works which studied similar problems in the context of learning theory [Anshu, Landau, Liu, STOC 2022] and cryptography [Ananth, Gulati, Lin, TCC 2024]. *Based on joint work with Prabhanjan Ananth and Aditya Gulati, to appear in TCC 2025
Title: On Cryptography and Distribution Verification with Application to Quantum Advantage
Title: Compiled Nonlocal Games from any trapdoor Claw-Free Function
Title: The Black-Box Simulation Barrier Persists in a Fully Quantum World
Title: Classical Obfuscation of Quantum Circuits via Publicly-Verifiable QFHE
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 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 "null" 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, 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. Our main step is the first construction of a 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 build on a generic approach introduced by Bartusek, Kitagawa, Nishimaki and Yamakawa (STOC 2023) for publicly verifying the homomorphic evaluations of QFHE ciphertexts. Unfortunately, previous work on publicly-verifiable QFHE required ciphertexts that are both quantum and non-compact, which was due to a heavy use of subspace states and their publicly-verifiable properties. As part of our core technical contribution, we introduce new techniques for analyzing subspace 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 satisfies both blindness and public-verifiability. This is based on joint work with James Bartusek, Saachi Mutreja and Omri Shmueli.
Title: Can we base cryptography on hard problems in quantum error correction?
Abstract: Cryptographic assumptions are typically found in well-studied mathematical conjectures, such as the hardness of factoring large integers, computing discrete logarithms, or solving short vector problems in lattices. A popular paradigm for "post-quantum" assumptions is rooted in coding theory, in particular, the hardness of decoding random linear codes in the presence of noise, also known as Learning Parity with Noise (LPN). Despite many decades of extensive study, the fastest known algorithms still run in exponential time. This naturally raises the question: is there a quantum analog of LPN? Surprisingly, the hardness of decoding "random" quantum codes, such as stabilizer codes, has been far from understood. In this talk, I will present some recent work on the average-case complexity of quantum stabilizer decoding, and its potential to serve as a new post-quantum hardness assumption. Based on joint works with: Yihui Quek and Peter Shor (arXiv:2410.18953) Andrey Khesin, Jonathan Lu, Akshar Ramkumar and Vinod Vaikuntanathan (arXiv:2509.20697)
Title: Perfectly Recording Queries to Random Unitaries and Other Goups
Title: Quantum Lightning from Non-Abelian Group Actions
Title: A meta-complexity characterization of minimal quantum cryptography
Abstract: We give a meta-complexity characterization of EFI pairs, which are considered the "minimal" primitive in quantum cryptography (due to their equivalence to quantum commitments and for being implied by almost all other known quantum cryptographic primitives). More precisely, we show that the existence of EFI pairs is equivalent to the following: there exists a non-uniformly samplable distribution over pure states such that the problem of estimating a certain Kolmogorov-like complexity measure is hard given a single copy. The complexity measure that we consider is a smoothed version of the algorithmic entropy notion introduced by Gacs [Gac01]. A key technical step in our proof, which may be of independent interest, is to show that the existence of EFI pairs is equivalent to the existence of non-uniform single-copy secure pseudorandom state generators (nu 1-PRS). As a corollary, we get an alternative, arguably simpler, construction of a universal EFI pair.
Title: Less is More: On Copy Complexity in Quantum Cryptography
Title: A Unified Approach to Quantum Key Leasing with a Classical Lessor
Abstract: Secure key leasing allows a cryptographic key to be leased as a quantum state in such a way that the key can later be revoked in a verifiable manner. In this work, we propose a modular framework for constructing secure key leasing with a classical-lessor, where the lessor is entirely classical and, in particular, the quantum secret key can be both leased and revoked using only classical communication. Based on this framework, we obtain classical-lessor secure key leasing schemes for public-key encryption (PKE), pseudorandom function (PRF), and digital signature. We adopt the strong security notion known as security against verification key revealing attacks (VRA security) proposed by Kitagawa et al. (Eurocrypt 2025) into the classical-lessor setting, and we prove that all three of our schemes satisfy this notion under the learning with errors assumption. Our PKE scheme improves upon the previous construction by Goyal et al. (Eurocrypt 2025), and our PRF and digital signature schemes are respectively the first PRF and digital signature with classical-lessor secure key leasing property.