Details:
Title  On exact algebraic [non]immunity of sboxes based on power functions.  Author(s)  Nicolas T. Courtois, Blandine Debraize, Eric Garrido  Type  Book, Chapter in Book, Conference Proceeding  Abstract  In this paper we are interested in algebraic immunity of several well known highlynonlinear vectorial Boolean functions (or Sboxes), designed for block and stream ciphers. Unfortunately, ciphers that use such Sboxes may still be vulnerable to so called “algebraic attacks” proposed recently by Courtois, Pieprzyk, Meier, Armknecht, et al. These attacks are not always feasible in practice but are in general very powerful. They become possible, if we regard the Sboxes, no longer as highlynonlinear functions of their inputs, but rather exhibit (and exploit) much simpler algebraic equations, that involve both input and the output bits. Instead of complex and “explicit” Boolean functions we have then simple and “implicit” algebraic relations that can be combined to fully describe the secret key of the system.
In this paper we look at the number and the type of relations that do exist for several well known components. We wish to correct or/and complete several inexact results on this topic that were presented at FSE 2004.
We also wish to bring a theoretical contribution. One of the main problems in the area of algebraic attacks is to prove that some systems of equations (derived from some more fundamental equations), are still linearly independent. We give a complete proof that the number of linearly independent equations for the Rijndael Sbox (derived from the basic equation XY = 1) is indeed as reported by Courtois and Pieprzyk. It seems that nobody has so far proven this fundamental statement.  Keywords  Boolean functions, Power functions, highly nonlinear functions, Sboxes  ISBN  9783540354581/pbk 
URL 
http://link.springer.com/chapter/10.1007%2F11780656_7 
Language  English  Pages  7686  Publisher  Berlin: Springer  Year  2006  Edition  0  Translation 
No  Refereed 
No 
