Paper 2021/620
Algebraic attacks on block ciphers using quantum annealing
Elżbieta Burek, Michał Misztal, and Michał Wroński
Abstract
This paper presents method for transformation of algebraic equations of symmetric cipher into the QUBO problem. After transformation of given equations $f_1, f_2, \dots, f_n$ to equations over integers $f'_1, f'_2, \dots, f'_n$, one has to linearize each, obtaining $f'_{lin_i}=lin(f'_i)$, where $lin$ denotes linearization operation. Finally, one can obtain problem in the QUBO form as $\left( f'_{lin_1} \right)^2+\dots+\left( f'_{lin_n} \right)^2+Pen$, where $Pen$ denotes penalties obtained during linearization of equations and $n$ is the number of equations. In this paper, we show examples of the transformation of some block ciphers to the QUBO problem. What is more, we present the results of the transformation of the full AES128 cipher to the QUBO problem, where the number of variables of equivalent QUBO problem is equal to $237,915$, which means, at least theoretically, that problem may be solved using the DWave Advantage quantum annealing computer. Unfortunately, it is hard to estimate the time this process would require.
Metadata
 Available format(s)
 Category
 Secretkey cryptography
 Publication info
 Preprint. MINOR revision.
 Keywords
 CryptanalysisAESsymmetric ciphersalgebraic attacksquantum annealing
 Contact author(s)

elzbieta burek @ wat edu pl
michal misztal @ wat edu pl
michal wronski @ wat edu pl  History
 20210517: received
 Short URL
 https://ia.cr/2021/620
 License

CC BY
BibTeX
@misc{cryptoeprint:2021/620, author = {Elżbieta Burek and Michał Misztal and Michał Wroński}, title = {Algebraic attacks on block ciphers using quantum annealing}, howpublished = {Cryptology {ePrint} Archive, Paper 2021/620}, year = {2021}, url = {https://eprint.iacr.org/2021/620} }