Quantum Cryptanalysis of Symmetric Primitives by Improving Relaxed Variants of Simon’s Algorithm

Khosravi, Ali; Eghlidos, Taraneh

doi:10.22042/isecure.2022.321346.739

Quantum Cryptanalysis of Symmetric Primitives by Improving Relaxed Variants of Simon’s Algorithm

Document Type : Research Article

Authors

Ali Khosravi ¹

Taraneh Eghlidos ²

¹ Sharif University of Technology, Department of Electrical Engineering, Tehran, Iran

² Electronics Research Institute, Sharif University of Technology, Tehran, Iran.

https://doi.org/10.22042/isecure.2022.321346.739

Abstract

The main goal of Simon’s Algorithm is to find the period of periodic functions. However, if the target function does not satisfy Simon's promise completely or if the number of superposition queries of the adversary is limited, Simon's algorithm cannot compute the actual period, unambiguously. These problems may lead to the failure of period-finding-based (PFB) quantum attacks. We focus in this paper on relaxing Simon's algorithm so that quantum adversaries can still carry out the mentioned attacks without any assumptions on the target function. To that end, we use two different methods, which are suitable for some of PFB quantum attacks. In the first method, as a complement to Kaplan's suggestion, we show that using Simon's algorithm one can find proper partial periods of Boolean vector functions, so that the probability of their establishment, independent of the target function, is directly related to the number of the attacker's quantum queries. Next, we examine how one can use partial period instead of the actual one. The advantage of this method is twofold: It enables the attackers to perform the quantum PFB distinguishers, with smaller number of quantum queries than those of the previous relaxation method. On the other hand, it generalizes the previous forgery attacks on modes of operation for message authentication codes. In the second method, we use Grover's algorithm, as a complement to Simon's algorithm in quantum key recovery attacks. This ensures that the time complexity of the mentioned attacks is less than that of a quantum brute-force attack.

Keywords

Modes of Operation

Quantum Cryptanalysis

Quantum Distinguishers

Quantum Key Recovery Attack

Quantum Related Key Attack

Quantum Slide Attack

Symmetric Cipher

20.1001.1.20082045.2023.15.1.3.0

[1] Peter W Shor. Algorithms for quantum computation: discrete logarithms and factoring. In Proceedings 35th annual symposium on foundations of computer science, pages 124–134. IEEE, 1994.
[2] Lov K Grover. A fast quantum mechanical algorithm for database search. In Proceedings of the twenty-eighth annual ACM symposium on Theory of computing, pages 212–219, 1996.
[3] Daniel R Simon. On the power of quantum computation. SIAM journal on computing, 26(5):1474–1483, 1997.
[4] Gembu Ito, Akinori Hosoyamada, Ryutaroh Matsumoto, Yu Sasaki, and Tetsu Iwata. Quantum chosen-ciphertext attacks against feistel ciphers. In Cryptographers’ Track at the RSA Conference, pages 391–411. Springer, 2019.
[5] Marc Kaplan, Ga¨etan Leurent, Anthony Leverrier, and Mar´ıa Naya-Plasencia. Breaking symmetric cryptosystems using quantum period finding. In Annual international cryptology conference, pages 207–237. Springer, 2016.
[6] Hidenori Kuwakado and Masakatu Morii. Quantum distinguisher between the 3-round feistel cipher and the random permutation. In 2010 IEEE International Symposium on Information Theory, pages 2682–2685. IEEE, 2010.
[7] Huiqin Xie and Li Yang. Quantum miss-in-themiddle attack. arXiv preprint arXiv:1812.08499, 2018.
[8] Hidenori Kuwakado and Masakatu Morii. Security on the quantum-type even-mansour cipher. In 2012 International Symposium on Information Theory and its Applications, pages 312–316. IEEE, 2012.
[9] Shimon Even and Yishay Mansour. A construction of a cipher from a single pseudorandom permutation. Journal of cryptology, 10(3):151–161,1997.
[10] Martin Roetteler and Rainer Steinwandt. A note on quantum related-key attacks. Information Processing Letters, 115(1):40–44, 2015.
[11] Xavier Bonnetain, Mar´ıa Naya-Plasencia, and Andr´e Schrottenloher. On quantum slide attacks. In International Conference on Selected Areas in Cryptography, pages 492–519. Springer, 2019.
[12] Gregor Leander and Alexander May. Grover meets simon–quantumly attacking the fxconstruction. In International Conference on the Theory and Application of Cryptology and Information Security, pages 161–178. Springer, 2017.
[13] Andr´e Chailloux, Mar´ıa Naya-Plasencia, and Andr´e Schrottenloher. An efficient quantum collision search algorithm and implications on symmetric cryptography. In International Conference on the Theory and Application of Cryptology and Information Security, volume 10625, pages 211–240. Springer, 2017.
[14] Mar´ıa Naya-Plasencia. Preparing symmetric crypto for the quantum world. In FSE 2019-26th Annual Fast Software Encryption Conference, 2019.
[15] Akinori Hosoyamada and Yu Sasaki. Cryptanalysis against symmetric-key schemes with online classical queries and offline quantum computations. In Cryptographers’ Track at the RSA Conference, volume 10808, pages 198–218. Springer, 2018.
[16] Xavier Bonnetain, Akinori Hosoyamada, Mar´ıa Naya-Plasencia, Yu Sasaki, and Andr´e Schrottenloher. Quantum attacks without superposition queries: the offline simon’s algorithm. In International Conference on the Theory and Application of Cryptology and Information Security, pages 552–583. Springer, 2019.
[17] Xuexuan Hao, Fengrong Zhang, Yongzhuang Wei, and Yong Zhou. Quantum period finding based on the bernstein-vazirani algorithm. Quantum Inf. Comput., 20(1&2):65–84, 2020.
[18] Mark Zhandry. A note on quantum-secure prps. arXiv preprint arXiv:1611.05564, 2016.
[19] Ping Wang, Shengping Tian, Zhiwei Sun, and Ning Xie. Quantum algorithms for hash preimage attacks. Quantum Engineering, 2(2):e36, 2020.
[20] Gilles Brassard, Peter Høyer, and Alain Tapp. Quantum cryptanalysis of hash and claw-free functions. In Latin American Symposium on Theoretical Informatics, pages 163–169. Springer, 1998.
[21] Marc Kaplan, Ga¨etan Leurent, Anthony Leverrier, and Mar´ıa Naya-Plasencia. Quantum differential and linear cryptanalysis. arXiv preprint arXiv:1510.05836, 2015.
[22] Huiqin Xie and Li Yang. Using bernstein–vazirani algorithm to attack block ciphers. Designs, Codes and Cryptography, 87(5):1161–1182, 2019.
[23] Hongwei Li and Li Yang. A quantum algorithm to approximate the linear structures of boolean functions. Mathematical Structures in Computer Science, 28(1):1–13, 2018.
[24] W Hoeffding. Probability inequalities for sums of bounded random variables, amer. ˇz. Statist.Assoc. J, 1329, 1963.
[25] Mayuresh Vivekanand Anand, Ehsan Ebrahimi Targhi, Gelo Noel Tabia, and Dominique Unruh. Post-quantum security of the cbc, cfb, ofb, ctr, and xts modes of operation. In Post-Quantum Cryptography, pages 44–63. Springer, 2016.