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

IEEE Transactions on Emerging Topics in Computing

Algebraic attacks on block ciphers using quantum annealing

Elżbieta Burek, Michał Wroński, Krzysztof Mańk, Michał Misztal

Published Jan 1, 2022• 18 citations
Publisher

Abstract

This paper presents the transformation method of the system of algebraic equations describing the symmetric cipher into the QUBO problem. After transformation of given equations$f_0, f_1, \ldots, f_{n-1}$f0,f1,...,fn-1to equations over integers$f^{\prime }_0, f^{\prime }_1, \ldots, f^{\prime }_{n-1}$f0',f1',...,fn-1', one can linearize each, obtaining$f^{\prime }_{lin_i}=lin(f^{\prime }_i)$flini'=lin(fi'), for$i=\overline{0, n-1}$i=0,n-1¯, where$lin$lindenotes linearization operation. Finally, one can obtain problem in the QUBO form as$(f^{\prime }_{lin_0} )^2+\cdots +(f^{\prime }_{lin_{n-1}} )^2+Pen-C$(flin0')2+⋯+(flinn-1')2+Pen-C, where$Pen$Pendenotes penalties obtained during linearization of equations,$n$nis the number of equations and$C$Cis constant appearing in the polynomial$(f^{\prime }_{lin_0} )^2+\cdots +(f^{\prime }_{lin_{n-1}} )^2+Pen$(flin0')2+⋯+(flinn-1')2+Pen. This paper presents the transformation method of SPN block ciphers to the QUBO problem. What is more, we present the results of the transformation of the complete AES-128 cipher to the QUBO problem, where the number of variables of the equivalent QUBO problem equals approximately 30,026. It is worth noting that AES-128 is much easier to solve using quantum annealing than the factorization problem and the discrete logarithm problem of a similar level of security. For example, factorizing a 3072 bit long RSA integer using quantum annealing requires a QUBO problem of about 2,360,000 variables.

DOI
10.1109/tetc.2022.3143152

Related papers

Converting of Simon Cipher Multivariate Polynomial Equations to Qubo Problem

Elżbieta Burek

Abstract The use of quantum annealing in the cryptanalysis of symmetric cryptography is a new idea based on the concept of algebraic attacks. This paper shows how to describe the Simon cipher as a system of multivariate polynomial equations so that the obtained optimization problem in the form of QUBO consistsof assmall number of binary variables aspossible. According to our calculations, the use of quantum annealing to an algebraic attack on the Simon128 / 128 cipher, since the QUBO problem consists of 27, 270 binary variables, is more effective than the same attack on the AES128 cipher, for which the QUBO problem includes 29, 770 binary variables.

Tatra Mountains Mathematical Publications•Jun 24, 2025•0 citations

Applications of Quantum Annealing in Cryptography

Anpeng Zhang, Xiutao Feng

This paper presents a new method to reduce the optimization of a pseudo-Boolean function to QUBO problem which can be solved by quantum annealer. The new method has two aspects, one is coefficient optimization and the other is variable optimization. The former is an improvement on the existing algorithm in a special case. The latter is realized by means of the maximal independent point set in graph theory. We apply this new method in integer factorization on quantum annealers and achieve the largest integer factorization (4137131) with 93 variables, the range of coefficients is [-1024,1024] which is much smaller than the previous results. We also focus on the quantum attacks on block ciphers and present an efficient method with smaller coefficients to transform Boolean equation systems into QUBO problems.

arXiv:2211.10076•Nov 18, 2022•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

Transformation of the discrete logarithm problem over F2n to the QUBO problem using normal bases

Michał Wroński, Mateusz Leśniak

Quantum computations are very important branch of modern cryptology. According to the number of working physical qubits available in general-purpose quantum computers and in quantum annealers, there is no coincidence, that nowadays quantum annealers allow to solve larger problems. In this paper we focus on solving discrete logarithm problem (DLP) over binary fields using quantum annealing. It is worth to note, that however solving DLP over prime fields using quantum annealing has been considered before, no author, until now, has considered DLP over binary fields using quantum annealing. Therefore, in this paper, we aim to bridge this gap. We present a polynomial transformation of the discrete logarithm problem over binary fields to the Quadratic Unconstrained Binary Optimization (QUBO) problem, using approximately 3n2 logical variables for the binary field F2n. In our estimations, we assume the existence of an optimal normal base in the given fields. Such a QUBO instance can then be solved using quantum annealing.

International Journal of Electronics and Telecommunications•Apr 7, 2025•0 citations

A compact QUBO encoding of computational logic formulae demonstrated on cryptography constructions

Gregory Morse, Tamás Kozsik, Oskar Mencer +1 more

We aim to advance the state-of-the-art in Quadratic Unconstrained Binary Optimization formulation with a focus on cryptography algorithms. As the minimal QUBO encoding of the linear constraints of optimization problems emerges as the solution of integer linear programming (ILP) problems, by solving special boolean logic formulas (like ANF and DNF) for their integer coefficients it is straightforward to handle any normal form, or any substitution for multi-input AND, OR or XOR operations in a QUBO form. To showcase the efficiency of the proposed approach we considered the most widespread cryptography algorithms including AES-128/192/256, MD5, SHA1 and SHA256. For each of these, we achieved QUBO instances reduced by thousands of logical variables compared to previously published results, while keeping the QUBO matrix sparse and the magnitude of the coefficients low. In the particular case of AES-256 cryptography function we obtained more than 8x reduction in variable count compared to previous results. The demonstrated reduction in QUBO sizes notably increases the vulnerability of cryptography algorithms against future quantum annealers, capable of embedding around $30$ thousands of logical variables.

arXiv:2409.07501•Sep 10, 2024•0 citations

Transformation of the discrete logarithm problem over $\mathbb F_{2^n}$ to the QUBO problem using normal bases

Michał Wroński, Mateusz Leśniak

Quantum computations are very important branch of modern cryptology. According to the number of working physical qubits available in general-purpose quantum computers and in quantum annealers, there is no coincidence, that nowadays quantum annealers allow to solve larger problems. In this paper we focus on solving discrete logarithm problem (DLP) over binary fields using quantum annealing. It is worth to note, that however solving DLP over prime fields using quantum annealing has been considered before, no author, until now, has considered DLP over binary fields using quantum annealing. Therefore, in this paper, we aim to bridge this gap. We present a polynomial transformation of the discrete logarithm problem over binary fields to the Quadratic Unconstrained Binary Optimization (QUBO) problem, using approximately $3n^2$ logical variables for the binary field $\mathbb{F}_{2^n}$. In our estimations, we assume the existence of an optimal normal base of II type in the given fields. Such a QUBO instance can then be solved using quantum annealing.

arXiv:2409.18534•Sep 27, 2024•0 citations
This paper presents the transformation method of the system of algebraic equations describing the symmetric cipher into the QUBO problem. After transformation of given equationsf0,f1,…,fn−1f_0, f_1, \ldots, f_{n-1}f0​,f1​,…,fn−1​f0,f1,...,fn-1to equations over integersf0′,f1′,…,fn−1′f^{\prime }_0, f^{\prime }_1, \ldots, f^{\prime }_{n-1}f0′​,f1′​,…,fn−1′​f0',f1',...,fn-1', one can linearize each, obtainingflini′=lin(fi′)f^{\prime }_{lin_i}=lin(f^{\prime }_i)flini​′​=lin(fi′​)flini'=lin(fi'), fori=0,n−1‾i=\overline{0, n-1}i=0,n−1​i=0,n-1¯, wherelinlinlinlindenotes linearization operation. Finally, one can obtain problem in the QUBO form as(flin0′)2+⋯+(flinn−1′)2+Pen−C(f^{\prime }_{lin_0} )^2+\cdots +(f^{\prime }_{lin_{n-1}} )^2+Pen-C(flin0​′​)2+⋯+(flinn−1​′​)2+Pen−C(flin0')2+⋯+(flinn-1')2+Pen-C, wherePenPenPenPendenotes penalties obtained during linearization of equations,nnnnis the number of equations andCCCCis constant appearing in the polynomial(flin0′)2+⋯+(flinn−1′)2+Pen(f^{\prime }_{lin_0} )^2+\cdots +(f^{\prime }_{lin_{n-1}} )^2+Pen(flin0​′​)2+⋯+(flinn−1​′​)2+Pen(flin0')2+⋯+(flinn-1')2+Pen. This paper presents the transformation method of SPN block ciphers to the QUBO problem. What is more, we present the results of the transformation of the complete AES-128 cipher to the QUBO problem, where the number of variables of the equivalent QUBO problem equals approximately 30,026. It is worth noting that AES-128 is much easier to solve using quantum annealing than the factorization problem and the discrete logarithm problem of a similar level of security. For example, factorizing a 3072 bit long RSA integer using quantum annealing requires a QUBO problem of about 2,360,000 variables.
Abstract The use of quantum annealing in the cryptanalysis of symmetric cryptography is a new idea based on the concept of algebraic attacks. This paper shows how to describe the Simon cipher as a system of multivariate polynomial equations so that the obtained optimization problem in the form of QUBO consistsof assmall number of binary variables aspossible. According to our calculations, the use of quantum annealing to an algebraic attack on the Simon128 / 128 cipher, since the QUBO problem consists of 27, 270 binary variables, is more effective than the same attack on the AES128 cipher, for which the QUBO problem includes 29, 770 binary variables.
This paper presents a new method to reduce the optimization of a pseudo-Boolean function to QUBO problem which can be solved by quantum annealer. The new method has two aspects, one is coefficient optimization and the other is variable optimization. The former is an improvement on the existing algorithm in a special case. The latter is realized by means of the maximal independent point set in graph theory. We apply this new method in integer factorization on quantum annealers and achieve the largest integer factorization (4137131) with 93 variables, the range of coefficients is [-1024,1024] which is much smaller than the previous results. We also focus on the quantum attacks on block ciphers and present an efficient method with smaller coefficients to transform Boolean equation systems into QUBO problems.
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 computations are very important branch of modern cryptology. According to the number of working physical qubits available in general-purpose quantum computers and in quantum annealers, there is no coincidence, that nowadays quantum annealers allow to solve larger problems. In this paper we focus on solving discrete logarithm problem (DLP) over binary fields using quantum annealing. It is worth to note, that however solving DLP over prime fields using quantum annealing has been considered before, no author, until now, has considered DLP over binary fields using quantum annealing. Therefore, in this paper, we aim to bridge this gap. We present a polynomial transformation of the discrete logarithm problem over binary fields to the Quadratic Unconstrained Binary Optimization (QUBO) problem, using approximately 3n2 logical variables for the binary field F2n. In our estimations, we assume the existence of an optimal normal base in the given fields. Such a QUBO instance can then be solved using quantum annealing.
We aim to advance the state-of-the-art in Quadratic Unconstrained Binary Optimization formulation with a focus on cryptography algorithms. As the minimal QUBO encoding of the linear constraints of optimization problems emerges as the solution of integer linear programming (ILP) problems, by solving special boolean logic formulas (like ANF and DNF) for their integer coefficients it is straightforward to handle any normal form, or any substitution for multi-input AND, OR or XOR operations in a QUBO form. To showcase the efficiency of the proposed approach we considered the most widespread cryptography algorithms including AES-128/192/256, MD5, SHA1 and SHA256. For each of these, we achieved QUBO instances reduced by thousands of logical variables compared to previously published results, while keeping the QUBO matrix sparse and the magnitude of the coefficients low. In the particular case of AES-256 cryptography function we obtained more than 8x reduction in variable count compared to previous results. The demonstrated reduction in QUBO sizes notably increases the vulnerability of cryptography algorithms against future quantum annealers, capable of embedding around 303030 thousands of logical variables.
Transformation of the discrete logarithm problem over F2n\mathbb F_{2^n}F2n​ to the QUBO problem using normal bases
Quantum computations are very important branch of modern cryptology. According to the number of working physical qubits available in general-purpose quantum computers and in quantum annealers, there is no coincidence, that nowadays quantum annealers allow to solve larger problems. In this paper we focus on solving discrete logarithm problem (DLP) over binary fields using quantum annealing. It is worth to note, that however solving DLP over prime fields using quantum annealing has been considered before, no author, until now, has considered DLP over binary fields using quantum annealing. Therefore, in this paper, we aim to bridge this gap. We present a polynomial transformation of the discrete logarithm problem over binary fields to the Quadratic Unconstrained Binary Optimization (QUBO) problem, using approximately 3n23n^23n2 logical variables for the binary field F2n\mathbb{F}_{2^n}F2n​. In our estimations, we assume the existence of an optimal normal base of II type in the given fields. Such a QUBO instance can then be solved using quantum annealing.