paper
title
Efficient Computation of Algebraic Immunity for Algebraic and Fast Algebraic Attacks.
authors
Frederik Armknecht, Claude Carlet, Philippe Gaborit, Simon Künzli, Willi Meier, and Olivier Ruatta.
publication
In S. Vaudenay, editor, Advances in Cryptology - EUROCRYPT 2006, 25th Annual International Conference on the Theory and Applications of Cryptographic Techniques, St. Petersburg, Russia, May 28 - June 1, 2006. Proceedings, volume 4004 of Lecture Notes in Computer Science, pages 147-164. Springer-Verlag, 2006.
abstract
In this paper we propose several efficient algorithms for assessing the resistance of Boolean functions against algebraic and fast algebraic attacks when implemented in LFSR-based stream ciphers. An algorithm is described which permits to compute the algebraic immunity d of a Boolean function with n variables in O(D^2) operations, for D \approx \binom{n}{d}, rather than in O(D^3) operations necessary in all previous algorithms. Our algorithm is based on multivariate polynomial interpolation. For assessing the vulnerability of arbitrary Boolean functions with respect to fast algebraic attacks, an efficient generic algorithm is presented that is not based on interpolation. This algorithm is demonstrated to be particularly efficient for symmetric Boolean functions. As an application it is shown that large classes of symmetric functions are very vulnerable to fast algebraic attacks despite their proven resistance against conventional algebraic attacks.
external links
[Eurocrypt 2006], [Homepage F. Armknecht], [Homepage N. Courois]