Algebraic attacks on block ciphers using quantum annealing
Elżbieta Burek, Michał Wroński, Krzysztof Mańk, Michał Misztal · IEEE Transactions on Emerging Topics in Computing · 2022
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.