Quantum Tokens for Digital Signatures

This paper wins “best abstract” award: “Quantum Tokens for Digital Signatures,” by Shalev Ben David and Or Sattath:

Abstract: The fisherman caught a quantum fish. “Fisherman, please let me go,” begged the fish, “and I will grant you three wishes.” The fisherman agreed. The fish gave the fisherman a quantum computer, three quantum signing tokens and his classical public key.

The fish explained: “to sign your three wishes, use the tokenized signature scheme on this quantum computer, then show your valid signature to the king, who owes me a favor.”

The fisherman used one of the signing tokens to sign the document “give me a castle!” and rushed to the palace. The king executed the classical verification algorithm using the fish’s public key, and since it was valid, the king complied.

The fisherman’s wife wanted to sign ten wishes using their two remaining signing tokens. The fisherman did not want to cheat, and secretly sailed to meet the fish. “Fish, my wife wants to sign ten more wishes.”

But the fish was not worried: “I have learned quantum cryptography following the previous story (The Fisherman and His Wife by the brothers Grimm). The quantum tokens are consumed during the signing. Your polynomial wife cannot even sign four wishes using the three signing tokens I gave you.”

“How does it work?” wondered the fisherman.

“Have you heard of quantum money? These are quantum states which can be easily verified but are hard to copy. This tokenized quantum signature scheme extends Aaronson and Christiano’s quantum money scheme, which is why the signing tokens cannot be copied.”

“Does your scheme have additional fancy properties?” the fisherman asked.

“Yes, the scheme has other security guarantees: revocability, testability and everlasting security. Furthermore, if you’re at the sea and your quantum phone has only classical reception, you can use this scheme to transfer the value of the quantum money to shore,” said the fish, and swam his way.

Tags: academic papers, quantum cryptography, security tokens, signatures

Posted on October 6, 2016 at 7:03 AM • 11 Comments

Comments

Aleksei Shpakovskii • October 6, 2016 7:46 AM

so the fish could revoke a signing token if she wanted to cheat (or felt cheated)?

Chelloveck • October 6, 2016 9:27 AM

Makes more sense than most article abstracts. And it equates quantum effects with inscrutable magic powers, so it’s factually accurate as well! Looking forward to the next paper in which they describe creation of the quantum tokens via the spinning of straw.

Ted • October 6, 2016 10:59 AM

The application of this research for quantum money is interesting.

EY has an interesting paper ‘Fintech: Are banks responding appropriately?’ that discusses quantum computing as a fintech development being researched for the purpose of adding additional protection for digital assets and payment transactions.

http://www.ey.com/Publication/vwLUAssets/EY-fintech-are-banks-responding-appropriately/$FILE/EY-fintech-are-banks-responding-appropriately.pdf

The updated fairy tale is a wonderful adaptation of the story collected for the children’s book.

Clive Robinson • October 6, 2016 11:09 AM

The paper is long at thirty three pages to the acknowledgments, and page 22 should be enough to scare most non mathmatical mortals 😉

It’s going to need more than a couple of cups of hot brownian motion generation[1] to get through…

[1] See Douglas Adam’s description of the infinite improbability drive in Hitchhikers Gude to the Galaxy to discover the beverage.

Scott • October 6, 2016 12:35 PM

@Chelloveck

creation of the quantum tokens via the spinning of straw

That would have to be the Rumpelstiltoken process. 😀

Unsigned • October 6, 2016 2:44 PM

And now for the most significant bit:

If you thought double spending was frivolous, does this open up a lack of accountability?

“Never saw it before, certainly didn’t sign it.”

Slime Mold with Mustard • October 7, 2016 3:50 AM

Must we assume that our clever fish was caught in a side channel ?

David Leppik • October 7, 2016 10:44 AM

Bonus points for using emoji (a rubber stamp) as a symbol in a formula.

Alex • October 7, 2016 11:50 AM

Well which is it? “Hard to copy” or “Can not be copied”.

Or Sattath • October 9, 2016 5:43 AM

Hi,

I’m one of the authors of that paper (Or Sattath). Thank you Bruce!

I’ll be happy to reply to more of your comments and questions, if you have any.

@Aleksei Shpakovskii Re: “so the fish could revoke a signing token if she wanted to cheat (or felt cheated)?”

Revocation is a bit tricky: it requires the cooperation from the fisherman in this example. After successful revocation, the fish can be sure that no documents will be signed using his public key. In this case, if 3 tokens were provided, and 2 were revoked, then at most one document was or will be signed. This should be compared with the following: suppose you have a secret key, which you’re giving away while you go on vacation to your friend. There is no way for you to know after your return from the vacation how many documents were or will be signed using the secret key by your friend (or, perhaps, by an adversary which hacked to your friend’s system).

@ Alex Re: Well which is it? “Hard to copy” or “Can not be copied”.

Hard to copy – the tokens can certainly be copied by an exponential adversary. Perhaps we should change the abstract if this is confusing – the accurate wording should be “can not be copied by a poly adversary.

itgrrl • October 10, 2016 1:14 AM

@Ted:

“…quantum computing as a fintech development being researched for the purpose of adding additional protection for digital assets and payment transactions…”

Wait, did the authors use a fish analogy as a reference to… FINtech?

(It’s OK folks, I’ll see myself out…)

Schneier on Security

Quantum Tokens for Digital Signatures

Comments

Leave a comment Cancel reply