[go: up one dir, main page]
More Web Proxy on the site http://driver.im/
Skip to main content
Springer Nature Link
Log in

On the (Im)plausibility of Public-Key Quantum Money from Collision-Resistant Hash Functions

  • Conference paper
  • First Online:
Advances in Cryptology – ASIACRYPT 2023 (ASIACRYPT 2023)

Part of the book series: Lecture Notes in Computer Science ((LNCS,volume 14445))

  • 386 Accesses

Abstract

Public-key quantum money is a cryptographic proposal for using highly entangled quantum states as currency that is publicly verifiable yet resistant to counterfeiting due to the laws of physics. Despite significant interest, constructing provably-secure public-key quantum money schemes based on standard cryptographic assumptions has remained an elusive goal. Even proposing plausibly-secure candidate schemes has been a challenge.

These difficulties call for a deeper and systematic study of the structure of public-key quantum money schemes and the assumptions they can be based on. Motivated by this, we present the first black-box separation of quantum money and cryptographic primitives. Specifically, we show that collision-resistant hash functions cannot be used as a black-box to construct public-key quantum money schemes where the banknote verification makes classical queries to the hash function. Our result involves a novel combination of state synthesis techniques from quantum complexity theory and simulation techniques, including Zhandry’s compressed oracle technique.

This is a preview of subscription content, log in via an institution to check access.

Access this chapter

Log in via an institution

Subscribe and save

Springer+ Basic
£29.99 /Month
  • Get 10 units per month
  • Download Article/Chapter or eBook
  • 1 Unit = 1 Article or 1 Chapter
  • Cancel anytime
Subscribe now

Buy Now

Chapter
GBP 19.95
Price includes VAT (United Kingdom)
  • Available as PDF
  • Read on any device
  • Instant download
  • Own it forever
eBook
GBP 47.99
Price includes VAT (United Kingdom)
  • Available as EPUB and PDF
  • Read on any device
  • Instant download
  • Own it forever
Softcover Book
GBP 59.99
Price includes VAT (United Kingdom)
  • Compact, lightweight edition
  • Dispatched in 3 to 5 business days
  • Free shipping worldwide - see info

Tax calculation will be finalised at checkout

Purchases are for personal use only

Institutional subscriptions

Similar content being viewed by others

Notes

  1. 1.

    A recent work by [MLZ22] presents a nice framework capturing many of the candidate constructions of public-key quantum money.

  2. 2.

    Technically, we show a weaker statement which holds for almost every \((\textsf{pk},s)\).

  3. 3.

    Technically, we require that the reduced density matrix of \(\rho _{\textsf{pk},s}\) is accepted by \(\textsf{Ver}\).

  4. 4.

    The fact that we don’t have the description of \({\mathcal {R}}\) is the problem here.

  5. 5.

    Actually we use the residual state after running verification polynomially many times on the valid banknote.

References

  1. Aaronson, S., Ambainis, A.: The need for structure in quantum speedups. arXiv preprint arXiv:0911.0996 (2009)

  2. Aaronson, S.: Quantum copy-protection and quantum money. In: 24th Annual IEEE Conference on Computational Complexity, pp. 229-242. IEEE Computer Society, Los Alamitos, CA (2009). https://doi.org/10.1109/CCC.2009.42

  3. Aaronson, S., Christiano, P.: Quantum money from hidden subspaces. Theory Comput. 9, 349–401 (2013). https://doi.org/10.4086/toc.2013.v009a009

  4. Austrin, P., Chung, H., Chung, K.-M., Fu, S., Lin, Y.-T., Mahmoody, M.: On the impossibility of key agreements from quantum random oracles. Cryptology ePrint Archive (2022)

    Google Scholar 

  5. Ananth, P., Hu, Z., Yuen, H.: On the (im)plausibility of public-key quantum money from collision-resistant hash functions. Cryptology ePrint Archive, Paper 2023/069. https://eprint.iacr.org/2023/0692023. URL: https://eprint.iacr.org/2023/069 (cit. on pp. 17, 27-29)

  6. Ananth, P., Jain, A., Lin, H., Matt, C., Sahai, A.: Indistinguishability obfuscation without multilinear maps: new paradigms via low degree weak pseudorandomness and security amplification. In: Boldyreva, A., Micciancio, D. (eds.) CRYPTO 2019. LNCS, vol. 11694, pp. 284–332. Springer, Cham (2019). https://doi.org/10.1007/978-3-030-26954-8_10

    Chapter  Google Scholar 

  7. Ananth,. P., Kaleoglu, F.: A note on copy-protection from random oracles. Cryptology ePrint Archive, Paper 2022/1109. https://eprint.iacr.org/2022/1109 (2022). https://eprint.iacr.org/2022/1109

  8. Ananth, P., Kaleoglu, F., Li, X., Liu, Q., Zhandry, M.: On the feasibility of unclonable encryption, and more. In: Dodis, Y., Shrimpton, T. (eds.) CRYPTO 2022. LNCS, vol. 13508, pp. 212–241. Springer, Cham (2022). https://doi.org/10.1007/978-3-031-15979-4_8

    Chapter  Google Scholar 

  9. Ananth, P., La Placa, R.L.: Secure software leasing. In: Canteaut, A., Standaert, F.-X. (eds.) EUROCRYPT 2021. LNCS, vol. 12697, pp. 501–530. Springer, Cham (2021). https://doi.org/10.1007/978-3-030-77886-6_17

    Chapter  Google Scholar 

  10. Bilyk, A., Doliskani, J., Gong, Z.: Cryptanalysis of three quantum money schemes. arXiv preprint arXiv:2205.10488 (2022)

  11. Brakerski, Z., Döttling, N., Garg, S., Malavolta, G.: Factoring and pairings are not necessary for iO: circularsecure LWE suffices. Cryptology ePrint Archive (2020)

    Google Scholar 

  12. Bitansky, N., Degwekar, A., Vaikuntanathan, V.: Structure vs. hardness through the obfuscation lens. In: Katz, J., Shacham, H. (eds.) CRYPTO 2017. LNCS, vol. 10401, pp. 696–723. Springer, Cham (2017). https://doi.org/10.1007/978-3-319-63688-7_23

    Chapter  Google Scholar 

  13. Barak, B., et al.: On the (im)possibility of obfuscating programs. In: Kilian, J. (ed.) CRYPTO 2001. LNCS, vol. 2139, pp. 1–18. Springer, Heidelberg (2001). https://doi.org/10.1007/3-540-44647-8_1

    Chapter  Google Scholar 

  14. Broadbent, A., Gutoski, G., Stebila, D.: Quantum one-time programs. In: Canetti, R., Garay, J.A. (eds.) CRYPTO 2013. LNCS, vol. 8043, pp. 344–360. Springer, Heidelberg (2013). https://doi.org/10.1007/978-3-642-40084-1_20

    Chapter  Google Scholar 

  15. Broadbent, A., Islam, R.: Quantum encryption with certified deletion. In: Pass, R., Pietrzak, K. (eds.) TCC 2020. LNCS, vol. 12552, pp. 92–122. Springer, Cham (2020). https://doi.org/10.1007/978-3-030-64381-2_4

    Chapter  Google Scholar 

  16. Broadbent, A., Lord, S.: Uncloneable quantum encryption via oracles. In: Flammia, S.T. (ed.) 15th Conference on the Theory of Quantum Computation, Communication and Cryptography (TQC 2020), vol. 158. Leibniz International Proceedings in Informatics (LIPIcs), pp. 4:1-4:22. Schloss Dagstuhl-Leibniz-Zentrum für Informatik, Dagstuhl, Germany (2020). https://doi.org/10.4230/LIPIcs.TQC.2020.4

  17. Barak, B., Mahmoody-Ghidary, M.: Merkle puzzles are optimal — an O(n2)-query attack on any key exchange from a random oracle. In: Halevi, S. (ed.) CRYPTO 2009. LNCS, vol. 5677, pp. 374–390. Springer, Heidelberg (2009). https://doi.org/10.1007/978-3-642-03356-8_22

    Chapter  Google Scholar 

  18. Boneh, D., Papakonstantinou, P., Rackoff, C., Vahlis, Y., Waters, B.: On the impossibility of basing identity based encryption on trapdoor permutations. In: 2008 49th Annual IEEE Symposium on Foundations of Computer Science, pp. 283–292. IEEE (2008)

    Google Scholar 

  19. Ben-David, S., Sattath, O.: Quantum tokens for digital signatures. arXiv preprint arXiv:1609.09047 (2016)

  20. Canetti, R., Kalai, Y.T., Paneth, O.: On obfuscation with random oracles. In: Dodis, Y., Nielsen, J.B. (eds.) TCC 2015. LNCS, vol. 9015, pp. 456–467. Springer, Heidelberg (2015). https://doi.org/10.1007/978-3-662-46497-7_18

    Chapter  Google Scholar 

  21. Coladangelo, A., Liu, J., Liu, Q., Zhandry, M.: Hidden cosets and applications to unclonable cryptography. In: Malkin, T., Peikert, C. (eds.) CRYPTO 2021. LNCS, vol. 12825, pp. 556–584. Springer, Cham (2021). https://doi.org/10.1007/978-3-030-84242-0_20

    Chapter  Google Scholar 

  22. Coladangelo, A., Majenz, C., Poremba, A.: Quantum copy-protection of compute-and-compare programs in the quantum random oracle model. arXiv preprint arXiv:2009.13865 (2020)

  23. Cao, S., Xue, R.: Being a permutation is also orthogonal to one-wayness in quantum world: impossibilities of quantum one-way permutations from one-wayness primitives. In: Theoretical Computer Science, vol. 855, pp. 16–42 (2021)

    Google Scholar 

  24. Döttling, N., Garg, S.: Identity-based encryption from the Diffie-Hellman assumption. In: Katz, J., Shacham, H. (eds.) CRYPTO 2017. LNCS, vol. 10401, pp. 537–569. Springer, Cham (2017). https://doi.org/10.1007/978-3-319-63688-7_18

    Chapter  Google Scholar 

  25. Dieks, D.G.B.J.: Communication by EPR devices. Phys. Lett. A 92(6), 271–272 (1982)

    Google Scholar 

  26. Dachman-Soled, D., Lindell, Y., Mahmoody, M., Malkin, T.: On the black-box complexity of optimally-fair coin tossing. In: Ishai, Y. (ed.) TCC 2011. LNCS, vol. 6597, pp. 450–467. Springer, Heidelberg (2011). https://doi.org/10.1007/978-3-642-19571-6_27

    Chapter  Google Scholar 

  27. Devadas, L., Quach, W., Vaikuntanathan, V., Wee, H., Wichs, D.: Succinct LWE sampling, random polynomials, and obfuscation. In: Nissim, K., Waters, B. (eds.) TCC 2021. LNCS, vol. 13043, pp. 256–287. Springer, Cham (2021). https://doi.org/10.1007/978-3-030-90453-1_9

    Chapter  Google Scholar 

  28. Farhi, E., Gosset, D., Hassidim, A., Lutomirski, A., Shor, P.: Quantum money from knots. In: Proceedings of the 3rd Innovations in Theoretical Computer Science Conference, pp. 276–289 (2012)

    Google Scholar 

  29. Goyal, V., Kumar, V., Lokam, S., Mahmoody, M.: On black-box reductions between predicate encryption schemes. In: Cramer, R. (ed.) TCC 2012. LNCS, vol. 7194, pp. 440–457. Springer, Heidelberg (2012). https://doi.org/10.1007/978-3-642-28914-9_25

    Chapter  Google Scholar 

  30. Gertner, Y., Kannan, S., Malkin, T., Reingold, O., Viswanathan, M.: The relationship between public key encryption and oblivious transfer. In: Proceedings 41st Annual Symposium on Foundations of Computer Science, pp. 325–335. IEEE (2000)

    Google Scholar 

  31. Gay, R., Pass, R.: Indistinguishability obfuscation from circular security. In: Proceedings of the 53rd Annual ACM SIGACT Symposium on Theory of Computing, pp. 736–749 (2021)

    Google Scholar 

  32. Georgiou, M., Zhandry, M.: Unclonable decryption keys. Cryptology ePrint Archive (2020)

    Google Scholar 

  33. Hopkins, S., Jain, A., Lin, H.: Counterexamples to new circular security assumptions underlying iO. In: Malkin, T., Peikert, C. (eds.) CRYPTO 2021. LNCS, vol. 12826, pp. 673–700. Springer, Cham (2021). https://doi.org/10.1007/978-3-030-84245-1_23

    Chapter  Google Scholar 

  34. Hosoyamada, A., Yamakawa, T.: Finding collisions in a quantum world: quantum black-box separation of collision-resistance and one-wayness. In: Moriai, S., Wang, H. (eds.) ASIACRYPT 2020. LNCS, vol. 12491, pp. 3–32. Springer, Cham (2020). https://doi.org/10.1007/978-3-030-64837-4_1

    Chapter  Google Scholar 

  35. Impagliazzo, R.: A personal view of average-case complexity. In: Proceedings of Structure in Complexity Theory. Tenth Annual IEEE Conference, pp. 134–147. IEEE (1995)

    Google Scholar 

  36. Impagliazzo, R., Rudich, S.: Limits on the provable consequences of one-way permutations. In: Goldwasser, S. (ed.) CRYPTO 1988. LNCS, vol. 403, pp. 8–26. Springer, New York (1990). https://doi.org/10.1007/0-387-34799-2_2

    Chapter  Google Scholar 

  37. Ji, Z., Liu, Y.-K., Song, F.: Pseudorandom quantum states. In: Shacham, H., Boldyreva, A. (eds.) CRYPTO 2018. LNCS, vol. 10993, pp. 126–152. Springer, Cham (2018). https://doi.org/10.1007/978-3-319-96878-0_5

    Chapter  Google Scholar 

  38. Jain, A., Lin, H., Sahai, A.: Indistinguishability obfuscation from well-founded assumptions. In: Proceedings of the 53rd Annual ACM SIGACT Symposium on Theory of Computing, pp. 60–73 (2021)

    Google Scholar 

  39. Jain, A., Lin, H., Sahai, A.: Indistinguishability obfuscation from LPN over, DLIN, and PRGs in NC. In: Dunkelman, O., Dziembowski, S. (eds.) EUROCRYPT 2022. LNCS, vol. 13275, pp. 670–699. Springer, Cham (2022). https://doi.org/10.1007/978-3-031-06944-4_23

    Chapter  Google Scholar 

  40. Kane, D.M., Sharif, S., Silverberg, A.: Quantum money from quaternion algebras. arXiv preprint arXiv:2109.12643 (2021)

  41. Lutomirski, A.: An online attack against Wiesner’s quantum money. arXiv preprint arXiv:1010.0256 (2010)

  42. Montgomery, H., Liu, J., Zhandry, M.: Another round of breaking and making quantum money: how to not build it from lattices, and more. arXiv preprint arXiv:2211.11994 (2022)

  43. Molina, A., Vidick, T., Watrous, J.: Optimal counterfeiting attacks and generalizations for Wiesner’s quantum money. In: Iwama, K., Kawano, Y., Murao, M. (eds.) TQC 2012. LNCS, vol. 7582, pp. 45–64. Springer, Heidelberg (2013). https://doi.org/10.1007/978-3-642-35656-8_4

    Chapter  Google Scholar 

  44. Marriott, C., Watrous, J.: Quantum Arthur-Merlin games. Comput. Complex. 14(2), 122–152 (2005)

    Google Scholar 

  45. Nielsen, M.A., Chuang, I.L.: Quantum Computation and Quantum Information. Cambridge University Press, Cambridge (2010)

    Google Scholar 

  46. Papadimitriou, C.H.: Computational Complexity. Addison- Wesley, Boston (1994)

    Google Scholar 

  47. Papakonstantinou, P.A., Rackoff, C.W., Vahlis, Y.: How powerful are the DDH hard groups? Cryptology ePrint Archive (2012)

    Google Scholar 

  48. Roberts, B.: Security analysis of quantum lightning. In: Canteaut, A., Standaert, F.-X. (eds.) EUROCRYPT 2021. LNCS, vol. 12697, pp. 562–567. Springer, Cham (2021). https://doi.org/10.1007/978-3-030-77886-6_19

    Chapter  Google Scholar 

  49. Radian, R., Sattath, O.: Semi-quantum money. J. Cryptol. 35(2), 1–70 (2022)

    Google Scholar 

  50. Reingold, O., Trevisan, L., Vadhan, S.: Notions of reducibility between cryptographic primitives. In: Naor, M. (ed.) TCC 2004. LNCS, vol. 2951, pp. 1–20. Springer, Heidelberg (2004). https://doi.org/10.1007/978-3-540-24638-1_1

    Chapter  Google Scholar 

  51. Rudich, S.: The use of interaction in public cryptosystems. In: Feigenbaum, J. (ed.) CRYPTO 1991. LNCS, vol. 576, pp. 242–251. Springer, Heidelberg (1992). https://doi.org/10.1007/3-540-46766-1_19

    Chapter  Google Scholar 

  52. Rosenthal, G., Yuen, H.: Interactive proofs for synthesizing quantum states and unitaries. arXiv preprint arXiv:2108.07192 (2021)

  53. Shmueli, O.: Public-key Quantum money with a classical bank. In: Proceedings of the 54th Annual ACM SIGACT Symposium on Theory of Computing, pp. 790–803 (2022)

    Google Scholar 

  54. Shmueli, O.: Semi-quantum tokenized signatures. Cryptology ePrint Archive (2022)

    Google Scholar 

  55. Simon, D.R.: Finding collisions on a one-way street: can secure hash functions be based on general assumptions? In: Nyberg, K. (ed.) EUROCRYPT 1998. LNCS, vol. 1403, pp. 334–345. Springer, Heidelberg (1998). https://doi.org/10.1007/BFb0054137

    Chapter  Google Scholar 

  56. Unruh, D.: Computationally binding quantum commitments. In: Fischlin, M., Coron, J.-S. (eds.) EUROCRYPT 2016. LNCS, vol. 9666, pp. 497–527. Springer, Heidelberg (2016). https://doi.org/10.1007/978-3-662-49896-5_18

    Chapter  Google Scholar 

  57. Wiesner, S.: Conjugate coding. In: ACM SIGACT News 15(1), 78–88 (1983)

    Google Scholar 

  58. Winter, A.: Coding theorem and strong converse for quantum channels. IEEE Trans. Inf. Theory 45(7), 2481–2485 (1999)

    Google Scholar 

  59. Wee, H., Wichs, D.: Candidate obfuscation via oblivious LWE sampling. In: Canteaut, A., Standaert, F.-X. (eds.) EUROCRYPT 2021. LNCS, vol. 12698, pp. 127–156. Springer, Cham (2021). https://doi.org/10.1007/978-3-030-77883-5_5

    Chapter  Google Scholar 

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

    Google Scholar 

  61. Zhandry, M.: A note on the quantum collision and set equality problems. Quantum Inf. Comput. 15(7–8), 557–567 (2015)

    Google Scholar 

  62. Zhandry, M.: How to record quantum queries, and applications to quantum indifferentiability. Cryptology ePrint Archive, Paper 2018/276. https://eprint.iacr.org/2018/276 (2018)

  63. Zhandry, M.: Quantum lightning never strikes the same state twice. Or: quantum money from cryptographic assumptions. J. Cryptol. 34(1), Paper No. 6, 56 (2021). issn 0933-2790. https://doi.org/10.1007/s00145-020-09372-x

Download references

Author information

Authors and Affiliations

  1. UCSB, Santa Barbara, USA

    Prabhanjan Ananth

  2. Tsinghua University, Beijing, China

    Zihan Hu

  3. Columbia University, New York, USA

    Henry Yuen

Authors
  1. Prabhanjan Ananth
    View author publications

    You can also search for this author in PubMed Google Scholar

  2. Zihan Hu
    View author publications

    You can also search for this author in PubMed Google Scholar

  3. Henry Yuen
    View author publications

    You can also search for this author in PubMed Google Scholar

Corresponding author

Correspondence to Zihan Hu .

Editor information

Editors and Affiliations

  1. Nanyang Technological University, Singapore, Singapore

    Jian Guo

  2. Monash University, Melbourne, VIC, Australia

    Ron Steinfeld

Rights and permissions

Reprints and permissions

Copyright information

© 2023 International Association for Cryptologic Research

About this paper

Check for updates. Verify currency and authenticity via CrossMark

Cite this paper

Ananth, P., Hu, Z., Yuen, H. (2023). On the (Im)plausibility of Public-Key Quantum Money from Collision-Resistant Hash Functions. In: Guo, J., Steinfeld, R. (eds) Advances in Cryptology – ASIACRYPT 2023. ASIACRYPT 2023. Lecture Notes in Computer Science, vol 14445. Springer, Singapore. https://doi.org/10.1007/978-981-99-8742-9_2

Download citation

  • DOI: https://doi.org/10.1007/978-981-99-8742-9_2

  • Published:

  • Publisher Name: Springer, Singapore

  • Print ISBN: 978-981-99-8741-2

  • Online ISBN: 978-981-99-8742-9

  • eBook Packages: Computer ScienceComputer Science (R0)

Publish with us

Policies and ethics

Search

Navigation