A quantum distinguisher for 7/8-round SMS4 block cipher
- PDF / 523,306 Bytes
- 22 Pages / 439.37 x 666.142 pts Page_size
- 77 Downloads / 217 Views
A quantum distinguisher for 7/8-round SMS4 block cipher S. Hodži´c1
· L. R. Knudsen1
Received: 2 March 2020 / Accepted: 30 October 2020 / Published online: 13 November 2020 © Springer Science+Business Media, LLC, part of Springer Nature 2020
Abstract Constructions of quantum distinguishers (extended to key recovery attacks) for generalized Feistel networks have been recently proposed in several works, where the main focus has been on Type 1 and 2 schemes. In this work, we derive a quantum distinguisher for 7 and 8 rounds of the SMS4 block cipher, which belongs to the class of unbalanced (contracting) generalized Feistel schemes. In the former case, by applying Simon’s quantum algorithm we construct a quantum distinguisher that runs in (quantum) polynomial time O(n) (n is the branch size), while later we need to combine Simon’s and Grover’s algorithms in context of the amplitude amplification technique. We show that for the 8-round SMS4 cipher a quantum distinguisher can be constructed in both Q1 and Q2 attack models. This is achieved by applying the method of asymmetric search of a period, introduced by Bonnetain et al. (Advances in cryptology ASIACRYPT 2019, LNCS, 2019), where online and offline queries to the encryption oracle are separated. In this context, we answer the open problem posed by Dong et al. (Sci China Inf Sci 62:22501, 2019), which has been left open for construction of quantum distinguishers for ≥ 7 rounds. Moreover, we show that for the specific instance when the quantum oracle for 8 rounds of SMS4 cipher is available, one can extract the master secret key with the same complexity and number of qubits required for the 8-round distinguisher. Keywords Simon’s algorithm · Grover’s algorithm · Generalized Feistel network · SMS4 block cipher · Quantum cryptanalysis
B
S. Hodži´c [email protected] L. R. Knudsen [email protected]
1
Technical University of Denmark, DTU Compute, Kongens Lyngby, Denmark
123
411
Page 2 of 22
S. Hodži´c, L. R. Knudsen
1 Introduction The development of post-quantum cryptanalysis of block ciphers has received a significant attention in the last decade, due to interesting applications (mainly) of the quantum algorithms such as Simon’s [28], Grover’s [13], Shor’s [29], Bernstein-Vazirani’s [2] (and their combinations). In general, these algorithms have been utilized in many recent works for construction of quantum distinguishers and key recovery attacks. The work that raised an interest of the research community is due to Kuwakado and Morii [20], who found an application of Simon’s algorithm (for the first time) in context of the cryptanalysis of block ciphers. In their work, a construction of a quantum distinguisher for 3-round Feistel network [12] (which runs in polynomial time) has been derived. In further development of the quantum cryptanalysis, one of the most promising algorithms is the combination of Simon’s and Grover’s algorithm, in framework of the amplitude application technique derived by Brassard et al. [7]. Simon’s and Grover’s algorithms (along with their combina
Data Loading...
