The no-cloning theorem can be used as a basis for quantum money constructions which guarantee unconditionally unforgeable currency. Existing schemes, however, either (i) require long-term quantum memory and quantum communication between the user and the bank in order to verify the validity of a bill or (ii) fail to protect user privacy due to the uniqueness of each bill issued by the bank, which can allow its usage to be tracked. We introduce a construction of single-use quantum money that gives users the ability to detect whether the issuing authority is tracking them, employing an auditing procedure for which we prove unconditional security. Bill validation is classical, and hence does not require long-term quantum memory or quantum communication, making the protocol relatively practical to deploy. We discuss potential applications beyond money, including anonymous one-time pads and voting.
The no-cloning theorem can be used as a basis for quantum money constructions which guarantee unconditionally unforgeable currency. Existing schemes, however, either (i) require long-term quantum memory and quantum communication between the user and the bank in order to verify the validity of a bill or (ii) fail to protect user privacy due to the uniqueness of each bill issued by the bank, which can allow its usage to be tracked. We introduce a construction of single-use quantum money that gives users the ability to detect whether the issuing authority is tracking them, employing an auditing procedure for which we prove unconditional security. Bill validation is classical, and hence does not require long-term quantum memory or quantum communication, making the protocol relatively practical to deploy. We discuss potential applications beyond money, including anonymous one-time pads and voting.
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.
Abstract Unforgeable quantum money tokens were the first invention of quantum information science, but remain technologically challenging as they require quantum memories and/or long-distance quantum communication. More recently, virtual “S-money” tokens were introduced. These are generated by quantum cryptography, do not require quantum memories or long-distance quantum communication, and yet in principle guarantee many of the security advantages of quantum money. Here, we describe implementations of S-money schemes with off-the-shelf quantum key distribution technology, and analyse security in the presence of noise, losses, and experimental imperfection. Our schemes satisfy near-instant validation without cross-checking. We show that, given standard assumptions in mistrustful quantum cryptographic implementations, unforgeability and user privacy could be guaranteed with attainable refinements of our off-the-shelf setup. We discuss the possibilities for unconditionally secure (assumption-free) implementations.
Quantum tokens are underlying primitives for quantum money and network proposals, which leverage the no-cloning theorem to realize unforgeable authentication. A relevant but overlooked type of attack to such architectures is one in which a hacker steals the classical side information about the token states from the issuing agent (e.g., a bank), enabling the forgery of fake tokens without violating the no-cloning theorem. Our proposal addresses this threat by removing the classical side information about the token states, where instead a copy of the token is stored at the bank, i.e. a quantum vault. This copy can be accessed by anyone to perform authentication, consuming the token pair in the process. We benchmark the protocol and identify quality parameters within a hardware agnostic framework employing IBMQ processors, such that the protocol is applicable to arbitrary quantum platforms. By comparing the efficiency with which genuine tokens are produced and authenticated against a possible estimate-and-forge attack, we quantify the security of the protocol. We achieve probabilities lower than 10−4 for false-negative errors (Type 1) and 10−10 for successful attacks (Type 2) when considering quantum bills composed of 200 tokens, even in the worst performing processor and most conservative uncertainty estimate. The quantum vault not only protects both user and bank symmetrically with the same quantum principles, but provides a step towards public key authentication, since any untrusted party can have access granted by the bank to the tokens' authentication interface without being able to clone them. Besides this bank-mediated form of publicly accessible verifiability, our proposal achieves traceability and revocability, since the bank retains the vault copy of the tokens.
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., only the bank can verify the money states, or public, meaning anyone can verify. In this work, we propose a way to lift any private quantum coin scheme -- which is known to exist based on the existence of one-way functions, due to Ji, Liu, and Song (CRYPTO'18) -- to a scheme that closely resembles a public quantum coin scheme. Verification of a new coin is done by comparing it to the coins the user already possesses, by using a projector on to the symmetric subspace. No public coin scheme was known prior to this work. It is also the first construction that is very close to a public quantum money scheme and is provably secure based on standard assumptions. Finally, the lifting technique, when instantiated with the private quantum coins scheme~\cite{MS10}, gives rise to the first construction that is close to an inefficient unconditionally secure public quantum money scheme.
Abstract Quantum tokens are underlying primitives for quantum money and network proposals, which leverage the no-cloning theorem to realize unforgeable authentication. A relevant but overlooked type of attack to such architectures is one in which a hacker steals the classical side information about the token states from the issuing agent (e.g., a bank), enabling the forgery of fake tokens without violating the no-cloning theorem. Our proposal addresses this threat by removing the classical side information about the token states, where instead a copy of the token is stored at the bank, i.e. a quantum vault. This copy can be accessed by anyone to perform authentication, consuming the token pair in the process. We benchmark the protocol and identify quality parameters within a hardware agnostic framework employing IBM Quantum processors, such that the protocol is applicable to arbitrary quantum platforms. By comparing the efficiency with which genuine tokens are produced and authenticated against a possible estimate-and-forge attack, we quantify the security of the protocol. We achieve probabilities lower than 10-4 for false-negative errors (Type 1) and 10-10 for successful attacks (Type 2) when considering quantum bills composed of 200 tokens, even in the worst performing processor and a conservative uncertainty estimate. The quantum vault not only protects both user and bank symmetrically with the same quantum principles, but provides a step towards public key authentication, since any untrusted party can have access granted by the bank to the tokens' authentication interface without being able to clone them. Besides this bank-mediated form of publicly accessible verifiability, our proposal achieves traceability and revocability, since the bank retains the vault copy of the tokens.
Forty years ago, Wiesner proposed using quantum states to create money that is physically impossible to counterfeit, something that cannot be done in the classical world. However, Wiesner's scheme required a central bank to verify the money, and the question of whether there can be unclonable quantum money that anyone can verify has remained open since. One can also ask a related question, which seems to be new: can quantum states be used as copy-protected programs, which let the user evaluate some function f, but not create more programs for f? This paper tackles both questions using the arsenal of modern computational complexity. Our main result is that there exist quantum oracles relative to which publicly-verifiable quantum money is possible, and any family of functions that cannot be efficiently learned from its input-output behavior can be quantumly copy-protected. This provides the first formal evidence that these tasks are achievable. The technical core of our result is a "Complexity-Theoretic No-Cloning Theorem," which generalizes both the standard No-Cloning Theorem and the optimality of Grover search, and might be of independent interest. Our security argument also requires explicit constructions of quantum t-designs. Moving beyond the oracle world, we also present an explicit candidate scheme for publicly-verifiable quantum money, based on random stabilizer states; as well as two explicit schemes for copy-protecting the family of point functions. We do not know how to base the security of these schemes on any existing cryptographic assumption. (Note that without an oracle, we can only hope for security under some computational assumption).