The security of a significant proportion of cryptography in use today depends directly or indirectly on the presumed difficulty of either factoring or extracting discrete logarithms in polynomial time on quantum computers. This paper discusses a quantum version of differential cryptanalysis which propounds quadratic speedup over the existing classical one. Linear cryptanalysis and differential cryptanalysis are general form cryptanalysis which is primarily applicable to block cipher, but also to stream ciphers and cryptographic hash functions. Linear cryptanalysis is a known-plaintext attack, in which attacker studies probabilistic linear relations known as linear approximations between some bits of plaintext, some bits of cipher text and some bits of cipher key. And in differential cryptanalysis the role of attacker is to analyze how differences in input information can affect the resulting difference at the output. Differential Cryptanalysis is a chosen-plaintext attack. However, differential cryptanalysis is more compelling so in this paper we are proposing a quantum version of the same. The computational complexity of classical differential cryptanalysis reaches O(NK). But by applying variations of Grover's search that is either full or partial Quantum Search the number of queries required to find the cipher key will be reduced.
The security of a significant proportion of cryptography in use today depends directly or indirectly on the presumed difficulty of either factoring or extracting discrete logarithms in polynomial time on quantum computers. This paper discusses a quantum version of differential cryptanalysis which propounds quadratic speedup over the existing classical one. Linear cryptanalysis and differential cryptanalysis are general form cryptanalysis which is primarily applicable to block cipher, but also to stream ciphers and cryptographic hash functions. Linear cryptanalysis is a known-plaintext attack, in which attacker studies probabilistic linear relations known as linear approximations between some bits of plaintext, some bits of cipher text and some bits of cipher key. And in differential cryptanalysis the role of attacker is to analyze how differences in input information can affect the resulting difference at the output. Differential Cryptanalysis is a chosen-plaintext attack. However, differential cryptanalysis is more compelling so in this paper we are proposing a quantum version of the same. The computational complexity of classical differential cryptanalysis reaches O(NK). But by applying variations of Grover's search that is either full or partial Quantum Search the number of queries required to find the cipher key will be reduced.
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.
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.
This paper focuses on quantum key-recovery attacks on block ciphers. Previous works on quantum differential and truncated differential attacks like [Kaplan et al., ToSC 2016] have shown that classical algorithms for key-recovery, typically based on generating differential pairs and sieving them, can be accelerated by up to a quadratic speedup using variants of quantum search, quantum amplitude amplification, and quantum collision-finding.>br/> In this paper, we introduce a new quantum truncated differential key-recovery attack, which leverages the quantum convolution algorithm introduced in [Schrottenloher, CRYPTO 2022] and previously used in linear cryptanalysis. We adapt this algorithm to the case of differential cryptanalysis, by rewriting the probability of a differential of an n-bit cipher as a convolution of functions with 2n-bit input. We then construct a quantum state whose amplitudes encode the probability of the differential for different key guesses, and use this as the starting point of a quantum search. In some cases (although not on practical ciphers so far), the speedup is better than quadratic compared to classical attacks. We also extend the framework to related-key differential attacks.We give applications to a 9-round attack on QARMAv2-64 adapted from [Ahmadian et al., DCC 2024] and a 12-round related-key attack on AES-256 from [Boura et al., CRYPTO 2023], which show improvement over classical attacks and over Kaplan et al.’s strategy when taking into account the amount of memory and the type of quantum memory used (as our attack requires only quantum-accessible classical memory).
Abstract Differential attack is a basic cryptanalysis method for block ciphers that exploits the high probability relations between the input and output differences. The existing work in quantum differential cryptanalysis of block ciphers is focused on resource estimation to recover the last round subkeys on the basis of relations constructed using classical methods. To find such relations using quantum computing, we propose a method to search the high probability differential and impossible differential characteristics. The method explores all possible input and output difference pairs using superposition of qubits. The proposed method is used to design the quantum circuit to search the differential characteristics for a toy cipher smallGIFT. We execute the quantum circuit on a quantum simulator to get differential and impossible characteristics. These characteristics are validated with the characteristics obtained using branch-and-bound based method. The differential characteristic is used to mount quantum key recovery attack using Grover's search. We provide the estimation of quantum resources to search the differential characteristics of lightweight block cipher GIFT-64 on a quantum computer.
Motivated by Shor’s algorithm and its attractive features, the milestone results in quantum cryptanalysis were the discovery of quantum differential and linear cryptanalysis. In quantum cryptanalysis, quantum distinguishers imitate the classical setting. Details differ; however, as the distinguisher in the quantum setting can take maximum coset superposition of all possible subsets of plaintext pairs. Using quantum measurements, the winning gap of the game is exploited so that a distinguisher can still guess the secret key perfectly with a constant probability. Symmetric primitives also suffer reduced ideal security in the quantum world, but this security reduction is less drastic than for most asymmetric primitives. Stream ciphers, block ciphers, and cryptographic hash functions are primitives that are believed to resist quantum attacks. Analogs to Shor’s algorithm may say how hard it is to build a quantum computer, but devising quantum algorithms to outperform the best classical attacks for widely-used cryptographic primitives is probably outside the reach of current even if exponentially growing noisy intermediate-scale quantum (NISQ) computers.
ABSTRACT Since the proposal of the Grover algorithm in 1996, which first combined quantum algorithms with symmetric cryptanalysis, significant progress has been made in the quantization of classical cryptanalysis methods. Differential‐linear cryptanalysis is a hybrid technique combining differential and linear cryptanalysis; however, there has been no prior work on its quantization. This paper presents a quantum differential‐linear key recovery attack framework. We apply this framework to Simon32/64 and Simeck32/64. Considering that the experimental correlation distribution of the differential‐linear distinguisher significantly affects the complexity of quantum attacks, we measure the experimental correlation distributions of Simon32/64 and Simeck32/64. We conduct a quantum differential‐linear key recovery attack on 19‐round Simon32/64. Under the Q1 model, the time complexity of the attack is , the data complexity is , the memory complexity is and the success rate is 60.96%, which achieves the lowest time, memory, and data complexities among all existing 19‐round quantum attacks. In the Q2 model, the time complexity reduces to , with negligible memory complexity. For Simeck32/64, we present a 20‐round quantum key recovery attack under the Q2 model, which is the first quantum key recovery attack on this block cipher.