Iranian Society of Cryptology The ISC International Journal of Information Security 2008-2045 15 1 2023 01 01 Quantum Cryptanalysis of Symmetric Primitives by Improving Relaxed Variants of Simon’s Algorithm 83 95 154316 10.22042/isecure.2022.321346.739 EN Ali Khosravi Sharif University of Technology, Department of Electrical Engineering, Tehran, Iran Taraneh Eghlidos Electronics Research Institute, Sharif University of Technology, Tehran, Iran. 0000-0002-3182-0277 Journal Article 2021 12 24 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. https://www.isecure-journal.com/article_154316_add947ef6d495a9cf63dde8273b1f10f.pdf