We propose an information theoretically secure secret-key quantum money scheme in which the verification of a coin is classical and consists of only one round; namely, a classical query from the user to the bank and an accept/reject answer from the bank to the user. A coin can be verified polynomially (on the number of its qubits) many times before it expires. Our scheme is an improvement on Gavinsky's scheme [Gavinsky, Computational Complexity, 2012], where three rounds of interaction are needed and is based on the notion of quantum retrieval games. Moreover, we propose a public-key quantum money scheme which uses one-time memories as a building block and is computationally secure in the random oracle model. This construction is derived naturally from our secret-key scheme using the fact that one-time memories are a special case of quantum retrieval games.
We propose an information theoretically secure secret-key quantum money scheme in which the verification of a coin is classical and consists of only one round; namely, a classical query from the user to the bank and an accept/reject answer from the bank to the user. A coin can be verified polynomially (on the number of its qubits) many times before it expires. Our scheme is an improvement on Gavinsky's scheme [Gavinsky, Computational Complexity, 2012], where three rounds of interaction are needed and is based on the notion of quantum retrieval games. Moreover, we propose a public-key quantum money scheme which uses one-time memories as a building block and is computationally secure in the random oracle model. This construction is derived naturally from our secret-key scheme using the fact that one-time memories are a special case of quantum retrieval games.
Private quantum money allows a bank to mint quantum money states that it can later verify, but that no one else can forge. In classically verifiable quantum money -- introduced by Gavinsky (CCC 2012) -- the verification is done via an interactive protocol between the bank and the user, where the communication is classical, and the computational resources required of the bank are classical. In this work, we consider memoryless interactive protocols in which the minting is likewise classical, and construct a private money scheme that achieves these two notions simultaneously (i.e., classical verification and classical minting). We call such a construction a private semi-quantum money scheme, since all the requirements from the bank in terms of computation and communication are classical.
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.
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 key, and the scheme is secure against counterfeiting and sabotage, a new security notion that appears in the franchised model. Finally, we construct franchised quantum money and prove security assuming one-way functions.
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.
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.
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.