Paper 2017/1027

Eliminating Variables in Boolean Equation Systems

Bjørn Møller Greve, Håvard Raddum, Gunnar Fløystad, and Øyvind Ytrehus

Abstract

Systems of Boolean equations of low degree arise in a natural way when analyzing block ciphers. The cipher's round functions relate the secret key to auxiliary variables that are introduced by each successive round. In algebraic cryptanalysis, the attacker attempts to solve the resulting equation system in order to extract the secret key. In this paper we study algorithms for eliminating the auxiliary variables from these systems of Boolean equations. It is known that elimination of variables in general increases the degree of the equations involved. In order to contain computational complexity and storage complexity, we present two new algorithms for performing elimination while bounding the degree at 3, which is the lowest possible for elimination. Further we show that the new algorithms are related to the well known XL algorithm. We apply the algorithms to a downscaled version of the LowMC cipher and to a toy cipher based on the Prince cipher, and report on experimental results pertaining to these examples.

Metadata
Available format(s)
PDF
Category
Foundations
Publication info
Preprint.
Contact author(s)
haavardr @ simula no
History
2017-10-25: received
Short URL
https://ia.cr/2017/1027
License
Creative Commons Attribution
CC BY

BibTeX

@misc{cryptoeprint:2017/1027,
      author = {Bjørn Møller Greve and Håvard Raddum and Gunnar Fløystad and Øyvind Ytrehus},
      title = {Eliminating Variables in Boolean Equation Systems},
      howpublished = {Cryptology ePrint Archive, Paper 2017/1027},
      year = {2017},
      note = {\url{https://eprint.iacr.org/2017/1027}},
      url = {https://eprint.iacr.org/2017/1027}
}
Note: In order to protect the privacy of readers, eprint.iacr.org does not use cookies or embedded third party content.