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

Discover Computing

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

Cezary Pilaszewicz, Marian Margraf

Published Apr 10, 2025• 1 citation
Publisher

Abstract

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.

DOI
10.1007/s10791-025-09530-4

Related papers

A black-box attack on fixed-unitary quantum encryption schemes

Cezary Pilaszewicz, Lea R. Muth, Marian Margraf

Abstract We show how fixed-unitary quantum encryption schemes can be attacked in a black-box setting. We use an efficient technique to invert a unitary transformation on a quantum computer to retrieve an encrypted secret quantum state $${|{\psi }\rangle }$$ | ψ ⟩ . This attack has a success rate of 100% and can be executed in constant time. We name a vulnerable scheme which security is fully broken by our attack and suggest how to improve the scheme to invalidate this attack. The proposed attack highlights the importance of carefully designing quantum encryption schemes to ensure their security against quantum adversaries, even in a black-box setting. We point to the faulty assumption and name a criterion for future quantum cipher design to prevent similar vulnerabilities.

Discover Computing•Jun 22, 2024•2 citations

Quantum Guess and Determine Attack on Stream Ciphers

Lin Ding, Zheng Wu, Guixian Zhang +1 more

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.

The Computer Journal•Dec 8, 2022•3 citations

Quantum security of AES-128 under HHL algorithm

Juntao Gao, Hao Li, Baocang Wang +1 more

There have been a lot of researches about algebric analysis of AES. In this paper, we turned to quantum algorithm to analyze security of AES-128 against the modified HHL algorithm, which is a quantum algorithm used to get classical solutions of multivariate equation system. We constructed two types of equation systems of AES, and solved them with several variants of HHL algorithms respectively. The resulting complexities involved the condition number are given. We analyzed the reasons for the different complexity of the two equation systems and their solution methods, and pointed out that the combination of the boolean equation system and (the improved) BoolSol is more threatening to AES. With a lower bound on the condition number presented by Ding et al., we show that, for AES-128, HHL algorithm is difficult to achieve better attack effect than Grover algorithm. Our results have some enlightening significance for analyzing the post-quantum security of AES-like block ciphers.

Quantum Information and Computation•Feb 1, 2022•1 citation

Quantum Paths to Cryptanalysis

Cezary Pilaszewicz

Quantum computers offer a novel approach to data processing, which poses both opportunities and threats for modern cryptography. While Shor’s algorithm for prime factorisation demonstrated the possible impact of quantum cryptanalysis, the complete quantum significance in the cryptanalytical context still needs further research. This thesis compiles a series of recent publications, each of which examines a distinct application of quantum advantage in cryptography. Collectively, these contributions constitute a non-exhaustive compendium of recent advancements in quantum cryptanalysis. We first examine applications of the Harrow-Hassidim-Lloyd (HHL) algorithm for solving linear equation systems. We propose two approaches in which the quantum advantage of the HHL algorithm could be leveraged to investigate structural properties relevant to symmetric cryptanalysis. In the subsequent chapter, an analysis is conducted on the significance of adiabatic quantum computing and its role in the cryptanalytical setting. Together, these results offer novel insights into the capabilities and limitations of quantum-enhanced cryptanalysis of symmetric ciphers. Turning to asymmetric settings, two quantum attacks are proposed that result in the complete break of the underlying ciphers. The first one exploits the recipient’s encryption process to extract the secret key used in the Quantum Encryption Method. The second targets an Identity-Based Encryption scheme whose security relies on isogenies. We demonstrate that the distinct use of isogenies introduces new attack vectors for both classical and quantum adversaries. Collectively, these contributions deepen the understanding of quantum-enhanced cryptanalysis, thereby clarifying both its potential and current boundaries.

•Jan 1, 2025•0 citations

(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

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
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.
Abstract We show how fixed-unitary quantum encryption schemes can be attacked in a black-box setting. We use an efficient technique to invert a unitary transformation on a quantum computer to retrieve an encrypted secret quantum state ∣ψ⟩{|{\psi }\rangle }∣ψ⟩ | ψ ⟩ . This attack has a success rate of 100% and can be executed in constant time. We name a vulnerable scheme which security is fully broken by our attack and suggest how to improve the scheme to invalidate this attack. The proposed attack highlights the importance of carefully designing quantum encryption schemes to ensure their security against quantum adversaries, even in a black-box setting. We point to the faulty assumption and name a criterion for future quantum cipher design to prevent similar vulnerabilities.
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.
There have been a lot of researches about algebric analysis of AES. In this paper, we turned to quantum algorithm to analyze security of AES-128 against the modified HHL algorithm, which is a quantum algorithm used to get classical solutions of multivariate equation system. We constructed two types of equation systems of AES, and solved them with several variants of HHL algorithms respectively. The resulting complexities involved the condition number are given. We analyzed the reasons for the different complexity of the two equation systems and their solution methods, and pointed out that the combination of the boolean equation system and (the improved) BoolSol is more threatening to AES. With a lower bound on the condition number presented by Ding et al., we show that, for AES-128, HHL algorithm is difficult to achieve better attack effect than Grover algorithm. Our results have some enlightening significance for analyzing the post-quantum security of AES-like block ciphers.
Quantum computers offer a novel approach to data processing, which poses both opportunities and threats for modern cryptography. While Shor’s algorithm for prime factorisation demonstrated the possible impact of quantum cryptanalysis, the complete quantum significance in the cryptanalytical context still needs further research. This thesis compiles a series of recent publications, each of which examines a distinct application of quantum advantage in cryptography. Collectively, these contributions constitute a non-exhaustive compendium of recent advancements in quantum cryptanalysis. We first examine applications of the Harrow-Hassidim-Lloyd (HHL) algorithm for solving linear equation systems. We propose two approaches in which the quantum advantage of the HHL algorithm could be leveraged to investigate structural properties relevant to symmetric cryptanalysis. In the subsequent chapter, an analysis is conducted on the significance of adiabatic quantum computing and its role in the cryptanalytical setting. Together, these results offer novel insights into the capabilities and limitations of quantum-enhanced cryptanalysis of symmetric ciphers. Turning to asymmetric settings, two quantum attacks are proposed that result in the complete break of the underlying ciphers. The first one exploits the recipient’s encryption process to extract the secret key used in the Quantum Encryption Method. The second targets an Identity-Based Encryption scheme whose security relies on isogenies. We demonstrate that the distinct use of isogenies introduces new attack vectors for both classical and quantum adversaries. Collectively, these contributions deepen the understanding of quantum-enhanced cryptanalysis, thereby clarifying both its potential and current boundaries.
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.
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.