Algebraic Attacks and Annihilators
Frederik Armknecht · MADOC (University of Mannheim) · 2005
Algebraic attacks on block ciphers and stream ciphers have gained more and more attention in cryptography .T heir idea is to express ac ipher by as ystem of equations whose solution reveals the secret key. The complexity of an attack generally increases with the degree of the equations. Hence, low-degree equations are crucial for the efficienc yo fa lgebraic attacks. In the case of simple combiners ove rG F(2), it wa sp rove di n( 9) that the existence of low-degree equations is equivalent to the existence of low-degree annihilators, and the term algebraic immunity wa si ntroduced. This result wa se xtended to general finit efi elds GF ( q ) in (4). In thi sp aper ,w hich improve sp arts of the unpublished eprint paper (2), we present ag eneralized framework which additionally covers combiners with memory and S- Boxes ove r GF ( q ) .I na ll three cases, the existence of low-degree equations can be reduce dt ot he existence of certain annihilators. This might serv ea sas tarting point for further research.