On the Existence of low-degree Equations for Algebraic Attacks

Frederik Armknecht

Paper 2004/185

On the Existence of low-degree Equations for Algebraic Attacks

Frederik Armknecht

Abstract

Algebraic attacks on block ciphers and stream ciphers have gained more and more attention in cryptography. The idea is to express a cipher by a system of equations whose solution reveals the secret key. The complexity of an algebraic attack is closely related to the degree of the equations. Hence, low-degree equations are crucial for algebraic attacks. So far, the existence of low-degree equations for simple combiners, combiners with memory and S-boxes was treated independently. In this paper, we unify these approaches by reducing them to the same problem: finding low-degree annihilators. This enables a systematic treatment and implies a general criterion for the existence of low-degree equations. The unification allows to extend former results to all three cases. Therefore, we repeat an algorithm for finding a generating set of all low-degree equations. Additionally, we introduce a new improved version, adapted to specific keystream generators (e.g., for the Bluetooth keystream generator). Finally, we describe for certain cases an upper and a lower bound for the lowest possible degree. To the best of our knowledge, the upper bound has only been presented in the context of keystream generators before and the lower bound was not published previously.

Metadata

Available format(s): PDF PS
Category: Secret-key cryptography
Publication info: Published elsewhere. Unknown where it was published
Keywords: stream ciphers block ciphers algebraic attacks low-degree equations annihilators
Contact author(s): Armknecht @ th informatik uni-mannheim de
History: 2004-08-07: received
Short URL: https://ia.cr/2004/185
License: CC BY

BibTeX

@misc{cryptoeprint:2004/185,
      author = {Frederik Armknecht},
      title = {On the Existence of low-degree Equations for Algebraic Attacks},
      howpublished = {Cryptology ePrint Archive, Paper 2004/185},
      year = {2004},
      note = {\url{https://eprint.iacr.org/2004/185}},
      url = {https://eprint.iacr.org/2004/185}
}