Schrödinger's cash: Minting quantum money

THERE is something special about cold, hard cash. Perhaps it is that its value is guaranteed by the government of the day, or that you can stash it under the bed when a banking collapse threatens. Maybe it is the freedom that cash allows: the ability to live without banks or credit cards or taxes.

Quantum physicists think a lot about cash. Not just any old money, you understand. They think about quantum cash. Quantum banknotes aren't like credit cards or dollar bills. They are simply information: a mixture of bits - the 0s and 1s that we use to send electronic transactions - and quantum bits, or qubits, that are governed by the laws of quantum mechanics and can be both a 0 and 1 at the same time.

Since quantum money is just information, it can be stored and transmitted just like a digital picture or a text file. But because it has quantum properties too, it cannot be copied. It is this combination that makes quantum cash so attractive: whoever is in possession of it has exclusive and unequivocal ownership of it, just as with hard, physical cash and unlike a credit card. That is not the only use for quantum cash, though. To physicists, quantum cash is a toy problem, a sort of test case with which to study the strange properties of quantum mechanics.

Now the theoretical foundations are almost in place that could one day allow quantum cash to become a reality. These techniques could potentially be useful for other applications, too, such as making software impossible to pirate.

The idea of quantum money was first suggested in 1968 by Stephen Wiesner, a physicist then at Columbia University in New York. He envisaged creating a banknote containing light traps that could somehow store a few dozen photons. Being quantum objects, photons can never be counterfeited thanks to something called the no-cloning theorem. This states that quantum objects can never be perfectly copied since any measurement of the original also destroys its ability to be a 0 and a 1 at the same time and forces it to be one or the other.

In Wiesner's scheme, the polarisation of these photons would act as a unique identifier for the banknote. These polarisations would be known only to the bank, so anybody wanting to check the authenticity of the banknote need only take it to their local branch, which would use its prior knowledge of the polarisations to check it. And since the photon states cannot be copied, neither can the banknote.

Wiesner's original idea has a serious flaw. One important feature of a practical currency is that anybody should be able to authenticate it. That is why the banknotes in your wallet have watermarks, holograms and ink that fluoresces in ultraviolet light - features that allow anybody to be pretty sure that the banknote is real. But with Wiesner's quantum money, you would have to take your quantum cash to the bank every time you want to check it. "That just wouldn't work," says Scott Aaronson, a computer scientist at the Massachusetts Institute of Technology.

Wiesner's quantum money remained little more than a theoretical oddity for 40 years and was pretty much forgotten, though his work on exploiting quantum mechanics for sending secret messages became hugely influential. Then last year, Aaronson proposed a new approach that does away with the banknote and concentrates instead on the stream of information that represents quantum cash.

Talk to cryptographers about protecting information and they will tell you that there are two different kinds of security. The gold standard is "informational security", where mathematicians can prove beyond doubt that a piece of information is secure. An example of informational security is quantum key distribution, a technique that exploits the laws of quantum mechanics to send messages in a way that cannot be surreptitiously overheard. The security is guaranteed by the laws of physics.

This kind of security is hard to come by, so we usually have to resort to the second type, called "computational security". Here information is protected by a code that, while not impossible to break, is so difficult to crack that nobody could feasibly do it, even with the world's most powerful computers. An example is the RSA algorithm, which is widely used to encrypt e-commerce transactions and other forms of communication.

RSA is an example of public key cryptography, in which the method for encrypting messages is simple and made available to anyone. However, the process for decrypting messages is kept secret, so only those in the know can read encrypted messages. The security of public key cryptography relies on a certain kind of mathematical relation, called a trapdoor function, that is asymmetric - easy to calculate in one direction but hard to do in reverse. The most famous example is multiplication. It is easy to multiply two numbers together to get a third, but much harder to start with the third number and work out the two factors used to generate it.

This is exactly what RSA encryption relies on, and the fact that it is always possible to make the starting numbers so big that no computer could factor their product in any reasonable time. Computer scientists call this kind of problem "computationally hard". RSA encryption may not be impossible to crack but it is so hard to tackle that it is practically impossible.

Wiesner's quantum banknotes are informationally secure, but making quantum money that anybody can authenticate changes the nature of the problem significantly. So Aaronson decided to devise a quantum money scheme that was merely computationally secure, and he based it on the kind of asymmetric mathematics behind public key cryptography.

In Aaronson's scheme, so-called "public key quantum money" is always issued in two parts. The first is the quantum state. This might belong to a group of photons with a particular set of polarisations, which the issuing bank keeps secret. The second part is a circuit (or the plans for such a circuit) that verifies whether the secret set of polarisations is present in something purporting to be quantum cash. Such a circuit would be to quantum transactions what an ultraviolet light is to today's banknotes. A shopkeeper might keep a device containing the circuit behind the till to check any quantum money used in a transaction, rather than having to take the money to a bank as in Wiesner's scheme.

This circuit performs the same role as the trapdoor functions in public key cryptography. The process of verifying the secret using the circuit is easy but the process of working out the secret polarisations of the photons is hard. The security of the scheme relies entirely on the difficulty of this task.

Aaronson gives the example of a thief who has broken into a shop and stolen the quantum verifier. The thief then proceeds to feed randomly generated quantum states into the verifier, hoping to find one that it accepts. "I proved that a counterfeiter would have to use this box an unfeasible number of times," he says. "This rules out a large class of 'brute-force' attacks against quantum money."

The devil is in the detail, however. In trying to flesh out exactly how to construct a quantum verification circuit, he and others have run up against one problem after another.

The trouble with computational security is its reliance on the idea that a mathematical process is much more difficult in one direction than the other. While this may seem obvious from all attempts to perform calculations on the chosen task, it is often merely an assumption. So the task for Aaronson and his colleagues is to find a quantum process which we have good grounds to think is asymmetric, and which could therefore form the basis for the security of quantum money. "That's an entirely new problem in cryptography," says Aaronson.

How secure is secure?

Not having an agreed way of making tasks computationally secure makes this problem much more difficult to solve. Aram Harrow, a mathematical physicist at the University of Bristol, UK, agrees. "We need to find a plausible assumption to base the security on, and unfortunately it's very difficult to show that anything is very computationally hard," he says.

That hasn't stopped Aaronson and his colleagues trying. Over the last year or so, they have teamed up to form a "quantum money club" to find new ways of making quantum money computationally secure. They then look for weak links in their own work. Together, they have developed several important cla**** of scheme and then gone on to break each one.

Last summer, Aaronson published one such scheme, claiming the first evidence for quantum money that anyone can verify and only banks can clone. "That one stood for five months," he says. Then a group turned up at his door with a proof it wasn't true. "I did the only thing I could in such circ**stances: I joined their paper."

In December, their joint paper breaking Aaronson's own quantum money scheme was published on the physics preprint server (arxiv.org/abs/0912.3825). The team behind it has an impressive pedigree and includes theoretical physicist Peter Shor of MIT, who previously developed a quantum computer algorithm that could factor numbers faster than a conventional computer.

The looph*** they found in Aaronson's scheme was that the verification algorithm does not make a perfect check on the photon polarisations. So a hacker doesn't need to know the original quantum state to fool the verifying circuit into thinking the secret polarisations are present. To counterfeit this particular form of quantum money, the hacker would only need a state close enough to the original to pass the test. This is much easier for a hacker to work out, says Andrew Lutomirski, a graduate student in theoretical physics at MIT and one of the group that broke Aaronson's scheme.

All was not lost, however. As well as breaking this scheme, Aaronson, Lutomirski and colleagues put forward a new one which takes a different approach: it produces a quantum state that is secret, even from the bank that created it. This time the bank has a different way of making the quantum states that form the secret part of the quantum money. As part of the "minting" process, the bank measures part of the secret quantum state while leaving the rest of the state unmeasured. This leaves the unmeasured part with certain properties that work like a quantum watermark. And a verifying circuit can use this subsequently to authenticate the money.

This means the bank can publish a verification algorithm that allows anybody to check the money, but which cannot be used to counterfeit it. Aaronson and Lutomirski call this "collision-free quantum money". The beauty of this public key scheme is that it is just as difficult for the bank to create counterfeits as for anybody else - a property that even conventional money does not have.

There is a sting in the tail, however. While the members of the quantum money club are pretty sure that collision-free quantum money is computationally secure, they have not been able to prove it.

Despite the failure to nail quantum cash, the efforts to study it have revealed new insights into the behaviour of quantum states. Some members of the quantum money club are using these ideas to explore the limits of what can be known about a quantum state. Quantum mechanics says you cannot measure a state without destroying it, but the team's work on quantum money has shown that it is possible to verify a quantum state is physically present, even though they know nothing about that state. In effect, they are able to get some information about it without destroying it.

Now the quantum money club is exploring what other information can be extracted about a quantum state using verifying algorithms. That is potentially bad news for quantum money: it may be that a verifying circuit will always allow the user to gain enough information about the quantum state to make a counterfeit. However, Shor and colleagues suspect not.

The constant creation and cracking of quantum money schemes is forcing them to the conclusion that a radically new approach is needed. "Much as we wish it were otherwise, it seems possible that public key quantum money intrinsically requires a new mathematical leap of faith," they say in their paper. They have in mind a revolution as big as the one that made public key cryptography possible in the 1970s - though when that new breakthrough might happen and what advances will set it off is anybody's guess.

Even so, the process of studying this problem is turning out to be fruitful. "It's opening up a wh*** new area to study," says Harrow. The greatest legacy of the race to create quantum money may not be a new kind of currency, at least not in the short term. Instead, we are getting a better understanding of the fundamental laws of physics. It is a trade-off most would say was worthwhile.