Toward Secure Quantum Money

Abstract

The no-cloning theorem of quantum physics may enable the creation of uncounterfeitable money. The design's central idea is to represent money as a quantum state. An arbitrary quantum state, whose superposition we know nothing about, is impossible to clone, and measuring the state will collapse the superposition. A quantum money scheme could be implemented to represent money if qubit coherence times improve enough to store a superposition over a period of weeks or longer.

Any quantum money scheme needs a verification algorithm, a method to distinguish valid and counterfeit money without destroying a valid state. In the first scheme proposed for quantum money, the mint that created the money state keeps a private description of the state and uses the description to verify a purported money state [Wie83]. This description, called the trapdoor, can also be used to produce duplicate states, so the mint must keep the trapdoor secret.

Recently, several schemes have been proposed for public key quantum money, which anyone can verify using only public information (a public trapdoor). [Zha17]’s proposed scheme, called quantum lightning, is a stronger form of public key quantum money where even the mint cannot duplicate a valid state. However, none of the public key schemes have been proven secure. It is difficult to show that the public trapdoor cannot be used to produce counterfeit states.

In this work, we show that [Zha17]’s quantum lightning construction is not secure. The construction's purported security is based on the multi-collision resistance of a hash function. However, we show how to break this collision-resistance by constructing collisions in the span of the verification algorithm's trapdoor. We call this the trapdoor span attack.

We also give the first detailed description and analysis of [Zha17]'s attempted construction for quantum lightning based on the SIS problem. The trapdoor span attack is powerful, as it allows counterfeiting in this construction as well.

Finally, we propose and analyze two modified versions of the construction based on SIS. These modifications are designed to foil the trapdoor span attack. The first proposal, though unsuccessful, could be useful for future attempts. The second construction is promising, but much more work is needed to develop and analyze it. We hope that the second construction may lead to a secure construction of quantum money.