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

Tatra Mountains Mathematical Publications

Converting of Simon Cipher Multivariate Polynomial Equations to Qubo Problem

Elżbieta Burek

Published Jun 24, 2025• 0 citations
Publisher

Abstract

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.

DOI
10.2478/tmmp-2025-0006

Related papers

Algebraic attacks on block ciphers using quantum annealing

Elżbieta Burek, Michał Wroński, Krzysztof Mańk +1 more

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.

IEEE Transactions on Emerging Topics in Computing•Jan 1, 2022•20 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•1 citation

Solving systems of Boolean multivariate equations with quantum annealing

Sergi Ramos-Calderer, Carlos Bravo-Prieto, Ruge Lin +4 more

Polynomial systems over the binary field have important applications, especially in symmetric and asymmetric cryptanalysis, multivariate-based postquantum cryptography, coding theory, and computer algebra. In this paper, we study the quantum annealing model for solving Boolean systems of multivariate equations of degree 2, usually referred to as the multivariate quadratic problem. We present different methodologies to embed the problem into a Hamiltonian that can be solved by available quantum annealing platforms. In particular, we provide three embedding options, and we highlight their differences in terms of quantum resources. Moreover, we design a machine-agnostic algorithm that adopts an iterative approach to better solve the problem Hamiltonian by repeatedly reducing the search space. Finally, we use D-Wave devices to successfully implement our methodologies on several instances of the multivariate quadratic problem.

arXiv:2111.13224•Physical Review Research•Feb 7, 2022•10 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•10 citations

Automatic Conversion of MiniZinc Programs to QUBO

Wolf, Armin, Cristian Grozea

Obtaining Quadratic Unconstrained Binary Optimisation models for various optimisation problems, in order to solve those on physical quantum computers (such as the the DWave annealers) is nowadays a lengthy and tedious process that requires one to remodel all problem variables as binary variables and squeeze the target function and the constraints into a single quadratic polynomial into these new variables. We report here on the basis of our automatic converter from MiniZinc to QUBO, which is able to process a large set of constraint optimisation and constraint satisfaction problems and turn them into equivalent QUBOs, effectively optimising the whole process.

arXiv:2307.10032•Jul 19, 2023•1 citation

Faster Quantum Algorithms for MQ2 and Applications

Quentin Edme, Pierre-Alain Fouque, André Schrottenloher

We study quantum algorithms for multivariate quadratic Boolean equation systems by focusing on their precise gate count. While better asymptotic algorithms are known, currently gate counts were only computed for exhaustive search (Schwabe and Westerbaan, SPACE 2016) and a variant of Grover's search using preprocessing (Pring, WAIFI 2018). This limits the applicability of Boolean equation solving to cryptanalysis, which considers relatively small numbers of variables (from 40 to 200) and is concerned with the exact complexity of the solver. In this paper, we introduce two new quantum algorithms. The first algorithm is an optimized quantum exhaustive search which amortizes the cost of polynomial evaluation at each quantum search iterate. The second algorithm adapts a method of Bouillaguet et al. (SOSA 2022) which proceeds by linearization of the system. In both cases, we implement the quantum circuits, study their complexity, and obtain significant improvements over previous results. Next, we apply these new algorithms to the cryptanalysis of the block ciphers LowMC and RAIN in the single-data setting. By adapting attacks from Liu et al. (ToSC 2022) and Liu et al. (ToSC 2023) we obtain the first quantum cryptanalysis results on these ciphers.

IACR Communications in Cryptology•Apr 8, 2025•0 citations
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 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.
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.
Polynomial systems over the binary field have important applications, especially in symmetric and asymmetric cryptanalysis, multivariate-based postquantum cryptography, coding theory, and computer algebra. In this paper, we study the quantum annealing model for solving Boolean systems of multivariate equations of degree 2, usually referred to as the multivariate quadratic problem. We present different methodologies to embed the problem into a Hamiltonian that can be solved by available quantum annealing platforms. In particular, we provide three embedding options, and we highlight their differences in terms of quantum resources. Moreover, we design a machine-agnostic algorithm that adopts an iterative approach to better solve the problem Hamiltonian by repeatedly reducing the search space. Finally, we use D-Wave devices to successfully implement our methodologies on several instances of the multivariate quadratic problem.
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.
Obtaining Quadratic Unconstrained Binary Optimisation models for various optimisation problems, in order to solve those on physical quantum computers (such as the the DWave annealers) is nowadays a lengthy and tedious process that requires one to remodel all problem variables as binary variables and squeeze the target function and the constraints into a single quadratic polynomial into these new variables. We report here on the basis of our automatic converter from MiniZinc to QUBO, which is able to process a large set of constraint optimisation and constraint satisfaction problems and turn them into equivalent QUBOs, effectively optimising the whole process.
We study quantum algorithms for multivariate quadratic Boolean equation systems by focusing on their precise gate count. While better asymptotic algorithms are known, currently gate counts were only computed for exhaustive search (Schwabe and Westerbaan, SPACE 2016) and a variant of Grover's search using preprocessing (Pring, WAIFI 2018). This limits the applicability of Boolean equation solving to cryptanalysis, which considers relatively small numbers of variables (from 40 to 200) and is concerned with the exact complexity of the solver. In this paper, we introduce two new quantum algorithms. The first algorithm is an optimized quantum exhaustive search which amortizes the cost of polynomial evaluation at each quantum search iterate. The second algorithm adapts a method of Bouillaguet et al. (SOSA 2022) which proceeds by linearization of the system. In both cases, we implement the quantum circuits, study their complexity, and obtain significant improvements over previous results. Next, we apply these new algorithms to the cryptanalysis of the block ciphers LowMC and RAIN in the single-data setting. By adapting attacks from Liu et al. (ToSC 2022) and Liu et al. (ToSC 2023) we obtain the first quantum cryptanalysis results on these ciphers.