Welcome to the resource topic for 2021/620
Title:
Algebraic attacks on block ciphers using quantum annealing
Authors: Elżbieta Burek, Michał Misztal, 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 AES-128 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 D-Wave Advantage quantum annealing computer. Unfortunately, it is hard to estimate the time this process would require.
ePrint: https://eprint.iacr.org/2021/620
See all topics related to this paper.
Feel free to post resources that are related to this paper below.
Example resources include: implementations, explanation materials, talks, slides, links to previous discussions on other websites.
For more information, see the rules for Resource Topics .