Emerging Technology from the arXiv

A View from Emerging Technology from the arXiv

Unexpected Problems For Quantum Money

Proving that quantum money can never be copied–even by the banks that created it–turns out to be harder than expected.

  • December 23, 2009

In 1969, Stephen Wiesner at Columbia University suggested that the quantum properties of photons could be used to make “quantum money” that was impossible to counterfeit. The idea was to store a few dozen photons in light traps in each bill. and ensure that the polarisation of these photons was known only to the bank.

Since quantum states are impossible to copy, such a bank note could never be copied. And anyone wanting to check the note would need only take it to the issuing bank which could use its prior knowledge of the polarisations to test the bill’s veracity.

Wiesner’s idea became an inspiration for the generation of quantum physicists who developed quantum encryption, the ability to send a message with perfect security.

But there’s a practical problem with Wiesner’s quantum money. The most serious drawback is that only the issuing bank can verify that a bill is genuine whereas one of the important features of any practical currency is that anybody must be able to determine its veracity.

What’s needed is some kind of asymmetric technique that allows a bank to create quantum money that cannot be copied but also allows anyone to check it.

As it happens, something very similar is possible with so-called public key encryption techniques. Here anybody can encode a message with a publicly available key but the encrypted message can only be decoded with another key which is kept private.

Public-key encryption depends on certain types of mathematical functions that are easy to calculate in one direction but hard to do in reverse. The most famous example is multiplication. It’s easy to multiply two numbers together to get a third. But the problem of starting with the third number and working out which two generated it, a process called factoring, is much harder.

The security of public key encryption techniques rests on the idea that factoring can always be made so hard that it is effectively impossible for any conventional computer to do it; that is any computer that relies only on classical mechanics to do its number crunching.

Is it possible to design similarly asymmetric protocols that make quantum money possible?

One idea is to have the bank to write down a description of a quantum state that can be efficiently generated and then to manufacture the state in that. Of course, this description must be kept secret. The bank then constructs an algorithm to verify the state (but not reproduce it), a so-called verification circuit.

Quantum money then consists of both the quantum state and the verification circuit. Of course, if anybody can work out the secret description, they can print as many copies of the quantum money they like. But the security of quantum money relies on the difficulty of deducing the secret description given both the verification circuit and a copy of the state, which the money contains.

But there’s a problem. The bank knows the secret description and so can make as many copies as it likes of this money without anybody being any the wiser.

Today Andrew Lutomirski and a crack team of quantum eggheads at the Massachusetts Institute of Technology in Cambridge suggest how to close this loophole with an entirely new kind of quantum money which they call collision free.

Their idea is to use an entirely different state for the quantum money. This state is a superposition of an exponentially large number of unrelated terms each of which is created by the measurement of an equally exponential superposition. Incorporating this quantum measurement into the process of creating the quantum money ensures that a bank cannot reproduce this state, even though it knows how the initial superposition was created. At least, the bank cannot do this in any reasonable amount of time.

Lutomirski say that this form of quantum money can be verified using a Markov chain algorithm.

That’s an interesting development but the MIT team’s paper has a sting in the tail. Lutomirski and co say they expect that computationally secure collision-free quantum money is possible but are unable to give a proof.

“Surprisingly, the question of whether public-key quantum money schemes are possible under computational assumptions has remained open for forty years, from Wiesner’s time until today.”

And they finish with this jaw dropper: “Much as we wish it were otherwise, it seems possible that public-key quantum money intrinsically requires a new mathematical leap of faith, just as public-key cryptography required a new leap of faith when it was first introduced in the 1970s.”

That’s a surprising admission and a challenge.

But there’s another fly in the ointment for any scheme that depends for its security on the inability to carry out a calculation in polynomial time: it’s only secure under attack from conventional computers.

The trouble is that quantum mechanics may allow these kind of problem to be solved easily. Whatever mathematical leap of faith these authors are hoping for, it may just be the case that quantum money will only be “collision free” until quantum mechanics begins to play a significant role in processing information.

Ref:arxiv.org/abs/0912.3825: Breaking and Making Quantum Money: Toward a New Quantum Cryptographic Protocol

Cut off? Read unlimited articles today.

Become an Insider
Already an Insider? Log in.

Uh oh–you've read all of your free articles for this month.

Insider Premium
$179.95/yr US PRICE

Want more award-winning journalism? Subscribe and become an Insider.
  • Insider Premium {! insider.prices.premium !}*

    {! insider.display.menuOptionsLabel !}

    Our award winning magazine, unlimited access to our story archive, special discounts to MIT Technology Review Events, and exclusive content.

    See details+

    What's Included

    Bimonthly home delivery and unlimited 24/7 access to MIT Technology Review’s website.

    The Download. Our daily newsletter of what's important in technology and innovation.

    Access to the Magazine archive. Over 24,000 articles going back to 1899 at your fingertips.

    Special Discounts to select partner offerings

    Discount to MIT Technology Review events

    Ad-free web experience

    First Look. Exclusive early access to stories.

    Insider Conversations. Listen in as our editors talk to innovators from around the world.

  • Insider Plus {! insider.prices.plus !}* Best Value

    {! insider.display.menuOptionsLabel !}

    Everything included in Insider Basic, plus ad-free web experience, select discounts to partner offerings and MIT Technology Review events

    See details+

    What's Included

    Bimonthly home delivery and unlimited 24/7 access to MIT Technology Review’s website.

    The Download. Our daily newsletter of what's important in technology and innovation.

    Access to the Magazine archive. Over 24,000 articles going back to 1899 at your fingertips.

    Special Discounts to select partner offerings

    Discount to MIT Technology Review events

    Ad-free web experience

  • Insider Basic {! insider.prices.basic !}*

    {! insider.display.menuOptionsLabel !}

    Six issues of our award winning magazine and daily delivery of The Download, our newsletter of what’s important in technology and innovation.

    See details+

    What's Included

    Bimonthly home delivery and unlimited 24/7 access to MIT Technology Review’s website.

    The Download. Our daily newsletter of what's important in technology and innovation.

/
You've read all of your free articles this month. This is your last free article this month. You've read of free articles this month. or  for unlimited online access.