Mark Zhandry

In this work, we study the hardness required to achieve proofs of quantumness (PoQ), which in turn capture (potentially interactive) quantum advantage. A ``trivial'' PoQ is to simply assume an average-case hard problem for classical computers that is easy for quantum computers. However, there is much interest in ``non-trivial'' PoQ that actually rely on quantum hardness assumptions, as these are often a starting point for more sophisticated protocols such as classical verification of quantum computation (CVQC). We show several lower-bounds for the hardness required to achieve non-trivial PoQ, in particular showing that they likely require cryptographic hardness, with different types of cryptographic hardness being required for different variations of non-trivial PoQ. In particular, our results help explain the challenges in using lattices to build publicly verifiable PoQ and its various extensions such as CVQC.

What does it mean to have access to a subroutine? In quantum computing, the usual answer is that, if we can perform a circuit implementing a unitary $U$, we can also implement its variants $U^\dagger$, $\controlled U$, and $\controlled U^\dagger$ equally as efficiently. These four operations are the "usual" suite of oracles we mean when we model access to a subroutine. We interrogate these choices and investigate how changing our access model to $U$ affects the tractability of its computational problems. This submission is a collection of three preprints on possible models of oracle access. 1. In the most limited setting, we only have access to $U$: this is the natural model for metrology, sensing, learning, and other experimental contexts. We show that, unlike in the usual model, the generic Grover speedups for search and estimation, ubiquitous throughout quantum algorithms, cannot be achieved in this setting. 2. In the usual model as well as in general, we show that controlled unitary oracles have a surprisingly limited role. We prove they are not helpful for a large class of problems: problems which are invariant up to global phase, i.e. problems which are a about $U$ as a unitary channel. 3. In the full setting, we are given a circuit implementing $U$: this model is natural for algorithms on scalable quantum computers. We show that the usual suite of oracles is not enough to characterize the strength of this model, by giving a natural problem which cannot be solved efficiently without queries to $U^*$ or $U^T$---which can be implemented from any circuit for $U$. Our proofs are simple and use two main techniques: the compressed oracle method and a lifting principle which we call the "acorn trick".

One-shot signatures (OSS) were defined by Amos, Georgiou, Kiayias, and Zhandry (STOC'20). These allow for signing exactly one message, after which the signing key self-destructs, preventing a second message from ever being signed. While such an object is impossible classically, Amos et al observe that OSS may be possible using quantum signing keys by leveraging the no-cloning principle. OSS has since become an important conceptual tool with many applications in decentralized settings and for quantum cryptography with classical communication. OSS are also closely related to separations between classical-binding and collapse-binding for post-quantum hashing and commitments. Unfortunately, the only known OSS construction due to Amos et al. was only justified in a classical oracle model, and moreover their justification was ultimately found to contain a fatal bug. Thus, the existence of OSS, even in a classical idealized model, has remained open. We give the first standard-model OSS, with provable security assuming (sub-exponential) indistinguishability obfuscation (iO) and LWE. This also gives the first standard-model separation between classical and collapse-binding post-quantum commitments/hashing, solving a decade-old open problem. Along the way, we also give the first construction with unconditional security relative to a classical oracle. To achieve our standard-model construction, we develop a notion of permutable pseudorandom permutations (permutable PRPs), and show how they are useful for translating oracle proofs involving random permutations into obfuscation-based proofs. In particular, obfuscating permutable PRPs gives a trapdoor one-way permutation that is \emph{full-domain}, solving another decade-old-problem of constructing this object from (sub-exponential) iO and one-way functions.

In 2012, Aaronson and Christiano introduced the idea of hidden subspace states to build public-key quantum money [STOC '12]. Since then, this idea has been applied to realize several other cryptographic primitives which enjoy some form of unclonability. In this work, we propose a generalization of hidden subspace states to hidden coset states. We study different unclonable properties of coset states and several applications: (*) We show that, assuming indistinguishability obfuscation (iO), hidden coset states possess a certain direct product hardness property, which immediately implies a tokenized signature scheme in the plain model. Previously, a tokenized signature scheme was known only relative to an oracle, from a work of Ben-David and Sattath [QCrypt '17]. (*) Combining a tokenized signature scheme with extractable witness encryption, we give a construction of an unclonable decryption scheme in the plain model. The latter primitive was recently proposed by Georgiou and Zhandry [ePrint '20], who gave a construction relative to a classical oracle. (*) We conjecture that coset states satisfy a certain natural monogamy-of-entanglement property. Assuming this conjecture is true, we remove the requirement for extractable witness encryption in our unclonable decryption construction. As potential evidence in support of the conjecture, we prove a weaker version of this monogamy property, which we believe will still be of independent interest. (*) Finally, we give the first construction of a copy-protection scheme for pseudorandom functions (PRFs) in the plain model. Our scheme is secure either assuming iO, onw-way functions (OWFs) and extractable witness encryption, or assuming iO, OWFs, compute-and-compare obfuscation and the conjectured monogamy property mentioned above. This is the first example of a copy-protection scheme with provable security in the plain model for a class of functions that is not evasive.

We prove that Kilian's four-message succinct argument system is post-quantum secure in the standard model when instantiated with any probabilistically checkable proof and any collapsing hash function (which in turn exist based on the post-quantum hardness of Learning with Errors). At the heart of our proof is a new "measure-and-repair" quantum rewinding procedure that achieves asymptotically optimal knowledge error.

The quantum random oracle model (QROM) has become the standard model in which to prove the post-quantum security of random-oracle-based constructions. Unfortunately, none of the known proof techniques allow the reduction to record information about the adversary’s queries, a crucial feature of many classical ROM proofs. In this work, we give a new QROM proof technique that overcomes this “recording barrier”, allowing for efficient on-the-fly simulation of random oracles, roughly analogous to the usual classical simulation. We then use this new technique to give the first proof of indifferentiability for domain extension, as well as other applications.

Classical bits can be copied, but quantum bits, in general, cannot. As a result, there is interest in creating uncounterfeitable quantum money, in which a set of qubits can be spent as money but cannot be duplicated. To function as money, there must be a way to verify that a given state is a valid banknote and not a counterfeit. Many recent efforts have tried to allow public key verification, where any untrusted user, even a would-be counterfeiter, can verify the banknotes. However, despite many attempts, a secure construction of public-key quantum money has remained elusive. Here we introduce franchised quantum money, a new notion that is weaker than public key quantum money but brings us closer to realizing it. Franchised quantum money allows any untrusted user to verify banknotes using a unique secret key. Furthermore, we give a construction of franchised quantum money and prove security assuming the quantum hardness of the short-integer solution problem (SIS). This is the first construction of quantum money that allows an untrusted user to verify the banknotes, and which has a proof of security based on widespread assumptions. It is therefore an important step toward public key quantum money. Under franchised quantum money, untrusted users receive unique secret verification keys. With their key, a user can verify banknotes without the mint involved, but they cannot create counterfeit money that would fool another user. This is different from public key quantum money because the verification key may actually enable counterfeiting, but the only person that the counterfeiter can fool is themselves. Here is how franchised quantum money might be useful: consider a group of large corporations, mutually distrustful, that nevertheless want to make transactions with each other. Further, a trusted third party, the mint, will administer the money system. While the mint cannot make verification public-key, it can franchise the ability to verify banknotes to the group of untrusted corporations. The mint gives each corporation a unique secret verification key that allows them to verify banknotes from another corporation. Now what if one corporation decides to start using its key to copy money? Since each corporation gets a different key, any banknotes that the corporation produces will fail to verify when a different key is used. Therefore the dishonest corporation will not be able to fool anyone but themselves. Public key quantum money has eluded sophisticated attempts to construct it directly, so franchised quantum money is useful as a stepping stone. Although franchised quantum money is not public-key, it still enables verification without the mint involved, which is the main feature of interest for public key quantum money. Further, we give a construction of franchised quantum money with a proof of security based on widely-held assumptions about the SIS problem. Franchised quantum money offers greater security than existing constructions of quantum money, and brings us closer to public-key verification.