Challenges
Datasets
Workspaces
Papers
Discussions
Leaderboard
Log inSign up
Challenges
Datasets
Workspaces
Papers
Discussions
Leaderboard
Blog
Job Board
Q3AS

© 2026 Aqora Quantum S.A.S.

TermsPrivacyLegal Notice

arXiv:1812.08499

Quantum Miss-in-the-Middle Attack

Huiqin Xie, Li Yang

Published Dec 20, 2018• 1 citation
arXivHTMLPDF

Abstract

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.

DOI
10.48550/arxiv.1812.08499

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.

Mathematics•Aug 22, 2024•0 citations

A Quantum Automatic Tool for Finding Impossible Differentials

Huiqin Xie, Qiqing Xia, Wang, Ke +2 more

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.

arXiv:2407.10056•Jul 14, 2024•0 citations

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.06997•Dec 18, 2017•4 citations

Classical and Quantum based Differential Cryptanalysis Methods

Priyanka Jojan, Kapil Kumar Soni, Akhtar Rasool

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.

International Conference on Computing, Communication and Networking Technologies (ICCCNT)•Jul 6, 2021•5 citations

Quantum differential cryptanalysis based on Bernstein-Vazirani algorithm

Rong-Xue Xu, Hongwei Sun, Kejia Zhang +2 more

Abstract Recent research has demonstrated the potential of quantum algorithms to exploit vulnerabilities in various popular constructions, such as certain block ciphers like Feistel, Even-Mansour, and multiple MACs, within the superposition query model. In this study, we delve into the security of block ciphers against quantum threats, particularly investigating their susceptibility to cryptanalysis techniques, notably exploring quantum adaptations of differential cryptanalysis. Initially, we introduce a BV-based quantum algorithm for identifying linear structures with a complexity of $O(n)$ O ( n ) , where n denotes the number of bits in the function. Subsequently, we illustrate the application of this algorithm in devising quantum differential cryptanalysis techniques, including quantum differential cryptanalysis, quantum small probability differential cryptanalysis, and quantum impossible differential cryptanalysis, demonstrating polynomial acceleration compared to prior approaches. By treating the encryption function as a unified entity, our algorithm circumvents the traditional challenge of extending differential paths in differential cryptanalysis.

EPJ Quantum Technology•Dec 1, 2024•6 citations

A practical-quantum differential attack on block ciphers

Tarun Yadav, Manoj Kumar, Amit Kumar +1 more

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.

Cryptography and Communications•Jul 1, 2023•11 citations
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.
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.
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.
Abstract Recent research has demonstrated the potential of quantum algorithms to exploit vulnerabilities in various popular constructions, such as certain block ciphers like Feistel, Even-Mansour, and multiple MACs, within the superposition query model. In this study, we delve into the security of block ciphers against quantum threats, particularly investigating their susceptibility to cryptanalysis techniques, notably exploring quantum adaptations of differential cryptanalysis. Initially, we introduce a BV-based quantum algorithm for identifying linear structures with a complexity of O(n)O(n)O(n) O ( n ) , where n denotes the number of bits in the function. Subsequently, we illustrate the application of this algorithm in devising quantum differential cryptanalysis techniques, including quantum differential cryptanalysis, quantum small probability differential cryptanalysis, and quantum impossible differential cryptanalysis, demonstrating polynomial acceleration compared to prior approaches. By treating the encryption function as a unified entity, our algorithm circumvents the traditional challenge of extending differential paths in differential cryptanalysis.
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.