Prior studies on quantum money from knots, and the invariant money framework that generalizes it, anchor their security on the hardness of path-finding. However, we show that the hardness of path-finding is proven to be necessary for security under certain conditions. In other conditions, this assumption is not a direct anchoring hardness problem such that breaking it allows an adversary to forge a banknote directly. In particular, for quantum money from knots, even when the path-finding assumption does not hold, an adversary still cannot directly forge a banknote. The adversary needs to additionally prepare the uniform superposition over the paths it finds, which we show is as hard as the original problem. Existing security proofs supplement path-finding hardness with knowledge-of-path assumptions. While this combination is sufficient, it may not be necessary. We identify an assumption pair, preparation assumption and transfer assumption, that is both necessary and sufficient for the security of every invariant money scheme. Breaking either assumption directly enables a forgery. The preparation assumption says that no efficient algorithm, given the serial number of a banknote and one object measured from it, prepares a state that verification accepts. While quantum money security gives a forger one quantum state and asks for two that pass, our assumption concerns a problem that takes only classical inputs and asks for one quantum state that passes. This assumption is equivalent to security against forgers that measure their banknote first. Given that its inputs are classical, it is falsifiable and can be attacked and bounded like other computational problems. The transfer assumption covers forgers that keep the banknote coherent, stating that every such forger only has an advantage over the measure-first adversary by at most a polynomial factor.
Prior studies on quantum money from knots, and the invariant money framework that generalizes it, anchor their security on the hardness of path-finding. However, we show that the hardness of path-finding is proven to be necessary for security under certain conditions. In other conditions, this assumption is not a direct anchoring hardness problem such that breaking it allows an adversary to forge a banknote directly. In particular, for quantum money from knots, even when the path-finding assumption does not hold, an adversary still cannot directly forge a banknote. The adversary needs to additionally prepare the uniform superposition over the paths it finds, which we show is as hard as the original problem. Existing security proofs supplement path-finding hardness with knowledge-of-path assumptions. While this combination is sufficient, it may not be necessary. We identify an assumption pair, preparation assumption and transfer assumption, that is both necessary and sufficient for the security of every invariant money scheme. Breaking either assumption directly enables a forgery. The preparation assumption says that no efficient algorithm, given the serial number of a banknote and one object measured from it, prepares a state that verification accepts. While quantum money security gives a forger one quantum state and asks for two that pass, our assumption concerns a problem that takes only classical inputs and asks for one quantum state that passes. This assumption is equivalent to security against forgers that measure their banknote first. Given that its inputs are classical, it is falsifiable and can be attacked and bounded like other computational problems. The transfer assumption covers forgers that keep the banknote coherent, stating that every such forger only has an advantage over the measure-first adversary by at most a polynomial factor.
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 certain natural class of quantum money schemes from lattices cannot be secure. We use this theorem to break the recent quantum money scheme of Khesin, Lu, and Shor. **In the second part, we propose a framework for building quantum money and quantum lightning we call invariant money which abstracts some of the ideas of quantum money from knots by Farhi et al.(ITCS'12). In addition to formalizing this framework, we provide concrete hard computational problems loosely inspired by classical knowledge-of-exponent assumptions, whose hardness would imply the security of quantum lightning, a strengthening of quantum money where not even the bank can duplicate banknotes. **We discuss potential instantiations of our framework, including an oracle construction using cryptographic group actions and instantiations from rerandomizable functional encryption, isogenies over elliptic curves, and knots.
A quantum money scheme enables a trusted bank to provide untrusted users with verifiable quantum banknotes that cannot be forged. In this work, we report a proof-of-principle experimental demonstration of the preparation and verification of unforgeable quantum banknotes. We employ a security analysis that takes experimental imperfections fully into account. We measure a total of $3.6\ifmmode\times\else\texttimes\fi{}{10}^{6}$ states in one verification round, limiting the forging probability to ${10}^{\ensuremath{-}7}$ based on the security analysis. Our results demonstrate the feasibility of preparing and verifying quantum banknotes using currently available experimental techniques.
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 zero-sets of random multivariate polynomials. A main technical advance is to show that the "black-box" version of our scheme, where the polynomials are replaced by classical oracles, is unconditionally secure. Previously, such a result had only been known relative to a quantum oracle (and even there, the proof was never published). Even in Wiesner's original setting -- quantum money that can only be verified by the bank -- we are able to use our techniques to patch a major security hole in Wiesner's scheme. We give the first private-key quantum money scheme that allows unlimited verifications and that remains unconditionally secure, even if the counterfeiter can interact adaptively with the bank. Our money scheme is simpler than previous public-key quantum money schemes, including a knot-based scheme of Farhi et al. The verifier needs to perform only two tests, one in the standard basis and one in the Hadamard basis -- matching the original intuition for quantum money, based on the existence of complementary observables. Our security proofs use a new variant of Ambainis's quantum adversary method, and several other tools that might be of independent interest.
There are various practical obstacles in quantum cryptography. These include the problems that arise in implementing quantum cryptographic protocols with current and near-term technology, and those that come with the development and security analysis of new protocols. In this work, we examine a few of these obstacles and, for each one, we highlight an approach that aims to mitigate it. We start by examining the setting of device-independence, with oblivious transfer in the bounded-quantum-storage-model as the primitive of interest. The typical approach to enabling device-independence is the use of a Bell-inequality violation, which requires a strict non-communication assumption that is practically difficult to enforce. We develop and analyze the security of a device-independent oblivious transfer protocol that replaces the Bell-inequality violation approach with a computational assumption, thereby relaxing the non-communication assumption. Our second topic examines the problem of noise in a quantum money scheme. We show how to achieve noise-tolerance in the public-key setting. Our scheme can be seen as a generalization of the [AC12] scheme: a valid banknote is now a subspace state possibly affected by noise, and verification is performed by using classical oracles to check for membership in "larger spaces." Additionally, a banknote in our scheme is minted by preparing conjugate coding states and applying a unitary. For our last topic, we consider the general task of proving security against a specious adversary, which is the quantum analogue of the classical semi-honest adversary. A useful feature of specious adversaries is that security against them can guarantee security against stronger adversaries [DNS12]. This motivates the search for a canonical specious adversary, where proving security against such an adversary guarantees security against the entire class of specious adversaries. Within a restricted setting, we define a particular specious adversary and show that it satisfies our definition of canonical.
Quantum cryptography leverages unclonability to enable a wide range of cryptographic applications that are impossible classically, such as digital currency protected against counterfeiting by quantum mechanics. Security requires that no efficient user can produce even one additional valid banknote beyond those already in their possession. However, existing security bounds weaken as the number of banknotes available to a user increases.
In this paper, we study a construction of quantum money whose asymptotic query security does not deteriorate as long as the number of banknotes available to a user remains below the scale required for state tomography. In particular, we show that the construction based on an n-qubit Haar-random state and a reflection oracle achieves optimal query security: unless a user holds Ω(2n) banknotes, their existing banknotes cannot asymptotically speed up counterfeiting --- their best possible attack is the same as if they do not have any banknotes. To establish this result, we develop a framework based on the compressed-oracle technique for defining and analyzing progress measures for quantum tasks such as Haar state cloning. Furthermore, we prove a tight lower bound for generating r additional copies, give a matching attack, and apply our results to quantum copy-protection.
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. 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 currency scheme: privacy. In this work, we first further develop the formal definitions of privacy for quantum money schemes. Then, we construct the first public-key quantum money schemes that satisfy these security notions. Namely, - Assuming existence of indistinguishability obfuscation (iO) and hardness of Learning with Errors (LWE), we construct a public-key quantum money scheme with anonymity against users and traceability by authorities. Since it is a policy choice whether authorities should be able to track banknotes or not, we also construct an untraceable money scheme from the same cryptographic assumptions, where no one (not even the authorities) can track banknotes. Further, we show that the no-cloning principle, a result of quantum mechanics, allows us to construct schemes, with security guarantees that are classically impossible, for a seemingly unrelated application: voting! - Assuming iO and LWE, we construct a universally verifiable quantum voting scheme with classical votes. Finally, as a technical tool, we introduce the notion of publicly rerandomizable encryption with strong correctness, where no adversary is able to produce a malicious ciphertext and a malicious randomness such that the ciphertext before and after rerandomization decrypts to different values! We believe this might be of independent interest. - Assuming LWE, we construct a (post-quantum) classical publicly rerandomizable encryption scheme with strong correctness.