Algebraic attacks on block ciphers using quantum annealing

Elżbieta Burek; Michał Misztal; Michał Wroński

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 to equations over integers , one has to linearize each, obtaining , where denotes linearization operation. Finally, one can obtain problem in the QUBO form as , where denotes penalties obtained during linearization of equations and 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 , 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.

Metadata

Available format(s): PDF
Category: Secret-key cryptography
Publication info: Preprint. MINOR revision.
Keywords: Cryptanalysis AES symmetric ciphers algebraic attacks quantum annealing
Contact author(s): elzbieta burek @ wat edu pl
michal misztal @ wat edu pl
michal wronski @ wat edu pl
History: 2021-05-17: 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}
}