Gesellschaft fr Informatik e.V.

Lecture Notes in Informatics


WEWoRC 2005 -Western European Workshop on Research in Cryptology P-74, 13-21 (2005).

Gesellschaft für Informatik, Bonn
2005


Editors

Christopher Wolf, Stefan Lucks, Po-Wah Yau (eds.)


Copyright © Gesellschaft für Informatik, Bonn

Contents

Algebraic attacks and annihilators

Frederik Armknecht

Abstract


Algebraic attacks on block ciphers and stream ciphers have gained more and more attention in cryptography. Their idea is to express a cipher by a system of equations whose solution reveals the secret key. The complexity of an algebraic attack generally increases with the degree of the equations. Hence, low-degree equations are crucial for the efficiency of algebraic attacks. In the case of simple combiners over $GF(2)$, it was proved in [9] that the existence of low-degree equations is equivalent to the existence of low-degree annihilators, and the term ”algebraic immunity” was introduced. This result was extended to general finite fields GF (q) in [4]. In this paper, which improves parts of the unpublished eprint paper [2], we present a generalized framework which additionally covers combiners with memory and S- Boxes over GF (q). In all three cases, the existence of low-degree equations can be reduced to the existence of certain annihilators. This might serve as a starting point for further research.


Full Text: PDF

Gesellschaft für Informatik, Bonn
ISBN 3-88579-403-9


Last changed 24.01.2012 21:52:36