Ever since there’s been money, there have been people trying to counterfeit it. Preventing counterfeiting is one of the oldest “security problems” facing human civilization, and one that has to be solved reasonably well before a market economy becomes possible. The problem attracted the attention of no less than Isaac Newton, who, in his role as Master of the Mint, redesigned the English coins by adding milled edges that were difficult for counterfeiters to reproduce. (Newton also personally oversaw the hangings of many counterfeiters.) Today, paper money comes equipped with an arsenal of anti-counterfeiting measures, including holograms, embedded strips, “microprinting,” and special inks that look different depending on the angle.
Yet it should surprise no one that, as mints have become more technically sophisticated, so have counterfeiters—leading to an arms race with no obvious winner. From a cryptographer’s perspective, the root of the problem is that unforgeable cash seems theoretically impossible. For whatever printing technology a government can build, a criminal organization could in principle build as well. Furthermore, if we abstract away the printing details, and see a banknote as just a pattern of information—that is, a string of 1’s and 0’s—then we know that any information that can be read can also be copied an unlimited number of times. Of course, the credit card companies (and services such as PayPal) get around this problem by having a trusted bank authorize each and every transaction. But secure digital cash without such a “middleman”—that is, with the same flexibility and convenience as ordinary cash—would appear to be a fundamental impossibility.
And it is a fundamental impossibility—at least in classical physics. Since the 1920’s, though, we’ve known that the universe obeys a different, less intuitive set of rules when probed at the microscopic scale. In quantum physics, any object (such as an electron or photon) exists in a sort of smear over all possible configurations—until the object is measured, at which point it “collapses” to a single, randomly-chosen configuration. Furthermore, this “collapse” is an irreversible process: Heisenberg’s famous Uncertainty Principle says you can either measure the position of a particle or its momentum, but not both to unlimited accuracy. One consequence of the Uncertainty Principle is the so-called No-Cloning Theorem: there can be no “subatomic Xerox machine” that takes an unknown particle, and spits out two particles with exactly the same position and momentum as the original one (except, say, that one particle is two inches to the left). For if such a machine existed, then we could determine both the position and momentum of the original particle—by measuring the position of one “Xerox copy” and the momentum of the other copy. But that would violate the Uncertainty Principle.
In 1969, the physicist Stephen Wiesner wrote a remarkable manuscript, pointing out that the No-Cloning Theorem raises the possibility of uncopyable cash: dollar bills whose authenticity would be guaranteed by quantum physics. Alas, Wiesner was unable to publish the manuscript for more than a decade, since the field of quantum computing and information (to which it naturally belonged) had not yet been invented.
Here’s how Wiesner’s scheme works: besides an ordinary serial number, each dollar bill would contain (say) a few hundred photons, which the central bank “polarized” in random directions when it issued the bill. (Let’s leave the engineering details to later!) The bank, in a massive database, remembers the polarization of every photon on every bill ever issued. If you ever want to verify that a bill is genuine, you just take it to the bank, and the bank uses its knowledge of the polarizations to measure the photons. On the other hand, the No-Cloning Theorem ensures that someone who doesn’t know the polarization of a photon can’t produce more photons with the same polarizations. And that’s why copying a bill is impossible—or rather, can succeed with only a tiny probability, which decreases exponentially with the number of photons on the bill.
Despite its elegance, Wiesner’s quantum money is a long way from replacing the classical money of today. The main technical problem is that photons can’t be stored for any significant amount of time. And while other particles (like electrons) can be stored, they tend to lose their polarizations in a matter of seconds at most—even in near-absolute-zero laboratory conditions, let alone someone’s wallet. And once the particles lose their polarizations, the bill is ruined, since it can no longer be verified by the bank.
Yet, even if we could solve the technological problems, Wiesner’s scheme would still have a severe drawback, which you might have noticed already. The drawback is that the bank—the original issuer of the bill—is the only one who can verify that bill as genuine. Ideally, printing bills ought to be the exclusive prerogative of the bank, but the checking process ought to be open to anyone: think of a convenience-store clerk holding up a $20 bill to a light.
But is it possible, even in principle, to have quantum money satisfying all three requirements: (1) the bank can print it, (2) anyone can test it, and (3) no one (except possibly the bank) can copy it? Surprisingly, this question has been open for forty years, from Wiesner’s time till today. I recently took up the question, and reached three new conclusions about it. First, if such a money scheme is possible at all, then unlike Wiesner’s, its security will have to depend on more than quantum physics. Instead, like with RSA and essentially every other modern encryption code, it will also need some assumption about computational hardness. In other words, a counterfeiter with all the time in the world really could copy bills—so everything rests on the hope that the computations needed to foil the scheme take too long to be practical.
The second conclusion was more positive. I showed that it’s possible to have quantum money that remains hard to copy, even after a counterfeiter gains access to a device for checking the money—provided the counterfeiter can’t reverse-engineer the checking device to see how it was built. This result rules out a large class of “brute-force” attacks against quantum money, though it says nothing about “subtle” attacks that depend on details of the checking device.
Third, I found that it’s possible to create quantum money schemes that seem hard to break—but, alas, there appears to be no way to prove those schemes secure, even by the relaxed standards of modern cryptography. In other words, while quantum money satisfying all three requirements might be possible, believing that seems to require a new mathematical “leap of faith.” That might not be as bad as it sounds: by analogy, the famous RSA cryptosystem also demanded a new leap of faith when it was introduced in the 1970s, namely that factoring huge numbers takes a prohibitively long time.
But now I should let you in on an embarrassing secret. I and colleagues at MIT—including Peter Shor in Applied Math and Ed Farhi, David Gosset, Avinatan Hassidim, and Andy Lutomirski in Physics—have been thinking about the quantum money problem on and off for almost a year, and we’ve had enormous trouble coming up with schemes that we haven’t also been able to break. Eventually, I proposed a scheme—wherein each dollar bill would be augmented with a special class of quantum states called “random stabilizer states” —that stood for a few months. Alas, in an upcoming paper, Gosset, Hassidim, Lutomirski, Shor, and I break that scheme.
But there’s a silver lining: in the same paper, we also propose a new quantum money scheme that’s impervious to the previous attacks. This scheme has an extremely curious feature: as part of the minting process, we have the bank measure part of the quantum state going into each dollar bill—a random and irreversible process—while leaving the rest of the state unmeasured. The measured part can be thought of as the classical “serial number” of the bill, and the unmeasured part as the quantum “certificate of authenticity.” As a result, not even the bank knows in advance the serial number of the bill it’s going to print, nor can it print two bills with the same serial number, even if it wants to.
Time will tell whether our new scheme finally solves the quantum money problem, or whether it too succumbs to a clever attack. In the meantime, maybe cash itself will go out of fashion, as some technologists have been predicting for decades. But if it doesn’t, then the “classical” way to deter counterfeiters—printing the bills with hidden threads, special ink, and so on—will probably remain popular for a while to come.
Read more at Scott Aaronson’s blog “Shtetl-Optimized.”