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.
 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.
 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.
 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.
 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.
 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.
 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.
 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.
 H. Bombin. Clifford gates by code deformation. New Journal of Physics, 13(4):043005, 2011.
 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.
 K. Chung, M. Georgiou, C. Lai, and V. Zikas. Cryptography with Disposable Backdoors. Cryptogr., 3(3):22, 2019, Cryptology ePrint Archive: Report 2018/352.
 P. Christiano. Personal communication, 2015.
 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.
 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.
 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.
 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.
 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.
 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.
 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.
 O. Goldreich. The Foundations of Cryptography - Vol. 2, Basic Applications. Cambridge University Press, 2004.
 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.
 J. Katz and Y. Lindell. Introduction to Modern Cryptography, Second Edition. CRC Press, 2014.
 N. A. Lynch. Distributed Algorithms. Morgan Kaufmann, 1996.
 M. Mosca and D. Stebila. Quantum coins, volume 523 of Contemp. Math., pages 35–47. Amer. Math. Soc., 2010.
 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.
 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.
 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.
 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.
 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.
 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.
 Y. Tokunaga, T. Okamoto, and N. Imoto. Anonymous quantum cash. In ERATO Conference on Quantum Information Science, 2003.
 W. K. Wootters and W. H. Zurek. A single quantum cannot be cloned. Nature, 299(5886):802–803, 1982.
 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.
 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.
 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).
 Andrea Coladangelo and Or Sattath, "A Quantum Money Solution to the Blockchain Scalability Problem", Quantum 4, 297 (2020).
 Anne Broadbent, Sevag Gharibian, and Hong-Sheng Zhou, "Towards Quantum One-Time Memories from Stateless Hardware", Quantum 5, 429 (2021).
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).
This Paper is published in Quantum under the Creative Commons Attribution 4.0 International (CC BY 4.0) license. Copyright remains with the original copyright holders such as the authors or their institutions.