The result of resource consumption in quantum attack implementation of cryptographic algorithm is an important metric to evaluate the security strength of cryptographic algorithm against quantum attack. This paper studies complete implementation of quantum attack on cryptographic algorithm using Grover meets Simon method. We find 9-round quantum distinguisher whose round is the longest currently about TWINE, and utilize Grover meets Simon method to carry out 14/15-round quantum key recovery attack on TWINE-80/TWINE-128 with lower complexity than exhaust attack. Furthermore, we give complete implementation of quantum oracle and QAA algorithm in TWINE’s quantum key recovery attack for the first time. The circuit is suitable for all implementation of quantum key recovery attack on block cipher using Grover meets Simon method.
The result of resource consumption in quantum attack implementation of cryptographic algorithm is an important metric to evaluate the security strength of cryptographic algorithm against quantum attack. This paper studies complete implementation of quantum attack on cryptographic algorithm using Grover meets Simon method. We find 9-round quantum distinguisher whose round is the longest currently about TWINE, and utilize Grover meets Simon method to carry out 14/15-round quantum key recovery attack on TWINE-80/TWINE-128 with lower complexity than exhaust attack. Furthermore, we give complete implementation of quantum oracle and QAA algorithm in TWINE’s quantum key recovery attack for the first time. The circuit is suitable for all implementation of quantum key recovery attack on block cipher using Grover meets Simon method.
Abstract The quantum security of lightweight block ciphers is receiving more and more attention. However, the existing quantum attacks on lightweight block ciphers only focused on the quantum exhaustive search, while the quantum attacks combined with classical cryptanalysis methods haven’t been well studied. In this paper, we study quantum key recovery attack on SIMON32/64 using Quantum Amplitude Amplification algorithm in Q1 model. At first, we reanalyze the quantum circuit complexity of quantum exhaustive search on SIMON32/64. We estimate the Clifford gates count more accurately and reduce the T gate count. Also, the T-depth and full depth is reduced due to our minor modifications. Then, using four differentials given by Biryukov in FSE 2014 as our distinguisher, we give our quantum key recovery attack on 19-round SIMON32/64. We treat the two phases of key recovery attack as two QAA instances separately, and the first QAA instance consists of four sub-QAA instances. Then, we design the quantum circuit of these two QAA instances and estimate their corresponding quantum circuit complexity. We conclude that the quantum circuit of our quantum key recovery attack is lower than quantum exhaustive search. Our work firstly studies the quantum dedicated attack on SIMON32/64. And this is the first work to study the complexity of quantum dedicated attacks from the perspective of quantum circuit complexity, which is a more fine-grained analysis of quantum dedicated attacks’ complexity.
Because of the substantial progress in quantum computing technology, the safety of traditional cryptologic schemes is facing serious challenges. In this study, we explore the quantum safety of the lightweight cipher MIBS and propose quantum key-recovery attacks on the MIBS cipher by utilizing Grover’s algorithm and Bernstein–Vazirani algorithm. We first construct linear-structure functions based on the 5-round MIBS cipher according to the characteristics of the linear transformations, and then we obtain a quantum distinguisher of the 5-round MIBS cipher by applying Bernstein–Vazirani algorithm to the constructed functions. Finally, utilizing this distinguisher and Grover’s algorithm, we realize a 7-round key-recovery attack on the MIBS cipher, and then we expand the attack to more rounds of MIBS based on a similar idea. The quantum attack on the 7-round MIBS requires 156 qubits and has a time complexity of 210.5. An 8-round attack requires 179 qubits and has a time complexity of 222. Compared with existing quantum attacks, our attacks have better time complexity when attacking the same number of rounds.
Quantum computing plays a vital role in the next generation computing platforms as researchers have achieved quantum supremacy by proving that quantum computers can outperform classical computers. These high performance computers will pose a serious threat to the security of the conventional cryptographic algorithms. The secret key of the conventional cryptographic algorithms when implemented by quantum circuits can easily be recovered with the help of Grover key search algorithm. The Grover’s algorithm requires low cost quantum implementation of cryptographic algorithms in order to mount the quantum key recovery attack successfully. Hence the low cost quantum implementation of conventional cryptographic algorithms to mount quantum key recovery attack using Grover search algorithm is an active area of research. This work proposes a novel quantum circuit implementation of two lightweight block ciphers namely PUFFIN and PRINT and for the first time in literature In-place method is used to optimize the quantum resources in these two ciphers which helps to build compact quantum circuits without extra ancilla inputs. The performance metrics considered in this work to quantify the quantum resources of the proposed circuits are number of quantum gates, quantum cost, latency and number of qubits. In addition, the quantum resources are also estimated to mount the quantum key recovery attacks on the proposed quantum circuit implementations of PUFFIN and PRINT using Grover-based key search algorithm.
Abstract Grover’s algorithm reduces the security level of the target cipher from n-bit to n/2-bit. To implement Grover’s algorithm, a quantum circuit capable of performing the target cipher operations must be constructed. In this paper, we propose a quantum circuit implementation scheme for the involutive lightweight block cipher (IVLBC) block cipher. We utilized the DORCIS tool to implement the quantum circuit for the S-box and applied Gaussian elimination to construct the quantum circuit for matrix multiplication. Subsequently, we evaluated the overall quantum resource consumption required for the implementation. Based on this, we performed a quantum attack on IVLBC using Grover’s algorithm, calculating the attack cost using the NCT gate library, and further analyzed its security. Finally, we conducted a comparative analysis of the classical attack complexity and quantum attack complexity of IVLBC, highlighting the potential of using quantum complexity as a standard for future security assessments.
Grover search algorithm is the most representative quantum attack method that threatens the security of symmetric key cryptography. If the Grover search algorithm is applied to symmetric key cryptography, the security level of target symmetric key cryptography can be lowered from n-bit to n2-bit. When applying Grover’s search algorithm to the block cipher that is the target of potential quantum attacks, the target block cipher must be implemented as quantum circuits. Starting with the AES block cipher, a number of works have been conducted to optimize and implement target block ciphers into quantum circuits. Recently, many studies have been published to implement lightweight block ciphers as quantum circuits. In this paper, we present optimal quantum circuit designs of symmetric key cryptography, including PRESENT and GIFT block ciphers. The proposed method optimized PRESENT and GIFT block ciphers by minimizing qubits, quantum gates, and circuit depth. We compare proposed PRESENT and GIFT quantum circuits with other results of lightweight block cipher implementations in quantum circuits. Finally, quantum resources of PRESENT and GIFT block ciphers required for the oracle of the Grover search algorithm were estimated.
With the development of quantum technology, quantum computing has an increasingly significant impact on cryptanalysis. Several quantum algorithms, such as Simon’s algorithm, Grover’s algorithm, the Bernstein–Vazirani algorithm, Shor’s algorithm, and the Grover-meets-Simon algorithm, have been proposed successively. However, almost all cryptanalysis is based on the quantum chosen-plaintext attack (qCPA) model. This paper focuses on a powerful cryptanalytic model, quantum related-key attack (qRKA), and proposes a strategy of qRKAs against symmetric ciphers using Simon’s algorithm. We construct a periodic function to efficiently recover the secret key of symmetric ciphers if the attacked symmetric ciphers satisfy Simon’s promise, and present the complexity analysis on specific symmetric ciphers. Then, we apply qRKA to the Even–Mansour cipher and SoEM construction, recover their secret keys, and show their complexity comparison in the distinct attack models. This work is of great significance for the qRKA cryptanalysis of existing provably secure cryptographic schemes and the design of future quantum secure cryptographic schemes.