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

Zero-correlation linear analysis for block ciphers based on the Bernstein–Vazirani and Grover algorithms

  • Published:
Quantum Information Processing Aims and scope Submit manuscript

Abstract

With the rapid development of quantum computing technology, the traditional cryptosystem will face a significant threat. It is an urgent security issue to study the security impact of quantum computing on classical cryptosystems and provide reliable cryptographic primitives for the post-quantum era. A powerful way to solve this problem is to quantize the classical cryptanalysis tools and use the improved versions for cryptanalysis. In this paper, we propose a quantum Zero-correlation analysis algorithm based on the Bernstein–Vazirani and Grover algorithms. It can find zero-correlation linear hulls for Feistel and SPN structures. We prove the correctness of the algorithm and analyze its complexity. Compared with the classical algorithms, the proposed quantum algorithm has significant advantages when the number of encryption rounds of block ciphers is large. Moreover, compared with the existing quantum Zero-correlation linear analysis, the proposed algorithm is more efficient and does not depend on the algebraic characteristics of the target cipher, which makes the algorithm has more flexible application scenarios. With the development of quantum computers, we discuss the threat of quantum cryptanalysis algorithms to classical security.

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

Access this article

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

Price includes VAT (United Kingdom)

Instant access to the full article PDF.

Institutional subscriptions

Fig. 1
Fig. 2
Fig. 3
Fig. 4
Fig. 5
Fig. 6

Similar content being viewed by others

Explore related subjects

Discover the latest articles, news and stories from top researchers in related subjects.

Data Availability Statement

The data that support the findings of this study are available from the corresponding author upon reasonable request.

References

  1. Shor, P.: Algorithms for quantum computation: discrete logarithms and factoring. In Proceedings of 35th Annual Symposium on the Foundations of Computer Science, IEEE Computer Society Press, Los Alamitos, CA, 124–134 (1994)

  2. Grover, L.K.: A fast quantum mechanical algorithm for database search. Proceedings of the twenty-eighth annual ACM symposium on Theory of computing, 212–219 (1996)

  3. Simon, Daniel, R.: On the power of quantum computation. SIAM journal on computing 26(5), 1474–1483 (1997)

  4. Bernstein, E., Vazirani, U.: Quantum complexity theory. In: Proceedings of the Twenty-fifth Annual ACM Symposium on Theory of Computing, pp. 11–20 (1993)

  5. Kuwakado, H., Morii, M.: Quantum distinguisher between the 3-round feistel cipher and the random permutation. In: 2010 IEEE International Symposium on Information Theory, pp. 2682–2685 (2010)

  6. Kuwakado, H., Morii, M.: Security on the quantum-type even-mansour cipher. In: 2012 International Symposium on Information Theory and Its Applications, pp. 312–316 (2012)

  7. Santoli, T., Schaffner, C.: Using simon’s algorithm to attack symmetric-key cryptographic primitives. arXiv preprint arXiv:1603.07856 (2016)

  8. Dong, X., Wang, X.: Quantum key-recovery attack on feistel structures. SCIENCE CHINA Inf. Sci. 61, 1–7 (2018)

    Article  Google Scholar 

  9. Dong, X., Li, Z., Wang, X.: Quantum cryptanalysis on some generalized feistel schemes. SCIENCE CHINA Inf. Sci. 62(2), 22501 (2019)

    Article  MathSciNet  Google Scholar 

  10. Jaques, S., Naehrig, M., Roetteler, M., Virdia, F.: Implementing grover oracles for quantum key search on aes and lowmc. In: Advances in Cryptology–EUROCRYPT 2020: 39th Annual International Conference on the Theory and Applications of Cryptographic Techniques, Zagreb, Croatia, May 10–14, 2020, Proceedings, Part II 30, pp. 280–310 (2020)

  11. Leander, G., May, A.: Grover meets simon–quantumly attacking the fx-construction. In: Advances in Cryptology–ASIACRYPT 2017: 23rd International Conference on the Theory and Applications of Cryptology and Information Security, Hong Kong, China, December 3-7, 2017, Proceedings, Part II 23, pp. 161–178 (2017)

  12. Kaplan, M., Leurent, G., Leverrier, A., Naya-Plasencia, M.: Breaking symmetric cryptosystems using quantum period finding. In: Advances in Cryptology–CRYPTO 2016: 36th Annual International Cryptology Conference, Santa Barbara, CA, USA, August 14-18, 2016, Proceedings, Part II 36, pp. 207–237 (2016)

  13. Zhou, Q., Lu, S., Zhang, Z., Sun, J.: Quantum differential cryptanalysis. Quantum Inf. Process. 14, 2101–2109 (2015)

    Article  ADS  Google Scholar 

  14. Kaplan, M., Leurent, G., Leverrier, A., Naya-Plasencia, M.: Quantum differential and linear cryptanalysis. arXiv preprint arXiv:1510.05836 (2015)

  15. Hosoyamada, A., Sasaki, Y.: Finding hash collisions with quantum computers by using differential trails with smaller probability than birthday bound. In: Advances in Cryptology–EUROCRYPT 2020: 39th Annual International Conference on the Theory and Applications of Cryptographic Techniques, Zagreb, Croatia, May 10–14, 2020, Proceedings, Part II 30, pp. 249–279 (2020)

  16. Dong, X., Sun, S., Shi, D., Gao, F., Wang, X., Hu, L.: Quantum collision attacks on aes-like hashing with low quantum random access memories. In: Advances in Cryptology–ASIACRYPT 2020: 26th International Conference on the Theory and Application of Cryptology and Information Security, Daejeon, South Korea, December 7–11, 2020, Proceedings, Part II 26, pp. 727–757 (2020)

  17. Bogdanov, A., Rijmen, V.: Linear hulls with correlation zero and linear cryptanalysis of block ciphers. Des. Codes Crypt. 70, 369–383 (2014)

    Article  MathSciNet  Google Scholar 

  18. Shi, R., Xie, H., Feng, H., Yuan, F., Liu, B.: Quantum zero-correlation linear cryptanalysis. Quantum Inf. Process. 21(8), 293 (2022)

    Article  ADS  MathSciNet  Google Scholar 

  19. Xie, H., Yang, L.: Quantum miss-in-the-middle attack. arXiv preprint arXiv:1812.08499 (2018)

  20. Li, H., Yang, L.: Quantum differential cryptanalysis to the block ciphers. In: Applications and Techniques in Information Security: 6th International Conference, ATIS 2015, Beijing, China, November 4-6, 2015, Proceedings 6, pp. 44–51 (2015)

  21. Dubuc, S.: Characterization of linear structures. Des. Codes Crypt. 22, 1573–7586 (2001)

    Article  MathSciNet  Google Scholar 

  22. Li, H., Yang, L.: A quantum algorithm to approximate the linear structures of boolean functions. Math. Struct. Comput. Sci. 28(1), 1–13 (2018)

    Article  MathSciNet  Google Scholar 

  23. Xie, H., Yang, L.: Using bernstein-vazirani algorithm to attack block ciphers. Des. Codes Crypt. 87, 1161–1182 (2019)

    Article  MathSciNet  Google Scholar 

  24. Xie, H., Yang, L.: A quantum related-key attack based on the bernstein-vazirani algorithm. Quantum Inf. Process. 19, 1–20 (2020)

    Article  ADS  MathSciNet  Google Scholar 

  25. Zhou, B.-M., Yuan, Z.: Quantum key-recovery attack on feistel constructions: Bernstein-vazirani meet grover algorithm. Quantum Inf. Process. 20, 1–14 (2021)

    Article  ADS  MathSciNet  Google Scholar 

  26. Chen, H., Li, Y., Abla, P., Li, Z., Jiao, L., Wang, M.: Quantum algorithm for finding impossible differentials and zero-correlation linear hulls of symmetric ciphers. In: Australasian Conference on Information Security and Privacy, pp. 431–451 (2023)

  27. Nyberg, K.: Constructions of bent functions and difference sets. In: Advances in Cryptology-EUROCRYPT’90: Workshop on the Theory and Application of Cryptographic Techniques Aarhus, Denmark, May 21–24, 1990 Proceedings 9, pp. 151–160 (1991)

  28. Sun, B., Liu, Z., Rijmen, V., Li, R., Cheng, L., Wang, Q., AlKhzaimi, H., Li, C.: Links among impossible differential, integral and zero-correlation linear cryptanalysis. In: Advances in Cryptology–CRYPTO 2015: 35th Annual Cryptology Conference, Santa Barbara, CA, USA, August 16-20, 2015, Proceedings, Part I, pp. 95–115 (2015)

  29. Cross, A.W., Bishop, L.S., Sheldon, S., Nation, P.D., Gambetta, J.M.: Validating quantum computers using randomized model circuits. Phys. Rev. A 100(3), 032328 (2019)

    Article  ADS  Google Scholar 

  30. Dario, G.: The 2022 ibm research annual letter. IEEE Specturm (2022)

  31. Gent, E.: Ibm’s target: A 4,000-qubit processor by 2025. IEEE Specturm (2022)

Download references

Acknowledgements

This project was supported by the National Natural Science Foundation of China (No. 61971021), the Key Research and Development Program of Hebei Province (No. 22340701D), and the Chinese Universities Industry-Education-Research Innovation Foundation of BII Education Grant Program (No. 2021BCA0200) for valuable helps.

Author information

Authors and Affiliations

  1. School of Cyber Science and Technology, Beihang University, Beijing, 100083, China

    Kun Zhang, Tao Shang, Yao Tang & Jianwei Liu

Authors
  1. Kun Zhang
    View author publications

    You can also search for this author in PubMed Google Scholar

  2. Tao Shang
    View author publications

    You can also search for this author in PubMed Google Scholar

  3. Yao Tang
    View author publications

    You can also search for this author in PubMed Google Scholar

  4. Jianwei Liu
    View author publications

    You can also search for this author in PubMed Google Scholar

Contributions

K.Z. and T.S. proposed the idea and conducted the analyses. All authors reviewed the manuscript.

Corresponding author

Correspondence to Tao Shang.

Ethics declarations

Conflict of interest

The authors declare no conflict of interest.

Additional information

Publisher's Note

Springer Nature remains neutral with regard to jurisdictional claims in published maps and institutional affiliations.

Rights and permissions

Springer Nature or its licensor (e.g. a society or other partner) holds exclusive rights to this article under a publishing agreement with the author(s) or other rightsholder(s); author self-archiving of the accepted manuscript version of this article is solely governed by the terms of such publishing agreement and applicable law.

Reprints and permissions

About this article

Check for updates. Verify currency and authenticity via CrossMark

Cite this article

Zhang, K., Shang, T., Tang, Y. et al. Zero-correlation linear analysis for block ciphers based on the Bernstein–Vazirani and Grover algorithms. Quantum Inf Process 23, 289 (2024). https://doi.org/10.1007/s11128-024-04491-x

Download citation

  • Received:

  • Accepted:

  • Published:

  • DOI: https://doi.org/10.1007/s11128-024-04491-x

Keywords

Search

Navigation