arXiv:2407.10056

A Quantum Automatic Tool for Finding Impossible Differentials

Huiqin Xie, Qiqing Xia, Wang, Ke, Yanjun Li, Yang Li

Published Jul 14, 2024• 0 citations

Abstract

Due to the superiority of quantum computing, traditional cryptography is facing severe threat. This makes the security evaluation of cryptographic systems in quantum attack models significant and urgent. For symmetric ciphers, the security analysis heavily relies on cyptanalytic tools. Thus exploring the use of quantum algorithms to traditional cyptanalytic tools has drawn a lot of attention. In this study, we utilize quantum algorithms to improve impossible differential attack, and design two quantum automatic tools for searching impossible differentials. The proposed quantum algorithms exploit the idea of miss-in-the-middle and the properties of truncated differentials. We rigorously prove their validity and calculate the quantum resources required to implement them. Compared to existing classical automatic cryptanalysis, the quantum tools proposed have the advantage of accurately characterizing S-boxes while only requiring polynomial complexity, and can take into consideration the impact of the key schedules in single-key model.

DOI: 10.48550/arxiv.2407.10056

Related papers

Quantum Automated Tools for Finding Impossible Differentials

Huiqin Xie, Qiqing Xia, Ke Wang +2 more

Due to the superiority of quantum computing, traditional cryptography is facing a severe threat. This makes the security evaluation of cryptographic systems in quantum attack models both significant and urgent. For symmetric ciphers, the security analysis heavily relies on cryptanalysis tools. Thus, exploring the use of quantum algorithms in traditional cryptanalysis tools has garnered considerable attention. In this study, we utilize quantum algorithms to improve impossible differential attacks and design two quantum automated tools to search for impossible differentials. The proposed quantum algorithms exploit the idea of miss-in-the-middle and the properties of truncated differentials. We rigorously prove their validity and calculate the quantum resources required for their implementation. Compared to the existing classical automated cryptanalysis, the proposed quantum tools have the advantage of accurately characterizing S-boxes while only requiring polynomial complexity, and can take into consideration the impact of the key schedules in a single-key model.

MathematicsAug 22, 20240 citations

Quantum Miss-in-the-Middle Attack

Huiqin Xie, Li Yang

Traditional cryptography is facing great challenges with the development of quantum computing. Not only public-key cryptography, the applications of quantum algorithms to symmetric cryptanalysis has also drawn more and more attention. In this paper, we apply quantum algorithms to the miss-in-the-middle technique and propose a quantum algorithm for finding impossible differentials of general block ciphers. We prove that, as long as the attacked block cipher satisfies certain algebraic conditions, the outputs of the quantum algorithm will be impossible differentials of it except for a negligible probability. The proposed quantum algorithm has polynomial quantum complexity and does not require any quantum or classical query to the encryption oracle of the block cipher. Compared with traditional miss-in-the-middle technique, which is difficult to find impossible differentials as the number of rounds increases, the quantum version of miss-in-the-middle technique proposed in this paper is more conducive to find impossible differentials when the block cipher has a large number of rounds.

arXiv:1812.08499Dec 20, 20181 citation

Quantum impossible differential and truncated differential cryptanalysis

Huiqin Xie, Li Yang

Traditional cryptography is suffering a huge threat from the development of quantum computing. While many currently used public-key cryptosystems would be broken by Shor's algorithm, the effect of quantum computing on symmetric ones is still unclear. The security of symmetric ciphers relies heavily on the development of cryptanalytic tools. Thus, in order to accurately evaluate the security of symmetric primitives in the post-quantum world, it is significant to improve classical cryptanalytic methods using quantum algorithms. In this paper, we focus on two variants of differential cryptanalysis: truncated differential cryptanalysis and impossible differential cryptanalysis. Based on the fact that Bernstein-Vazirani algorithm can be used to find the linear structures of Boolean functions, we propose two quantum algorithms that can be used to find high-probability truncated differentials and impossible differentials of block ciphers, respectively. We rigorously prove the validity of the algorithms and analyze their complexity. Our algorithms treat all rounds of the reduced cipher as a whole and only concerns the input and output differences at its both ends, instead of specific differential characteristics. Therefore, to a certain extent, they alleviate the weakness of conventional differential cryptanalysis, namely the difficulties in finding differential characteristics as the number of rounds increases.

arXiv:1712.06997Dec 18, 20174 citations

Quantum Truncated Differential and Boomerang Attack

Huiqin Xie, Li Yang

In order to design quantum-safe block ciphers, it is crucial to investigate the application of quantum algorithms to cryptographic analysis tools. In this study, we use the Bernstein–Vazirani algorithm to enhance truncated differential cryptanalysis and boomerang cryptanalysis. We first propose a quantum algorithm for finding truncated differentials, then rigorously prove that the output truncated differentials must have high differential probability for the vast majority of keys in the key space. Subsequently, based on this algorithm, we design a quantum algorithm for finding boomerang distinguishers. The quantum circuits of the two proposed quantum algorithms contain only polynomial quantum gates and qubits. Compared with classical tools for searching truncated differentials or boomerang distinguishers, the proposed algorithms can maintain the polynomial complexity while fully considering the impact of S-boxes and key scheduling.

arXiv:2407.15126SymmetryAug 30, 20243 citations

Quantum differential and linear cryptanalysis

Gaëtan Leurent, Marc A. Kaplan, Anthony Leverrier +1 more

Quantum computers, that may become available one day, would impact many scientific fields, most notably cryptography since many asymmetric primitives are insecure against an adversary with quantum capabilities. Cryptographers are already anticipating this threat by proposing and studying a number of potentially quantum-safe alternatives for those primitives. On the other hand, symmetric primitives seem less vulnerable against quantum computing: the main known applicable result is Grover's algorithm that gives a quadratic speed-up for exhaustive search. In this work, we examine more closely the security of symmetric ciphers against quantum attacks. Since our trust in symmetric ciphers relies mostly on their ability to resist cryptanalysis techniques, we investigate quantum cryptanalysis techniques. More specifically, we consider quantum versions of differential and linear cryptanalysis. We show that it is usually possible to use quantum computations to obtain a quadratic speed-up for these attack techniques, but the situation must be nuanced: we don't get a quadratic speed-up for all variants of the attacks. This allows us to demonstrate the following non-intuitive result: the best attack in the classical world does not necessarily lead to the best quantum one. We give some examples of application on ciphers LAC and KLEIN. We also discuss the important difference between an adversary that can only perform quantum computations, and an adversary that can also make quantum queries to a keyed primitive.

Mar 6, 2017133 citations

Quantum Differential and Linear Cryptanalysis

Marc Kaplan, Gaëtan Leurent, Anthony Leverrier +1 more

Quantum computers, that may become available one day, would impact many scientific fields, most notably cryptography since many asymmetric primitives are insecure against an adversary with quantum capabilities. Cryptographers are already anticipating this threat by proposing and studying a number of potentially quantum-safe alternatives for those primitives. On the other hand, symmetric primitives seem less vulnerable against quantum computing: the main known applicable result is Grover’s algorithm that gives a quadratic speed-up for exhaustive search. In this work, we examine more closely the security of symmetric ciphers against quantum attacks. Since our trust in symmetric ciphers relies mostly on their ability to resist cryptanalysis techniques, we investigate quantum cryptanalysis techniques. More specifically, we consider quantum versions of differential and linear cryptanalysis. We show that it is usually possible to use quantum computations to obtain a quadratic speed-up for these attack techniques, but the situation must be nuanced: we don’t get a quadratic speed-up for all variants of the attacks. This allows us to demonstrate the following non-intuitive result: the best attack in the classical world does not necessarily lead to the best quantum one. We give some examples of application on ciphers LAC and KLEIN. We also discuss the important difference between an adversary that can only perform quantum computations, and an adversary that can also make quantum queries to a keyed primitive.

arXiv:1510.05836IACR Transactions on Symmetric CryptologyDec 1, 201627 citations