SpringerLink
Log in

Tight Bounds for Simon’s Algorithm

  • Conference paper
  • First Online:
Progress in Cryptology – LATINCRYPT 2021 (LATINCRYPT 2021)

Part of the book series: Lecture Notes in Computer Science ((LNSC,volume 12912))

Abstract

Simon’s algorithm is the first example of a quantum algorithm exponentially faster than any classical algorithm, and has many applications in cryptanalysis. While these quantum attacks are often extremely efficient, they are generally missing some precise cost estimate. This article aims at resolving this issue by computing precise query costs for the different use cases of Simon’s algorithm in cryptanalysis.

We show that it requires little more than n queries to succeed in most cases. We perform the first concrete cost analysis for the offline Simon’s algorithm, and show that it require little more than \(n+k\) queries. We also find that for parameter sizes of cryptographic relevance, it is possible to truncate the output of the periodic function to a dozen of bits without any impact on the number of queries, which can save roughly a factor 3 in qubits in reversible implementations of Simon’s algorithm.

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
EUR 32.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
USD 29.95
Price excludes VAT (USA)
  • Available as PDF
  • Read on any device
  • Instant download
  • Own it forever
eBook
USD 69.99
Price excludes VAT (USA)
  • Available as EPUB and PDF
  • Read on any device
  • Instant download
  • Own it forever
Softcover Book
USD 89.99
Price excludes VAT (USA)
  • Compact, lightweight edition
  • Dispatched in 3 to 5 business days
  • Free ship** 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.

    In [22], the algorithm they introduce is in fact a special case of what we call here Grover-meets-Simon with a perfect external test.

References

  1. Bonnetain, X.: Quantum key-recovery on full AEZ. In: Adams, C., Camenisch, J. (eds.) SAC 2017. LNCS, vol. 10719, pp. 394–406. Springer, Cham (2018). https://doi.org/10.1007/978-3-319-72565-9_20

    Chapter  Google Scholar 

  2. Bonnetain, X.: Collisions on Feistel-MiMC and univariate GMiMC. Cryptology ePrint Archive, Report 2019/951 (2019). https://eprint.iacr.org/2019/951

  3. Bonnetain, X.: Tight bounds for Simon’s algorithm. IACR Cryptol. ePrint Arch. 2020, 919 (2020). https://eprint.iacr.org/2020/919

  4. Bonnetain, X., Hosoyamada, A., Naya-Plasencia, M., Sasaki, Y., Schrottenloher, A.: Quantum attacks without superposition queries: the offline Simon’s algorithm. In: Galbraith, S.D., Moriai, S. (eds.) ASIACRYPT 2019, Part I. LNCS, vol. 11921, pp. 552–583. Springer, December 2019

    Google Scholar 

  5. Bonnetain, X., Jaques, S.: Quantum period finding against symmetric primitives in practice. CoRR abs/2011.07022 (2020), https://arxiv.org/abs/2011.07022

  6. Bonnetain, X., Naya-Plasencia, M., Schrottenloher, A.: On quantum slide attacks. In: Paterson, K.G., Stebila, D. (eds.) SAC 2019. LNCS, vol. 11959, pp. 492–519. Springer, August 2019

    Google Scholar 

  7. Brassard, G., Hoyer, P.: An exact quantum polynomial-time algorithm for Simon’s problem. In: Proceedings of the Fifth Israeli Symposium on Theory of Computing and Systems, pp. 12–23 (1997)

    Google Scholar 

  8. Brassard, G., Høyer, P., Mosca, M., Tapp, A.: Quantum amplitude amplification and estimation. In: Lomo-naco, S.J., Brandt, H.E. (eds.) Quantum Computation and Information, AMS Contemporary Mathematics, vol. 305 (2002)

    Google Scholar 

  9. Cid, C., Hosoyamada, A., Liu, Y., Sim, S.M.: Quantum cryptanalysis on contracting feistel structures and observation on related-key settings. In: Bhargavan, K., Oswald, E., Prabhakaran, M. (eds.) INDOCRYPT 2020. LNCS, vol. 12578, pp. 373–394. Springer, Cham (2020). https://doi.org/10.1007/978-3-030-65277-7_17

    Chapter  Google Scholar 

  10. Dong, X., Dong, B., Wang, X.: Quantum attacks on some Feistel block ciphers. Des. Codes Cryptogr. 88(6), 1179–1203 (2020)

    Google Scholar 

  11. Dong, X., Li, Z., Wang, X.: Quantum cryptanalysis on some generalized Feistel schemes. Sci. China Inf. Sci. 62(2), 22501:1–22501:12 (2019)

    Google Scholar 

  12. Dong, X., Wang, X.: Quantum key-recovery attack on feistel structures. Sci. China Inf. Sci. 61(10), 102501:1–102501:7 (2018)

    Google Scholar 

  13. Hodžić, S., Knudsen Ramkilde, L., Brasen Kidmose, A.: On quantum distinguishers for Type-3 generalized Feistel network based on separability. In: Ding, J., Tillich, J.-P. (eds.) PQCrypto 2020. LNCS, vol. 12100, pp. 461–480. Springer, Cham (2020). https://doi.org/10.1007/978-3-030-44223-1_25

    Chapter  Google Scholar 

  14. Hodžić, S., Knudsen, L.: A quantum distinguisher for 7/8-round sms4 block cipher. Quant. Inf. Process. 19, 411 (2020)

    Google Scholar 

  15. Hosoyamada, A., Aoki, K.: On quantum related-key attacks on iterated even-mansour ciphers. In: Obana, S., Chida, K. (eds.) IWSEC 2017. LNCS, vol. 10418, pp. 3–18. Springer, Cham (2017). https://doi.org/10.1007/978-3-319-64200-0_1

    Chapter  Google Scholar 

  16. Hosoyamada, A., Sasaki, Y.: Cryptanalysis against symmetric-key schemes with online classical queries and offline quantum computations. In: Smart, N.P. (ed.) CT-RSA 2018. LNCS, vol. 10808, pp. 198–218. Springer, Cham, April 2018

    Google Scholar 

  17. Ito, G., Hosoyamada, A., Matsumoto, R., Sasaki, Yu., Iwata, T.: Quantum chosen-ciphertext attacks against feistel ciphers. In: Matsui, M. (ed.) CT-RSA 2019. LNCS, vol. 11405, pp. 391–411. Springer, Cham (2019). https://doi.org/10.1007/978-3-030-12612-4_20

    Chapter  Google Scholar 

  18. Kaplan, M., Leurent, G., Leverrier, A., Naya-Plasencia, M.: Breaking symmetric cryptosystems using quantum period finding. In: Robshaw, M., Katz, J. (eds.) CRYPTO 2016, Part II. LNCS, vol. 9815, pp. 207–237. Springer, August 2016

    Google Scholar 

  19. Koiran, P., Nesme, V., Portier, N.: The quantum query complexity of the abelian hidden subgroup problem. Theor. Comput. Sci. 380(1–2), 115–126 (2007)

    Google Scholar 

  20. Kuwakado, H., Morii, M.: Quantum distinguisher between the 3-round feistel cipher and the random permutation. In: IEEE Proceedings of the International Symposium on Information Theory (ISIT 2010), June 13–18, 2010, pp. 2682–2685. Austin (2010)

    Google Scholar 

  21. Kuwakado, H., Morii, M.: Security on the quantum-type even-mansour cipher. In: Proceedings of ISITA 2012, . October 28–31, pp. 312–316. Honolulu, HI (2012)

    Google Scholar 

  22. Leander, G., May, A.: Grover meets Simon - quantumly attacking the FX-construction. In: Takagi, T., Peyrin, T. (eds.) ASIACRYPT 2017, Part II. LNCS, vol. 10625, pp. 161–178. Springer, December 2017

    Google Scholar 

  23. May, A., Schlieper, L.: Quantum period finding with a single output qubit - factoring n-bit RSA with n/2 qubits. CoRR abs/1905.10074 (2019)

    Google Scholar 

  24. Ni, B., Ito, G., Dong, X., Iwata, T.: Quantum attacks against type-1 generalized Feistel ciphers and applications to CAST-256. In: Hao, F., Ruj, S., Sen Gupta, S. (eds.) INDOCRYPT 2019. LNCS, vol. 11898, pp. 433–455. Springer, December 2019

    Google Scholar 

  25. Nielsen, M.A., Chuang, I.L.: Quantum Computation and Quantum Information, 10th Anniversary edn. Cambridge University Press, Cambridge (2016)

    Google Scholar 

  26. Rahman, M., Paul, G.: Quantum attacks on HCTR and its variants. IACR Cryptol. ePrint Arch. 2020, 802 (2020)

    Google Scholar 

  27. Roetteler, M., Steinwandt, R.: A note on quantum related-key attacks. Inf. Process. Lett. 115(1), 40–44 (2015)

    Google Scholar 

  28. Santoli, T., Schaffner, C.: Using Simon’s algorithm to attack symmetric-key cryptographic primitives. Quant. Inf. Comput. 17(1 & 2), 65–78 (2017)

    Google Scholar 

  29. Shor, P.W.: Algorithms for quantum computation: Discrete logarithms and factoring. In: 35th FOCS, pp. 124–134. IEEE Computer Society Press, November 1994

    Google Scholar 

  30. Simon, D.R.: On the power of quantum computation. In: 35th FOCS, pp. 116–123. IEEE Computer Society Press, November 1994

    Google Scholar 

  31. Zalka, C.: Grover’s quantum searching algorithm is optimal. Phys. Rev. A 60(4), 2746 (1999)

    Google Scholar 

Download references

Acknowledgements

The author would like to thank André Schrottenloher and Akinori Hosoyamada for interesting discussions.

Author information

Authors and Affiliations

  1. Institute for Quantum Computing, Department of Combinatorics and Optimization, University of Waterloo, Waterloo, Canada

    Xavier Bonnetain

Authors
  1. Xavier Bonnetain
    View author publications

    You can also search for this author in PubMed Google Scholar

Corresponding author

Correspondence to Xavier Bonnetain .

Editor information

Editors and Affiliations

  1. Microsoft Research, Redmond, WA, USA

    Patrick Longa

  2. Universitat Pompeu Fabra, Barcelona, Spain

    Carla Ràfols

Rights and permissions

Reprints and permissions

Copyright information

© 2021 Springer Nature Switzerland AG

About this paper

Check for updates. Verify currency and authenticity via CrossMark

Cite this paper

Bonnetain, X. (2021). Tight Bounds for Simon’s Algorithm. In: Longa, P., Ràfols, C. (eds) Progress in Cryptology – LATINCRYPT 2021. LATINCRYPT 2021. Lecture Notes in Computer Science(), vol 12912. Springer, Cham. https://doi.org/10.1007/978-3-030-88238-9_1

Download citation

  • DOI: https://doi.org/10.1007/978-3-030-88238-9_1

  • Published:

  • Publisher Name: Springer, Cham

  • Print ISBN: 978-3-030-88237-2

  • Online ISBN: 978-3-030-88238-9

  • eBook Packages: Computer ScienceComputer Science (R0)

Publish with us

Policies and ethics

Search

Navigation