Quantum information allows us to build quantum money schemes, where a bank can issue banknotes in the form of authenticatable quantum states that cannot be cloned or counterfeited: a user in possession of k banknotes cannot produce k +1 banknotes. Similar to paper banknotes, in existing quantum money schemes, a banknote consists of an unclonable quantum state and a classical serial number, signed by bank. Thus, they lack one of the most fundamental properties cryptographers look for in a...

We put forth 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 allows a classical polynomial-time sender to input a choice of one out of two public observables, and a quantum polynomial-time receiver to recover an eigenstate of the corresponding observable -- while keeping the sender's choice hidden from any malicious receiver. We obtain the following results: - The...

Aaronson, Atia, and Susskind [Aaronson et al., 2020] established that efficiently mapping between quantum states $\ket{\psi}$ and $\ket{\phi}$ is computationally equivalent to distinguishing their superpositions $\frac{1}{\sqrt{2}}(|\psi\rangle + |\phi\rangle)$ and $\frac{1}{\sqrt{2}}(|\psi\rangle - |\phi\rangle)$. We generalize this insight into a broader duality principle in quantum computation, wherein manipulating quantum states in one basis is equivalent to extracting their value in a...

We construct a quantum oracle relative to which $\mathbf{BQP}=\mathbf{QCMA}$ but quantum-computation-classical-communication (QCCC) key exchange, QCCC commitments, and two-round quantum key distribution exist. We also construct an oracle relative to which $\mathbf{BQP}=\mathbf{QMA}$, but quantum lightning (a stronger variant of quantum money) exists. This extends previous work by Kretschmer [Kretschmer, TQC22], which showed that there is a quantum oracle relative to which...

Cryptographic group actions are a leading contender for post-quantum cryptography, and have also been used in the development of quantum cryptographic protocols. In this work, we explore quantum group actions, which consist of a group acting on a set of quantum states. We show the following results: 1. In certain settings, statistical (even query bounded) security is impossible, analogously to post-quantum classical group actions. 2. We construct quantum state group actions and prove that...

We construct a quantum money/quantum lightning scheme from class group actions on elliptic curves over $F_{p}$. Our scheme, which is based on the invariant money construction of Liu-Montgomery-Zhandry (Eurocrypt '23), is simple to describe. We believe it to be the most instantiable and well-defined quantum money construction known so far. The security of our quantum lightning construction is exactly equivalent to the (conjectured) hardness of constructing two uniform superpositions over...

In quantum cryptography, there could be a new world, Microcrypt, where cryptography is possible but one-way functions (OWFs) do not exist. Although many fundamental primitives and useful applications have been found in Microcrypt, they lack ``OWFs-free'' concrete hardness assumptions on which they are based. In classical cryptography, many hardness assumptions on concrete mathematical problems have been introduced, such as the discrete logarithm (DL) problems or the decisional...

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

In classical cryptography, one-way functions (OWFs) are the minimal assumption, while recent active studies have demonstrated that OWFs are not necessarily the minimum assumption in quantum cryptography. Several new primitives have been introduced such as pseudorandom unitaries (PRUs), pseudorandom function-like state generators (PRFSGs), pseudorandom state generators (PRSGs), one-way state generators (OWSGs), one-way puzzles (OWPuzzs), and EFI pairs. They are believed to be weaker than...

Although one-way functions are well-established as the minimal primitive for classical cryptography, a minimal primitive for quantum cryptography is still unclear. Universal extrapolation, first considered by Impagliazzo and Levin (1990), is hard if and only if one-way functions exist. Towards better understanding minimal assumptions for quantum cryptography, we study the quantum analogues of the universal extrapolation task. Specifically, we put forth the classical$\rightarrow$quantum...

We explore a new pathway to designing unclonable cryptographic primitives. We propose a new notion called unclonable puncturable obfuscation (UPO) and study its implications for unclonable cryptography. Using UPO, we present modular (and in some cases, arguably, simple) constructions of many primitives in unclonable cryptography, including, public-key quantum money, quantum copy-protection for many classes of functionalities, unclonable encryption, and single-decryption encryption....

We prove a tight parallel repetition theorem for $3$-message computationally-secure quantum interactive protocols between an efficient challenger and an efficient adversary. We also prove under plausible assumptions that the security of $4$-message computationally secure protocols does not generally decrease under parallel repetition. These mirror the classical results of Bellare, Impagliazzo, and Naor [BIN97]. Finally, we prove that all quantum argument systems can be generically compiled...

A robust combiner combines many candidates for a cryptographic primitive and generates a new candidate for the same primitive. Its correctness and security hold as long as one of the original candidates satisfies correctness and security. A universal construction is a closely related notion to a robust combiner. A universal construction for a primitive is an explicit construction of the primitive that is correct and secure as long as the primitive exists. It is known that a universal...

Non-malleable cryptography, proposed by Dolev, Dwork, and Naor (SICOMP '00), has numerous applications in protocol composition. In the context of proofs, it guarantees that an adversary who receives a proof cannot maul it into another valid proof. However, non-malleable cryptography (particularly in the non-interactive setting) suffers from an important limitation: An attacker can always copy the proof and resubmit it to another verifier (or even multiple verifiers). In this work, we...

A non-interactive ZK (NIZK) proof enables verification of NP statements without revealing secrets about them. However, an adversary that obtains a NIZK proof may be able to clone this proof and distribute arbitrarily many copies of it to various entities: this is inevitable for any proof that takes the form of a classical string. In this paper, we ask whether it is possible to rely on quantum information in order to build NIZK proof systems that are impossible to clone. We define and...

We give a construction of public key quantum money, and even a strengthened version called quantum lightning, from abelian group actions, which can in turn be constructed from suitable isogenies over elliptic curves. We prove security in the generic group model for group actions under a plausible computational assumption, and develop a general toolkit for proving quantum security in this model. Along the way, we explore knowledge assumptions and algebraic group actions in the quantum...

Unclonable cryptography builds primitives that enjoy some form of unclonability, such as quantum money, software copy protection, and bounded execution programs. These are impossible in the classical model as classical data is inherently clonable. Quantum computing, with its no-cloning principle, offers a solution. However, it is not enough to realize bounded execution programs; these require one-time memory devices that self-destruct after a single data retrieval query. Very recently, a new...

The powerful no-cloning principle of quantum mechanics can be leveraged to achieve interesting primitives, referred to as unclonable primitives, that are impossible to achieve classically. In the past few years, we have witnessed a surge of new unclonable primitives. While prior works have mainly focused on establishing feasibility results, another equally important direction, that of understanding the relationship between different unclonable primitives is still in its nascent stages....

Public-key quantum money is a cryptographic proposal for using highly entangled quantum states as currency that is publicly verifiable yet resistant to counterfeiting due to the laws of physics. Despite significant interest, constructing provably-secure public-key quantum money schemes based on standard cryptographic assumptions has remained an elusive goal. Even proposing plausibly-secure candidate schemes has been a challenge. These difficulties call for a deeper and systematic study...

E-voting offers significant potential savings in time and money compared to current voting systems. Unfortunately, many current e-voting schemes are susceptible to quantum attacks. In this paper, we expand upon EVOLVE, an existing lattice-based quantum-secure election scheme introduced by Pino et al. We are able to make these expansions by extending the dimensions of the voter's ballot and creating additional proofs, allowing for applicability to realistic election schemes. Thus, we present...

Public verification of quantum money has been one of the central objects in quantum cryptography ever since Wiesner's pioneering idea of using quantum mechanics to construct banknotes against counterfeiting. So far, we do not know any publicly-verifiable quantum money scheme that is provably secure from standard assumptions. In this work, we provide both negative and positive results for publicly verifiable quantum money. **In the first part, we give a general theorem, showing that a...

The existence of one-way functions is one of the most fundamental assumptions in classical cryptography. In the quantum world, on the other hand, there are evidences that some cryptographic primitives can exist even if one-way functions do not exist [Morimae and Yamakawa, CRYPTO 2022; Ananth, Qian, and Yuen, CRYPTO 2022]. We therefore have the following important open problem in quantum cryptography: What is the most fundamental element in quantum cryptography? In this direction, Brakerski,...

Assume that Alice can do only classical probabilistic polynomial-time computing while Bob can do quantum polynomial-time computing. Alice and Bob communicate over only classical channels, and finally Bob gets a state $|x_0\rangle+|x_1\rangle$ with some bit strings $x_0$ and $x_1$. Is it possible that Alice can know $\{x_0,x_1\}$ but Bob cannot? Such a task, called {\it remote state preparations}, is indeed possible under some complexity assumptions, and is bases of many quantum cryptographic...

We investigate the security assumptions behind three public-key quantum money schemes. Aaronson and Christiano proposed a scheme based on hidden subspaces of the vector space $\mathbb{F}_2^n$ in 2012. It was conjectured by Pena et al in 2015 that the hard problem underlying the scheme can be solved in quasi-polynomial time. We confirm this conjecture by giving a polynomial time quantum algorithm for the underlying problem. Our algorithm is based on computing the Zariski tangent space of a...

Quantum tokenized signature schemes (Ben-David and Sattath, QCrypt 2017) allow a sender to generate and distribute quantum unclonable states which grant their holder a one-time permission to sign in the name of the sender. Such schemes are a strengthening of public-key quantum money schemes, as they imply public-key quantum money where some channels of communication in the system can be made classical. An even stronger primitive is semi-quantum tokenized signatures, where the sender is...

Quantum money is a main primitive in quantum cryptography, that enables a bank to distribute to parties in the network, called wallets, unclonable quantum banknotes that serve as a medium of exchange between wallets. While quantum money suggests a theoretical solution to some of the fundamental problems in currency systems, it still requires a strong model to be implemented; quantum computation and a quantum communication infrastructure. A central open question in this context is whether we...

The construction of public key quantum money based on standard cryptographic assumptions is a longstanding open question. Here we introduce franchised quantum money, an alternative form of quantum money that is easier to construct. Franchised quantum money retains the features of a useful quantum money scheme, namely unforgeability and local verification: anyone can verify banknotes without communicating with the bank. In franchised quantum money, every user gets a unique secret verification...

We propose a new idea for public key quantum money. In the abstract sense, our bills are encoded as a joint eigenstate of a fixed system of commuting unitary operators. We perform some basic analysis of this black box system and show that it is resistant to black box attacks. In order to instantiate this protocol, one needs to find a cryptographically complicated system of computable, commuting, unitary operators. To fill this need, we propose using Brandt operators acting on the Brandt...

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 study a generalization of hidden subspace states to hidden coset states. This notion was considered independently by Vidick and Zhang [Eurocrypt '21], in the context of proofs of quantum knowledge from quantum money schemes....

Quantum copy protection uses the unclonability of quantum states to construct quantum software that provably cannot be pirated. Copy protection would be immensely useful, but unfortunately little is known about how to achieve it in general. In this work, we make progress on this goal, by giving the following results: –We show how to copy protect any program that cannot be learned from its input/output behavior, relative to a classical oracle. This improves on Aaronson [CCC’09], which ...

Secure software leasing (SSL) is a quantum cryptographic primitive that enables an authority to lease software to a user by encoding it into a quantum state. SSL prevents users from generating authenticated pirated copies of leased software, where authenticated copies indicate those run on legitimate platforms. Although SSL is a relaxed variant of quantum copy protection that prevents users from generating any copy of leased softwares, it is still meaningful and attractive. Recently, Ananth...

Secure two-party computation considers the problem of two parties computing a joint function of their private inputs without revealing anything beyond the output of the computation. In this work, we take the first steps towards understanding the setting where: 1) the two parties (Alice and Bob) can communicate only via a classical channel, 2) the input of Bob is quantum, and 3) the input of Alice is classical. Our first result indicates that in this setting it is in general impossible to...

In a quantum money scheme, a bank can issue money that users cannot counterfeit. Similar to bills of paper money, most quantum money schemes assign a unique serial number to each money state, thus potentially compromising the privacy of the users of quantum money. However in a quantum coins scheme, just like the traditional currency coin scheme, all the money states are exact copies of each other, providing a better level of privacy for the users. A quantum money scheme can be private, i.e.,...

Quantum money allows a bank to mint quantum money states that can later be verified and cannot be forged. Usually, this requires a quantum communication infrastructure to transfer quantum states between the user and the bank. Gavinsky (CCC 2012) introduced the notion of classically verifiable quantum money, which allows verification through classical communication. In this work we introduce the notion of classical minting, and combine it with classical verification to introduce semi-quantum...

We define the notion of one-shot signatures, which are signatures where any secret key can be used to sign only a single message, and then self-destructs. While such signatures are of course impossible classically, we construct one-shot signatures using quantum no-cloning. In particular, we show that such signatures exist relative to a classical oracle, which we can then heuristically obfuscate using known indistinguishability obfuscation schemes. We show that one-shot signatures have...

We consider the problem of efficiently simulating random quantum states and random unitary operators, in a manner which is convincing to unbounded adversaries with black-box oracle access. This problem has previously only been considered for restricted adversaries. Against adversaries with an a priori bound on the number of queries, it is well-known that t-designs suffice. Against polynomial-time adversaries, one can use pseudorandom states (PRS) and pseudorandom unitaries (PRU), as defined...

A central tenet of theoretical cryptography is the study of the minimal assumptions re- quired to implement a given cryptographic primitive. One such primitive is the one-time memory (OTM), introduced by Goldwasser, Kalai, and Rothblum [CRYPTO 2008], which is a classical functionality modeled after a non-interactive 1-out-of-2 oblivious transfer, and which is complete for one-time classical and quantum programs. It is known that secure OTMs do not exist in the standard model in both the...

We propose the concept of pseudorandom quantum states, which appear random to any quantum polynomial-time adversary. This offers a computational approximation to perfect randomness on quantum states (analogous to a cryptographic pseudorandom generator), as apposed to some statistical notion of quantum pseudorandomness in the literature, such as quantum t-designs (analogous to t-wise independent distributions). Under the assumption that quantum-secure one-way functions exist, we present...

Public key quantum money can be seen as a version of the quantum no-cloning theorem that holds even when the quantum states can be verified by the adversary. In this work, investigate quantum lightning, a formalization of ``collision-free quantum money'' defined by Lutomirski et al. [ICS'10], where no-cloning holds even when the adversary herself generates the quantum state to be cloned. We then study quantum money and quantum lightning, showing the following results: - We demonstrate...

Cryptographic agility is the ability to switch to larger cryptographic parameters or different algorithms in the case of security doubts. This very desirable property of cryptographic systems is inherently difficult to achieve in cryptocurrencies due to their permanent state in the blockchain: for example, if it turns out that the employed signature scheme is insecure, a switch to a different scheme can only protect the outputs of future transactions but cannot fix transaction outputs...

The fisherman caught a quantum fish. "Fisherman, please let me go", begged the fish, "and I will grant you three wishes". The fisherman agreed. The fish gave the fisherman a quantum computer, three quantum signing tokens and his classical public key. The fish explained: "to sign your three wishes, use the tokenized signature scheme on this quantum computer, then show your valid signature to the king, who owes me a favor". The fisherman used one of the signing tokens to sign the document...

Quantum cryptography is the art and science of exploiting quantum mechanical effects in order to perform cryptographic tasks. While the most well-known example of this discipline is quantum key distribution (QKD), there exist many other applications such as quantum money, randomness generation, secure two- and multi-party computation and delegated quantum computation. Quantum cryptography also studies the limitations and challenges resulting from quantum adversaries---including the...

Forty years ago, Wiesner pointed out that quantum mechanics raises the striking possibility of money that cannot be counterfeited according to the laws of physics. We propose the first quantum money scheme that is (1) public-key, meaning that anyone can verify a banknote as genuine, not only the bank that printed it, and (2) cryptographically secure, under a "classical" hardness assumption that has nothing to do with quantum money. Our scheme is based on hidden subspaces, encoded as the...

Blind signatures (BS), introduced by Chaum, have become a cornerstone in privacy-oriented cryptography. Using hard lattice problems, such as the shortest vector problem, as the basis of security has advantages over using the factoring or discrete logarithm problems. For instance, lattice operations are more efficient than modular exponentiation and lattice problems remain hard for quantum and subexponential-time adversaries. Generally speaking, BS allow a signer to sign a message without...

Recent experimental results in quantum cryptography have renewed the interest in information-theoretically secure ciphers. In April 2004, in Vienna a bank transfer was secured by means of a one time pad encryption, with the key material being derived from a quantum key exchange. However, in this experiment the integrity of the transmitted message remained unprotected. This can have severe consequences, if the bank transfer form itself contains no authentication mechanism and there is a...

It had been widely claimed that quantum mechanics can protect private information during public decision in for example the so-called two-party secure computation. If this were the case, quantum smart-cards could prevent fake teller machines from learning the PIN (Personal Identification Number) from the customers' input. Although such optimism has been challenged by the recent surprising discovery of the insecurity of the so-called quantum bit commitment, the security of quantum two-party...