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.
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.
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.
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.
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.
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.
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.
The general context Cryptography is a computer discipline that aims to protect messages through encryption systems. In symmetric cryptography, a secret parameter, called a key, is used both to encrypt and to decrypt messages. The security provided by a symmetric encryption system is evaluated using cryptanalysis techniques which aim, for example, to find the secret key. Quantum computer arrival could impact the cryptographic field. Indeed, in 1994, Shor exhibited that quantum computers could be used to improve assymetric cryptanalysis [17]. With the recent breakthrough in quantum computer, the security of cryptographic primitives against quantum adversary can not be taken as guaranteed. The NIST launched a competition for new primitives that are safe even against adversaries that has access to a quantum computer. To estimate the quantum security of a cryptographic scheme, it is necessary to perform its quantum cryptanalysis. Quantum cryptanalysis techniques sometimes are quantum adaptation of classical cryptanalysis techniques. This transformation is called quantizing. Let's note that an attack is valid if and only if it is more efficient than the naive attack. In the classical setting, the naive attack is the generic exhaustive search, in the quantum setting, it is the Grover search algorithm [14].