Quantum Tokens for Digital Signatures

Shalev Ben-David1 and Or Sattath2

1University of Waterloo, David R. Cheriton School of Computer Science
2Ben-Gurion University of the Negev, Computer Science Department

Find this paper interesting or want to discuss? Scite or leave a comment on SciRate.

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 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 away.

► BibTeX data

► References

[1] S. Aaronson. Quantum Copy-Protection and Quantum Money. In Proceedings of the 24th Annual IEEE Conference on Computational Complexity, CCC 2009, Paris, France, 15-18 July 2009, pages 229–242, 2009.
https:/​/​doi.org/​10.1109/​CCC.2009.42

[2] Y. Aharonov, J. Anandan, and L. Vaidman. Meaning of the wave function. Phys. Rev. A, 47:4616–4626, 1993.
https:/​/​doi.org/​10.1103/​PhysRevA.47.4616

[3] S. Aaronson and P. Christiano. Quantum money from hidden subspaces. In Proceedings of the 44th Symposium on Theory of Computing Conference, STOC 2012, New York, NY, USA, May 19 - 22, 2012, pages 41–60, 2012.
https:/​/​doi.org/​10.1145/​2213977.2213983

[4] S. Aaronson and P. Christiano. Quantum Money from Hidden Subspaces. Theory of Computing, 9:349–401, 2013.
https:/​/​doi.org/​10.4086/​toc.2013.v009a009

[5] R. Amos, M. Georgiou, A. Kiayias, and M. Zhandry. One-shot signatures and applications to hybrid quantum/​classical authentication. In K. Makarychev, Y. Makarychev, M. Tulsiani, G. Kamath, and J. Chuzhoy, editors, Proccedings of the Annual ACM SIGACT Symposium on Theory of Computing,, pages 255–268. ACM, 2020, Cryptology ePrint Archive: Report 2020/​107.
https:/​/​doi.org/​10.1145/​3357713.3384304

[6] Y. Aharonov and L. Vaidman. Measurement of the Schrödinger wave of a single particle. Physics Letters A, 178(1):38 – 42, 1993.
https:/​/​doi.org/​10.1016/​0375-9601(93)90724-E

[7] B. Barak. Hopes, fears, and software obfuscation. Commun. ACM, 59(3):88–96, 2016.
https:/​/​doi.org/​10.1145/​2757276

[8] C. H. Bennett, G. Brassard, S. Breidbart, and S. Wiesner. Quantum cryptography, or unforgeable subway tokens. In Advances in Cryptology, pages 267–275. Springer, 1983.
https:/​/​doi.org/​10.1007/​978-1-4757-0602-4_26

[9] N. Bitansky, Z. Brakerski, and Y. T. Kalai. Constructive Post-Quantum Reductions. In Y. Dodis and T. Shrimpton, editors, Advances in Cryptology - CRYPTO 2022 - 42nd Annual International Cryptology Conference, CRYPTO 2022, Santa Barbara, CA, USA, August 15-18, 2022, Proceedings, Part III, volume 13509 of Lecture Notes in Computer Science, pages 654–683. Springer, 2022.
https:/​/​doi.org/​10.1007/​978-3-031-15982-4_22

[10] N. Bitansky, R. Canetti, H. Cohn, S. Goldwasser, Y. T. Kalai, O. Paneth, and A. Rosen. The Impossibility of Obfuscation with Auxiliary Input or a Universal Simulator. In J. A. Garay and R. Gennaro, editors, Advances in Cryptology - CRYPTO 2014 - 34th Annual Cryptology Conference, Santa Barbara, CA, USA, August 17-21, 2014, Proceedings, Part II, volume 8617 of Lecture Notes in Computer Science, pages 71–89. Springer, 2014.
https:/​/​doi.org/​10.1007/​978-3-662-44381-1_5

[11] B. Barak, O. Goldreich, R. Impagliazzo, S. Rudich, A. Sahai, S. P. Vadhan, and K. Yang. On the (im)possibility of obfuscating programs. J. ACM, 59(2):6, 2012.
https:/​/​doi.org/​10.1145/​2160158.2160159

[12] H. Bombin. Clifford gates by code deformation. New Journal of Physics, 13(4):043005, 2011.
https:/​/​doi.org/​10.1088/​1367-2630/​13/​4/​043005
http:/​/​stacks.iop.org/​1367-2630/​13/​i=4/​a=043005

[13] G. Brassard. Searching a Quantum Phone Book. Science, 275(5300):627–628, 1997.
https:/​/​doi.org/​10.1126/​science.275.5300.627

[14] A. Behera, O. Sattath, and U. Shinar. Noise-Tolerant Quantum Tokens for MAC, 2021.
https:/​/​doi.org/​10.48550/​ARXIV.2105.05016

[15] D. Boneh and M. Zhandry. Quantum-Secure Message Authentication Codes. In T. Johansson and P. Q. Nguyen, editors, Advances in Cryptology - EUROCRYPT 2013, 32nd Annual International Conference on the Theory and Applications of Cryptographic Techniques, Athens, Greece, May 26-30, 2013. Proceedings, volume 7881 of Lecture Notes in Computer Science, pages 592–608. Springer, 2013.
https:/​/​doi.org/​10.1007/​978-3-642-38348-9_35

[16] R. Cleve and D. Gottesman. Efficient computations of encodings for quantum error correction. Phys. Rev. A, 56:76–82, Jul 1997.
https:/​/​doi.org/​10.1103/​PhysRevA.56.76

[17] K. Chung, M. Georgiou, C. Lai, and V. Zikas. Cryptography with Disposable Backdoors. Cryptogr., 3(3):22, 2019, Cryptology ePrint Archive: Report 2018/​352.
https:/​/​doi.org/​10.3390/​cryptography3030022

[18] P. Christiano. Personal communication, 2015.

[19] A. Coladangelo, J. Liu, Q. Liu, and M. Zhandry. Hidden Cosets and Applications to Unclonable Cryptography, 2021, arXiv: 2107.05692.
arXiv:2107.05692

[20] S. Chakraborty, J. Radhakrishnan, and N. Raghunathan. Bounds for Error Reduction with Few Quantum Queries. In Approximation, Randomization and Combinatorial Optimization, Algorithms and Techniques, 8th International Workshop on Approximation Algorithms for Combinatorial Optimization Problems, APPROX 2005 and RANDOM 2005, Berkeley, CA, USA, August 22-24, 2005, Proceedings, pages 245–256, 2005.
https:/​/​doi.org/​10.1007/​11538462_21

[21] R. Canetti, G. N. Rothblum, and M. Varia. Obfuscation of Hyperplane Membership. In D. Micciancio, editor, Theory of Cryptography, 7th Theory of Cryptography Conference, TCC 2010, Zurich, Switzerland, February 9-11, 2010. Proceedings, volume 5978 of Lecture Notes in Computer Science, pages 72–89. Springer, 2010.
https:/​/​doi.org/​10.1007/​978-3-642-11799-2_5

[22] W. Diffie and M. E. Hellman. New directions in cryptography. IEEE Trans. Information Theory, 22(6):644–654, 1976.
https:/​/​doi.org/​10.1109/​TIT.1976.1055638

[23] Y. Z. Ding and M. O. Rabin. Hyper-Encryption and Everlasting Security. In H. Alt and A. Ferreira, editors, STACS 2002, 19th Annual Symposium on Theoretical Aspects of Computer Science, Antibes - Juan les Pins, France, March 14-16, 2002, Proceedings, volume 2285 of Lecture Notes in Computer Science, pages 1–26. Springer, 2002.
https:/​/​doi.org/​10.1007/​3-540-45841-7_1

[24] E. Farhi, D. Gosset, A. Hassidim, A. Lutomirski, D. Nagaj, and P. Shor. Quantum State Restoration and Single-Copy Tomography for Ground States of Hamiltonians. Phys. Rev. Lett., 105:190503, Nov 2010.
https:/​/​doi.org/​10.1103/​PhysRevLett.105.190503

[25] E. Farhi, D. Gosset, A. Hassidim, A. Lutomirski, and P. Shor. Quantum money from knots. In Proceedings of the 3rd Innovations in Theoretical Computer Science Conference, pages 276–289. ACM, 2012.
https:/​/​doi.org/​10.1145/​2090236.2090260

[26] D. Gavinsky. Quantum money with classical verification. In IEEE 27th Annual Conference on Computational Complexity, pages 42–52. IEEE, 2012.
https:/​/​doi.org/​10.1109/​CCC.2012.10

[27] S. Goldwasser and Y. T. Kalai. On the Impossibility of Obfuscation with Auxiliary Input. In 46th Annual IEEE Symposium on Foundations of Computer Science (FOCS 2005), 23-25 October 2005, Pittsburgh, PA, USA, Proceedings, pages 553–562, 2005.
https:/​/​doi.org/​10.1109/​SFCS.2005.60

[28] M. Georgiou and I. Kerenidis. New Constructions for Quantum Money. In S. Beigi and R. König, editors, 10th Conference on the Theory of Quantum Computation, Communication and Cryptography, TQC 2015, May 20-22, 2015, Brussels, Belgium, volume 44 of LIPIcs, pages 92–110. Schloss Dagstuhl - Leibniz-Zentrum fuer Informatik, 2015.
https:/​/​doi.org/​10.4230/​LIPIcs.TQC.2015.92

[29] O. Goldreich. The Foundations of Cryptography - Vol. 2, Basic Applications. Cambridge University Press, 2004.

[30] M. Grassl, M. Rötteler, and T. Beth. Efficient Quantum Circuits For Non-Qubit Quantum Error-Correcting Codes. Int. J. Found. Comput. Sci., 14(5):757–776, 2003.
https:/​/​doi.org/​10.1142/​S0129054103002011

[31] J. Katz and Y. Lindell. Introduction to Modern Cryptography, Second Edition. CRC Press, 2014.

[32] N. A. Lynch. Distributed Algorithms. Morgan Kaufmann, 1996.

[33] M. Mosca and D. Stebila. Quantum coins, volume 523 of Contemp. Math., pages 35–47. Amer. Math. Soc., 2010.

[34] M. C. Pena, R. D. Díaz, J. Faugère, L. H. Encinas, and L. Perret. Non-quantum Cryptanalysis of the Noisy Version of Aaronson-Christiano's Quantum Money Scheme. IET Information Security, 13(4):362–366, 2019.
https:/​/​doi.org/​10.1049/​iet-ifs.2018.5307

[35] M. C. Pena, J. Faugère, and L. Perret. Algebraic Cryptanalysis of a Quantum Money Scheme The Noise-Free Case. In J. Katz, editor, Public-Key Cryptography - PKC 2015 - 18th IACR International Conference on Practice and Theory in Public-Key Cryptography, Gaithersburg, MD, USA, March 30 - April 1, 2015, Proceedings, volume 9020 of Lecture Notes in Computer Science, pages 194–213. Springer, 2015.
https:/​/​doi.org/​10.1007/​978-3-662-46447-2_9

[36] A. Prasad. Counting subspaces of a finite vector space — 1. Resonance, 15(11):977–987, 2010.
https:/​/​doi.org/​10.1007/​s12045-010-0114-5

[37] F. Pastawski, N. Y. Yao, L. Jiang, M. D. Lukin, and J. I. Cirac. Unforgeable noise-tolerant quantum tokens. Proceedings of the National Academy of Sciences, 109(40):16079–16082, 2012.
https:/​/​doi.org/​10.1073/​pnas.1203552109

[38] R. Radian and O. Sattath. Semi-Quantum Money. In Proceedings of the 1st ACM Conference on Advances in Financial Technologies, AFT 2019, Zurich, Switzerland, October 21-23, 2019, pages 132–146. ACM, 2019, arXiv: 1908.08889.
https:/​/​doi.org/​10.1145/​3318041.3355462
arXiv:1908.08889

[39] R. Radian and O. Sattath. Semi-quantum Money. Journal of Cryptology, 35(2), January 2022, arXiv: 1908.08889.
https:/​/​doi.org/​10.1007/​s00145-021-09418-8
arXiv:1908.08889

[40] O. Sattath. Quantum Prudent Contracts with Applications to Bitcoin, 2022.
https:/​/​doi.org/​10.48550/​ARXIV.2204.12806

[41] O. Sattath. Uncloneable Cryptography, 2022.
https:/​/​doi.org/​10.48550/​ARXIV.2210.14265

[42] O. Shmueli. Public-key Quantum money with a classical bank. In S. Leonardi and A. Gupta, editors, STOC '22: 54th Annual ACM SIGACT Symposium on Theory of Computing, Rome, Italy, June 20 - 24, 2022, pages 790–803. ACM, 2022.
https:/​/​doi.org/​10.1145/​3519935.3519952

[43] O. Shmueli. Semi-quantum Tokenized Signatures. In Y. Dodis and T. Shrimpton, editors, Advances in Cryptology - CRYPTO 2022 - 42nd Annual International Cryptology Conference, CRYPTO 2022, Santa Barbara, CA, USA, August 15-18, 2022, Proceedings, Part I, volume 13507 of Lecture Notes in Computer Science, pages 296–319. Springer, 2022.
https:/​/​doi.org/​10.1007/​978-3-031-15802-5_11

[44] T. Tulsi, L. K. Grover, and A. Patel. A new algorithm for fixed point quantum search. Quantum Information & Computation, 6(6):483–494, 2006.
http:/​/​portal.acm.org/​citation.cfm?id=2011693

[45] Y. Tokunaga, T. Okamoto, and N. Imoto. Anonymous quantum cash. In ERATO Conference on Quantum Information Science, 2003.

[46] D. Unruh. Revocable Quantum Timed-Release Encryption. J. ACM, 62(6):49:1–49:76, 2015.
https:/​/​doi.org/​10.1145/​2817206

[47] D. Unruh. Everlasting Multi-party Computation. J. Cryptol., 31(4):965–1011, 2018.
https:/​/​doi.org/​10.1007/​s00145-018-9278-z

[48] S. Wiesner. Conjugate coding. ACM Sigact News, 15(1):78–88, 1983.
https:/​/​doi.org/​10.1145/​1008908.1008920

[49] W. K. Wootters and W. H. Zurek. A single quantum cannot be cloned. Nature, 299(5886):802–803, 1982.

[50] M. Zhong, M. P. Hedges, R. L. Ahlefeldt, J. G. Bartholomew, S. E. Beavan, S. M. Wittig, J. J. Longdell, and M. J. Sellars. Optically addressable nuclear spins in a solid with a six-hour coherence time. Nature, 517(7533):177–180, jan 2015.
https:/​/​doi.org/​10.1038/​nature14025

[51] M. Zhandry. Quantum Lightning Never Strikes the Same State Twice, 2017, arXiv: 1711.02276.
arXiv:1711.02276

[52] M. Zhandry. Quantum Lightning Never Strikes the Same State Twice. Or: Quantum Money from Cryptographic Assumptions. J. Cryptol., 34(1):6, 2021, arXiv: 1711.02276.
https:/​/​doi.org/​10.1007/​s00145-020-09372-x
arXiv:1711.02276

Cited by

[1] S. Pirandola, U. L. Andersen, L. Banchi, M. Berta, D. Bunandar, R. Colbeck, D. Englund, T. Gehring, C. Lupo, C. Ottaviani, J. L. Pereira, M. Razavi, J. Shamsul Shaari, M. Tomamichel, V. C. Usenko, G. Vallone, P. Villoresi, and P. Wallden, "Advances in quantum cryptography", Advances in Optics and Photonics 12 4, 1012 (2020).

[2] Douglas Scott, "Science Spoofs, Physics Pranks and Astronomical Antics", arXiv:2103.17057, (2021).

[3] Thomas Vidick and Tina Zhang, "Classical proofs of quantum knowledge", arXiv:2005.01691, (2020).

[4] Or Sattath, "Quantum Prudent Contracts with Applications to Bitcoin", arXiv:2204.12806, (2022).

[5] Scott Aaronson, Jiahui Liu, Qipeng Liu, Mark Zhandry, and Ruizhe Zhang, "New Approaches for Quantum Copy-Protection", arXiv:2004.09674, (2020).

[6] Roy Radian and Or Sattath, "Semi-Quantum Money", arXiv:1908.08889, (2019).

[7] Andrea Coladangelo, Shafi Goldwasser, and Umesh Vazirani, "Deniable Encryption in a Quantum World", arXiv:2112.14988, (2021).

[8] Prabhanjan Ananth and Rolando L. La Placa, "Secure Software Leasing", arXiv:2005.05289, (2020).

[9] Andrea Coladangelo and Or Sattath, "A Quantum Money Solution to the Blockchain Scalability Problem", Quantum 4, 297 (2020).

[10] Andrea Coladangelo, Jiahui Liu, Qipeng Liu, and Mark Zhandry, "Hidden Cosets and Applications to Unclonable Cryptography", arXiv:2107.05692, (2021).

[11] Or Sattath and Shai Wyborski, "Uncloneable Decryptors from Quantum Copy-Protection", arXiv:2203.05866, (2022).

[12] Jiahui Liu, Hart Montgomery, and Mark Zhandry, "Another Round of Breaking and Making Quantum Money: How to Not Build It from Lattices, and More", arXiv:2211.11994, (2022).

[13] Or Sattath, "Uncloneable Cryptography", arXiv:2210.14265, (2022).

[14] Amit Behera and Or Sattath, "Almost Public Quantum Coins", arXiv:2002.12438, (2020).

[15] Nir Bitansky, Zvika Brakerski, and Yael Tauman Kalai, "Constructive Post-Quantum Reductions", arXiv:2203.02314, (2022).

[16] Anne Broadbent, Sevag Gharibian, and Hong-Sheng Zhou, "Towards Quantum One-Time Memories from Stateless Hardware", arXiv:1810.05226, (2018).

[17] Niraj Kumar, "Practically feasible robust quantum money with classical verification", arXiv:1908.04114, (2019).

[18] Anne Broadbent, Sevag Gharibian, and Hong-Sheng Zhou, "Towards Quantum One-Time Memories from Stateless Hardware", Quantum 5, 429 (2021).

[19] Or Sattath and Uriel Shinar, "Quantum Amnesia Leaves Cryptographic Mementos: A Note On Quantum Skepticism", arXiv:2212.08750, (2022).

[20] Prabhanjan Ananth, Zihan Hu, and Henry Yuen, "On the (Im)plausibility of Public-Key Quantum Money from Collision-Resistant Hash Functions", arXiv:2301.09236, (2023).

The above citations are from SAO/NASA ADS (last updated successfully 2023-02-07 03:33:24). The list may be incomplete as not all publishers provide suitable and complete citation data.

On Crossref's cited-by service no data on citing works was found (last attempt 2023-02-07 03:33:22).