Computing the Algebraic Immunity Efficiently

The purpose of algebraic attacks on stream and block ciphers is to recover the secret key by solving an overdefined system of multivariate algebraic equations. They become very efficient if this system is of low degree. In particular, they have been used to break stream ciphers immune to all previously known attacks. This kind of attack tends to work when certain Boolean functions used in the ciphering process have either low degree annihilators or low degree multiples. It is therefore important to be able to check this criterion for Boolean functions. We provide in this article an algorithm of complexity 0 (m d ) (for fixed d) which is able to prove that a given Boolean function in m variables has no annihilator nor multiple of degree less than or equal to d. This complexity is essentially optimal. We also provide a more practical algorithm for the same task, which we believe to have the same complexity. This last algorithm is also able to output a basis of annihilators or multiples when they exist.