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

The Computer Journal

Quantum Guess and Determine Attack on Stream Ciphers

Lin Ding, Zheng Wu, Guixian Zhang, Tairong Shi

Published Dec 8, 2022• 3 citations
Publisher

Abstract

Abstract To guarantee the security of symmetric key schemes against quantum adversary, developing quantum cryptanalytic techniques becomes a major worldwide challenge in the post-quantum world. In this paper, we present a general framework of classical guess and determine attack on stream ciphers, and then convert it into quantum guess and determine attack. It shows that, for a given stream cipher with a key size of $k$ bits and an internal state size of $n$ bits, if a basic guess and determine attack with a time complexity below $O ( {{{2}^{{3k}/{2}}}}/{n} )$ is available, there is a quantum guess and determine attack with multiple data that can recover all $n$ internal state bits of the cipher with complexity below $O ( {{2^{k / 2}}} )$. As applications, we present quantum guess and determine attacks on the SNOW-like stream ciphers. The results show that all of SNOW 1.0 with 128-bit key, SNOW 2.0 with 128-bit key and SOSEMANUK are insecure against quantum guess and determine attack. The resource requirements for implementing a quantum guess and determine attack on SNOW 3G are evaluated as a case study. To the best of our knowledge, this is the first time that the general quantum guess and determine attack is formally proposed and applied to the SNOW-like stream ciphers.

DOI
10.1093/comjnl/bxac174

Related papers

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, 2017•133 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 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.05836•IACR Transactions on Symmetric Cryptology•Dec 1, 2016•27 citations

Black-box security of stream ciphers under the quantum algorithm for linear systems of equations

Cezary Pilaszewicz, Marian Margraf

Abstract In this paper, we analyse the impact of the HHL quantum algorithm on stream ciphers in a black-box setting. We assume a black-box access to an oracle $$M^S$$ M S defining the output of the stream cipher. For a state k encapsulating the key material, the value $$M^S\cdot k$$ M S · k is the keystream $$(k'_1,k'_2,..., k'_N)$$ ( k 1 ′ , k 2 ′ , . . . , k N ′ ) generated by some stream cipher S. We translate this scenario into the quantum setting and describe how the HHL algorithm could be used to attack this construction. Further, we give simple and verifiable criteria under which a black-box attack on stream ciphers with the HHL algorithm is not efficiently feasible. Usually, these criteria follow from already known design principles for symmetric ciphers and should apply to the ciphers used today. We complement the criteria with a simple test, which confirms the resistance of said cipher. Moreover, we use our technique to test the currently used stream ciphers: Trivium, HC-128, and Salsa20.

Discover Computing•Apr 10, 2025•1 citation

(In)security of Stream Ciphers Against Quantum Annealing Attacks on the Example of the Grain 128 and Grain 128a Ciphers

Michał Wroński, Elżbieta Burek, Mateusz Leśniak

The security level of a cipher is a key parameter. While general-purpose quantum computers significantly threaten modern symmetric ciphers, other quantum approaches like quantum annealing have been less concerning. However, this paper argues that a quantum annealer specifically designed to attack Grain 128 and Grain 128a ciphers could soon be technologically feasible. Such an annealer would require 5,751 (6,761) qubits and 77,496 (94,865) couplers, with a qubit connectivity of 225 (245). This work also shows that modern stream ciphers like Grain 128 and Grain 128a may be vulnerable to quantum annealing attacks. Although the exact complexity of quantum annealing is unknown, heuristic estimates suggest that for many problems with$N$variables, a$\sqrt{N}$exponential advantage over simulated annealing may hold. We detail how to transform algebraic attacks on Grain ciphers into the QUBO problem, making our attack potentially more efficient than classical brute-force methods. We demonstrate that applying our attack to rescaled Grain cipher versions, Grain$l$and Grain$la$, overtakes brute-force and Grover’s attacks for sufficiently large$l$, assuming quantum annealing’s exponential benefit over simulated annealing.

IEEE Transactions on Emerging Topics in Computing•Oct 11, 2024•5 citations

Hidden Structures and Quantum Cryptanalysis

Xavier Bonnetain

In this thesis, we study the security of cryptographic systems against an adversary who has access to a quantum computer. In quantum computing, we studied the hidden period and hidden shift problems, which are among the few known problems that have some applications in cryptogaphy and for which the best known quantum algorithm is more than polynomially faster than the best known classical algorithm. We proposed some improvements, new tradeoffs between classical and quantum time and memory, and extended their scope of applications to cases where only a classical oracle is available. In cryptanalysis, in symmetric cryptography, we proposed some attacks against symmetric constructions based on hidden shifts, and generalized many attacks using hidden periods to cases where the construction is only accessible classically. We proposed a quantum cryptanalysis of the different versions of the authenticated cipher AEZ and some quantum versions of multiple slide attacks, which are a classical family of cryptanalyses. This rewriting of attacks in the formalism of hidden periods has allowed us to propose a new classical attack against multiple variants of the cipher MiMC. In asymmetric cryptography, we proposed a concrete and asymptotic quantum security analysis of some isogeny-based key exchanges. Finally, we studied quantum security in some cases where these hidden structure problems do not apply, with in particular the first quantum security analysis of AES, the most used symmetric cipher to date.

•Nov 15, 2019•1 citation
Abstract To guarantee the security of symmetric key schemes against quantum adversary, developing quantum cryptanalytic techniques becomes a major worldwide challenge in the post-quantum world. In this paper, we present a general framework of classical guess and determine attack on stream ciphers, and then convert it into quantum guess and determine attack. It shows that, for a given stream cipher with a key size of kkk bits and an internal state size of nnn bits, if a basic guess and determine attack with a time complexity below O(23k/2/n)O ( {{{2}^{{3k}/{2}}}}/{n} )O(23k/2/n) is available, there is a quantum guess and determine attack with multiple data that can recover all nnn internal state bits of the cipher with complexity below O(2k/2)O ( {{2^{k / 2}}} )O(2k/2). As applications, we present quantum guess and determine attacks on the SNOW-like stream ciphers. The results show that all of SNOW 1.0 with 128-bit key, SNOW 2.0 with 128-bit key and SOSEMANUK are insecure against quantum guess and determine attack. The resource requirements for implementing a quantum guess and determine attack on SNOW 3G are evaluated as a case study. To the best of our knowledge, this is the first time that the general quantum guess and determine attack is formally proposed and applied to the SNOW-like stream ciphers.
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 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.
Abstract In this paper, we analyse the impact of the HHL quantum algorithm on stream ciphers in a black-box setting. We assume a black-box access to an oracle MSM^SMS M S defining the output of the stream cipher. For a state k encapsulating the key material, the value MS⋅kM^S\cdot kMS⋅k M S · k is the keystream (k1′,k2′,...,kN′)(k'_1,k'_2,..., k'_N)(k1′​,k2′​,...,kN′​) ( k 1 ′ , k 2 ′ , . . . , k N ′ ) generated by some stream cipher S. We translate this scenario into the quantum setting and describe how the HHL algorithm could be used to attack this construction. Further, we give simple and verifiable criteria under which a black-box attack on stream ciphers with the HHL algorithm is not efficiently feasible. Usually, these criteria follow from already known design principles for symmetric ciphers and should apply to the ciphers used today. We complement the criteria with a simple test, which confirms the resistance of said cipher. Moreover, we use our technique to test the currently used stream ciphers: Trivium, HC-128, and Salsa20.
The security level of a cipher is a key parameter. While general-purpose quantum computers significantly threaten modern symmetric ciphers, other quantum approaches like quantum annealing have been less concerning. However, this paper argues that a quantum annealer specifically designed to attack Grain 128 and Grain 128a ciphers could soon be technologically feasible. Such an annealer would require 5,751 (6,761) qubits and 77,496 (94,865) couplers, with a qubit connectivity of 225 (245). This work also shows that modern stream ciphers like Grain 128 and Grain 128a may be vulnerable to quantum annealing attacks. Although the exact complexity of quantum annealing is unknown, heuristic estimates suggest that for many problems withNNNvariables, aN\sqrt{N}N​exponential advantage over simulated annealing may hold. We detail how to transform algebraic attacks on Grain ciphers into the QUBO problem, making our attack potentially more efficient than classical brute-force methods. We demonstrate that applying our attack to rescaled Grain cipher versions, Grainllland Grainlalala, overtakes brute-force and Grover’s attacks for sufficiently largelll, assuming quantum annealing’s exponential benefit over simulated annealing.
In this thesis, we study the security of cryptographic systems against an adversary who has access to a quantum computer. In quantum computing, we studied the hidden period and hidden shift problems, which are among the few known problems that have some applications in cryptogaphy and for which the best known quantum algorithm is more than polynomially faster than the best known classical algorithm. We proposed some improvements, new tradeoffs between classical and quantum time and memory, and extended their scope of applications to cases where only a classical oracle is available. In cryptanalysis, in symmetric cryptography, we proposed some attacks against symmetric constructions based on hidden shifts, and generalized many attacks using hidden periods to cases where the construction is only accessible classically. We proposed a quantum cryptanalysis of the different versions of the authenticated cipher AEZ and some quantum versions of multiple slide attacks, which are a classical family of cryptanalyses. This rewriting of attacks in the formalism of hidden periods has allowed us to propose a new classical attack against multiple variants of the cipher MiMC. In asymmetric cryptography, we proposed a concrete and asymptotic quantum security analysis of some isogeny-based key exchanges. Finally, we studied quantum security in some cases where these hidden structure problems do not apply, with in particular the first quantum security analysis of AES, the most used symmetric cipher to date.