TY - JOUR
ID - 154316
TI - Quantum Cryptanalysis of Symmetric Primitives by Improving Relaxed Variants of Simon’s Algorithm
JO - The ISC International Journal of Information Security
JA - ISECURE
LA - en
SN - 2008-2045
AU - Khosravi, Ali
AU - Eghlidos, Taraneh
AD - Sharif University of Technology, Department of Electrical Engineering, Tehran, Iran
AD - Electronics Research Institute, Sharif University of Technology, Tehran, Iran.
Y1 - 2023
PY - 2023
VL - 15
IS - 1
SP - 83
EP - 95
KW - Modes of Operation
KW - Quantum Cryptanalysis
KW - Quantum Distinguishers
KW - Quantum Key Recovery Attack
KW - Quantum Related Key Attack
KW - Quantum Slide Attack
KW - Symmetric Cipher
DO - 10.22042/isecure.2022.321346.739
N2 - 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.
UR - https://www.isecure-journal.com/article_154316.html
L1 - https://www.isecure-journal.com/article_154316_46fe659b3a964677d2f7294bc63657e8.pdf
ER -