Program (Workshop, 18th)
Title: On the Power of Oblivious State Preparation
Abstract: This talk will discuss Oblivious State Preparation (OSP) as a cryptographic primitive that unifies techniques developed in the context of a quantum server interacting with a classical client. OSP enables a classical sender to input a choice of one of two public observables and a quantum receiver to recover an eigenstate of the corresponding observable, while keeping the sender's choice hidden from the receiver. We will see that OSP follows from (plain) trapdoor claw-free functions (TCFs), and implies the existence of proofs of quantumness, test of a qubit, blind classical delegation of quantum computation, and classical verification of quantum computation. Moreover, round-optimal (two-round) OSP follows from dual-mode TCFs, and implies semi-quantum money, classically-verifiable position verification, and (assuming classical FHE with log-depth decryption) quantum FHE. While many of these results follow largely by adapting, modularizing, and generalizing prior work, we expect that the identification of a simple primitive giving all of these applications will be both a useful pedagogical tool and a boon to future research. In particular, it abstracts away the cryptographic essence of several results in the area, yielding relatively simple protocols that call an underlying OSP functionality. Finally, towards understanding the minimal hardness assumptions required to realize OSP, we will show that OSP implies key agreement with classical communication. This result helps to "explain" the use of public-key cryptography in enabling a classical client to establish a leash on a quantum server. Based on joint work with Dakshita Khurana
Title: Founding Quantum Cryptography on Quantum Advantage, or, Towards Cryptography from #P-Hardness
Abstract: A flurry of exciting recent research has shown that quantum cryptosystems (beyond QKD) can exist relative to certain oracles that break all classical cryptography. But obtaining unrelativized constructions of quantum cryptosystems from assumptions clearly weaker than the existence of one-way functions remained open. In this talk, I will describe how to base quantum commitments and secure computation on well-studied mathematical assumptions, from the quantum advantage literature, that do not imply the existence of one-way functions. To our knowledge, this provides the first unrelativized foundations for Microcrypt. Based on joint work with Kabir Tomer. eprint
Title: Quantum Algorithms for Factoring, Revisited
Abstract: We will describe an algorithm of O. Regev who constructed an $O(n^{3/2})$-gate quantum circuit for factoring, improving on Shor's $O(n^2)$, as well as our improvements to it. We will describe a collection of results: how to reduce the number of qubits in Regev's algorithm from $O(n^{3/2})$ to $O(n)$, achieving the best of Shor and Regev; how to build a factoring circuit whose gates err with probability 1/n^{3/2} (without using expensive quantum fault-tolerance techniques), improving on both Shor and Regev. In addition, time permitting, we will also present the Jacobi factoring circuit which completely factors a positive fraction of all numbers with near-linear size quantum circuits. This talk is based on joint work with Seyoon Ragavan (MIT).
Title: State-Based Classical Shadows in Constant Online Depth
Abstract: Classical Shadow Tomography (Huang, Kueng and Preskill, Nature Physics 2020) is a method for creating a classical snapshot of an unknown quantum state, which can later be used to predict the value of an a-priori unknown observable on that state. In the short time since their introduction, classical shadows received a lot of attention from the physics, quantum information, and quantum computing communities. In particular there has been a major effort focused on improving the complexity, and in particular depth, of generating the classical snapshot. We present a novel framework for classical shadow tomography inspired by quantum teleportation. Essentially, we create the snapshot by entangling the unknown input state with an independently prepared auxiliary state, and measuring the resulting entangled state. This presents two improvements compared to previous protocols. First, the online part of our method (i.e. the part that depends on the input) is simply performing a measurement in the Bell basis, which can be done in constant depth using elementary gates. Second, if we use (approximate) state 3-designs as auxiliary states then we recover the previous state of the art results but using an arguably weaker object (state designs vs. unitary designs). We then show that for efficient observables, it suffices to be computationally close to being a state design. To the best of our knowledge, computational classical shadow tomography was not considered in the literature prior to our work. Joint work with Nir Magrafta and Tomer Solomon.
Title: A Simple Framework for Secure Key Leasing
Abstract: Secure key leasing (a.k.a. key-revocable cryptography) enables us to lease a cryptographic key as a quantum state in such a way that the key can be later revoked in a verifiable manner. We propose a simple framework for constructing cryptographic primitives with secure key leasing via the certified deletion property of BB84 states. Based on our framework, we obtain the following schemes. (1) A public key encryption scheme with secure key leasing that has classical revocation based on any IND-CPA secure public key encryption scheme. Prior works rely on either quantum revocation or stronger assumptions such as the quantum hardness of the learning with errors (LWE) problem. (2) A pseudorandom function with secure key leasing that has classical revocation based on one-way functions. Prior works rely on stronger assumptions such as the quantum hardness of the LWE problem. (3) A digital signature scheme with secure key leasing that has classical revocation based on the quantum hardness of the short integer solution (SIS) problem. Our construction has static signing keys, i.e., the state of a signing key almost does not change before and after signing. Prior constructions either rely on non-static signing keys or indistinguishability obfuscation to achieve a stronger goal of copy-protection. In addition, all of our schemes remain secure even if a verification key for revocation is leaked after the adversary submits a valid certificate of deletion. To our knowledge, all prior constructions are totally broken in this setting. Moreover, in our view, our security proofs are much simpler than those for existing schemes. Joint work with Fuyuki Kitagawa and Tomoyuki Morimae. eprint
Title: Quantum advantage and primacy (supremacy)
Abstract: We discuss quantum computational advantage and the various ways in which a quantum device might provide advantages over classical devices. We then focus on quantum primacy (also known as supremacy) and the Extended Church-Turing Thesis (ECTT). We'll discuss the state of the art results in quantum complexity theory that attempt to refute the ECTT. Time permitting, we will overview applications. Reference: Movassagh, Nature Physics volume 19, pages1719-1724 (2023)
Associated Seminars
Title: Pseudorandom Function-like States from Common Haar Unitary
Abstract: Recent active studies have demonstrated that cryptography without one-way functions (OWFs) could be possible in the quantum world. Many fundamental primitives that are natural quantum analogs of OWFs or pseudorandom generators (PRGs) have been introduced, and their mutual relations and applications have been studied. Among them, pseudorandom function-like state generators (PRFSGs) [Ananth, Qian, and Yuen, Crypto 2022] are one of the most important primitives. PRFSGs are a natural quantum analogue of pseudorandom functions (PRFs), and imply many applications such as IND-CPA secret-key encryption (SKE) and EUF-CMA message authentication code (MAC). However, only known constructions of (many-query-secure) PRFSGs are ones from OWFs or pseudorandom unitaries (PRUs). In this paper, we construct PRFSGs in the common Haar unitary (CHU) model. The CHU model is an idealized model where any party can access a public single Haar random unitary, which can be considered as a quantum analog of the random oracle model. Our PRFSGs are, unfortunately, only non-adaptively-secure ones, and it is an open problem to construct adaptively-secure PRFSGs or even PRUs. Recently, [Ananth, Gulati, and Lin, eprint:2024/1043] constructed non-adaptively-secure PRFSGs in the common Haar state (CHS) model, where any party can access many copies of Haar random states. Their PRFSGs are secure as long as the number of queries by the adversary is at most $o(\secp/\log \secp)$, where $\secp$ is the security parameter. They also showed that this is optimal in the CHS model. Our result overcomes the barrier by considering the CHU model: Our non-adaptively-secure PRFSGs are secure against any unbounded poly number of queries. Our technical contribution is to introduce a new formula, which we call the Haar twirl approximation formula. The formula itself has its own interest and will have many applications. In fact, by using the formula, we give an alternative proof of the non-adaptive security of the PFC ensemble [Metger, Poremba, Sinha, and Yuen, FOCS 2024] as an additional result. A joint work with Minki Hhan
Title: A New World in the Depths of Microcrypt: Separating OWSGs and Quantum Money from QEFID
Abstract: While in classical cryptography, one-way functions (OWFs) are widely regarded as the ``minimal assumption,'' the situation in quantum cryptography is less clear. Recent works have put forward two concurrent candidates for the minimal assumption in quantum cryptography: One-way state generators (OWSGs), postulating the existence of a hard search problem with an efficient verification algorithm, and EFI pairs, postulating the existence of a hard distinguishing problem. Two recent papers [Khurana and Tomer STOC'24; Batra and Jain FOCS'24] showed that OWSGs imply EFI pairs, but the reverse direction remained open. In this work, we give strong evidence that the opposite direction does not hold: We show that there is a quantum unitary oracle relative to which EFI pairs exist, but OWSGs do not. In fact, we show a slightly stronger statement that holds also for EFI pairs that output classical bits (QEFID). As a consequence, we separate, via our oracle, QEFID, and one-way puzzles from OWSGs and several other Microcrypt primitives, including efficiently verifiable one-way puzzles and unclonable state generators. In particular, this solves a problem left open in [Chung, Goldin, and Gray Crypto'24]. Using similar techniques, we also establish a fully black-box separation (which is slightly weaker than an oracle separation) between private-key quantum money schemes and QEFID pairs. One conceptual implication of our work is that the existence of an efficient verification algorithm may lead to qualitatively stronger primitives in quantum cryptography. Joint work with Amit Behera, Giulio Malavolta, Tomoyuki Morimae, and Takashi Yamakawa. Eprint
Title: Signatures From Pseudorandom States via Bot-PRFs
Abstract: Different flavors of quantum pseudorandomness have proven useful for various cryptographic applications, with the compelling feature that these primitives are potentially weaker than post-quantum one-way functions. Ananth, Lin, and Yuen (2023) have shown that logarithmic pseudorandom states can be used to construct a pseudo-deterministic PRG : informally, for a fixed seed, the output is the same with 1-1/poly probability. In this work, we introduce new definitions for bot-PRG and bot-PRF. The correctness guarantees are that, for a fixed seed, except with negligible probability, the output is either the same (with probability 1-1/poly) or recognizable abort, denoted bot. We construct a bot-PRG from any pseudo-deterministic PRG and, from that, a bot-PRF. Even though most Minicrypt primitives, such as symmetric key encryption, commitments, MAC, and length-restricted one-time digital signatures, have been shown based on various quantum pseudorandomness assumptions, digital signatures remained elusive. Our main application is a (quantum) digital signature scheme with classical public keys and signatures, thereby addressing a previously unresolved question posed in Morimae and Yamakawa's work (Crypto, 2022). Additionally, we construct CPA secure public-key encryption with tamper-resilient quantum public keys. eprint
Title:Oracle Separation Between Quantum Commitments and Quantum One-wayness
Abstract: We show that there exists a unitary quantum oracle relative to which quantum commitments exist but no (efficiently verifiable) one-way state generators exist. Both have been widely considered candidates for replacing one-way functions as the minimal assumption for cryptography?the weakest cryptographic assumption implied by all of computational cryptography. Recent work has shown that commitments can be constructed from one-way state generators, but the other direction has remained open. Our results rule out any black-box construction, and thus settle this crucial open problem, suggesting that quantum commitments (as well as its equivalency class of EFI pairs, quantum oblivious transfer, and secure quantum multiparty computation) appear to be strictly weakest among all known cryptographic primitives. Joint work with John Bostance and Barak Nehoran. Eprint
Title: Cryptographic Characterization of Quantum Advantage
Abstract: Quantum computational advantage refers to an existence of computational tasks that are easy for quantum computing but hard for classical one. Unconditionally showing quantum advantage is beyond our current understanding of complexity theory, and therefore some computational assumptions are needed. Which complexity assumption is necessary and sufficient for quantum advantage? In this paper, we show that inefficient-verifier proofs of quantumness (IV-PoQ) exist if and only if classically-secure one-way puzzles (OWPuzzs) exist. As far as we know, this is the first time that a complete cryptographic characterization of quantum advantage is obtained. IV-PoQ capture various types of quantum advantage previously studied, such as sampling advantage and searching advantage. Previous work [Morimae and Yamakawa 2024] showed that IV-PoQ can be constructed from OWFs, but a construction of IV-PoQ from weaker assumptions was left open. Our result solves the open problem. OWPuzzs are one of the most fundamental quantum cryptographic primitives implied by many quantum cryptographic primitives weaker than one-way functions (OWFs). The equivalence between IV-PoQ and classically-secure OWPuzzs therefore highlights that if there is no quantum advantage, then these fundamental primitives do not exist. The equivalence also means that quantum advantage is an example of the applications of OWPuzzs. Except for commitments, no application of OWPuzzs was known before. Our result shows that quantum advantage is another application of OWPuzzs. Moreover, it is the first quantum computation classical communication (QCCC) application of OWPuzzs. Joint work with Tomoyuki Morimae and Takashi Yamakawa. Eprint