Algebraic attacks and annihilators
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  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 . In this paper, which improves parts of the unpublished eprint paper , 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