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.Category / Keywords: secret-key cryptography / stream ciphers, block ciphers, algebraic attacks, low-degree equations, annihilators Date: received 5 Aug 2004 Contact author: Armknecht at th informatik uni-mannheim de Available format(s): Postscript (PS) | Compressed Postscript (PS.GZ) | PDF | BibTeX Citation Version: 20040807:043459 (All versions of this report) Discussion forum: Show discussion | Start new discussion