Geodesic
On some algorithms for constructing low-degree annihilators for Boolean functions
Diskretnaya Matematika, Tome 18 (2006) no. 3, pp. 138-151.

Voir la notice de l'article provenant de la source Math-Net.Ru

The algebraic method is widely used in analysis of filter generators of pseudo-random sequences. It is based on obtaining low-degree Boolean equations in bits of the initial states of the generator. The problem to obtain such equations reduces to finding low-degree annihilators for the filtering Boolean function. The presence of nonzero low-degree annihilators decreases the complexity of determining the initial state of the generator by means of its output. In this research we deal with the problem to find all low-degree annihilators for a Boolean function defined as a polynomial in several variables. We propose two new algorithms which solve this problem. Their complexities are bounded above by polynomials of the number of variables of the function and of the number of monomials in the polynomial which defines the function. We also consider the application of these algorithms to realising the algebraic method by three known scenarios which yield low-degree equations. 
@article{DM_2006_18_3_a10,
     author = {V. V. Baev},
     title = {On some algorithms for constructing low-degree annihilators for {Boolean} functions},
     journal = {Diskretnaya Matematika},
     pages = {138--151},
     publisher = {mathdoc},
     volume = {18},
     number = {3},
     year = {2006},
     language = {ru},
     url = {http://geodesic.mathdoc.fr/item/DM_2006_18_3_a10/}
}
TY  - JOUR
AU  - V. V. Baev
TI  - On some algorithms for constructing low-degree annihilators for Boolean functions
JO  - Diskretnaya Matematika
PY  - 2006
SP  - 138
EP  - 151
VL  - 18
IS  - 3
PB  - mathdoc
UR  - http://geodesic.mathdoc.fr/item/DM_2006_18_3_a10/
LA  - ru
ID  - DM_2006_18_3_a10
ER  - 
%0 Journal Article
%A V. V. Baev
%T On some algorithms for constructing low-degree annihilators for Boolean functions
%J Diskretnaya Matematika
%D 2006
%P 138-151
%V 18
%N 3
%I mathdoc
%U http://geodesic.mathdoc.fr/item/DM_2006_18_3_a10/
%G ru
%F DM_2006_18_3_a10
V. V. Baev. On some algorithms for constructing low-degree annihilators for Boolean functions. Diskretnaya Matematika, Tome 18 (2006) no. 3, pp. 138-151. http://geodesic.mathdoc.fr/item/DM_2006_18_3_a10/

[1] Courtois N., Meier W., “Algebraic attacks on stream ciphers with linear feedback”, Lecture Notes Computer Sci., 2656, 2003, 345–359 | MR | Zbl

[2] Meier W., Pasalic E., Carlet C., “Algebraic attacks and decomposition of Boolean functions”, Lecture Notes Computer Sci., 3027, 2004, 474–491 | MR | Zbl

[3] Armknecht F., On the existence of low-degree equations for algebraic attacks, http://eprint.iacr.org/2004/185

[4] Mak-Vilyams F., Sloen N., Teoriya kodov, ispravlyayuschikh oshibki, Svyaz, Moskva, 1979

[5] Knut D., Iskusstvo programmirovaniya dlya EVM, {rm t. 3.:} Sortirovka i poisk, Mir, Moskva, 1978

[6] Armknecht F., “Improving fast algebraic attacks”, Lecture Notes Computer Sci., 3017, 2004, 65–82 | Zbl

[7] Courtois N., “Fast algebraic attacks on stream ciphers with linear feedback”, Lecture Notes Computer Sci., 2729, 2003, 177–194 | MR

[8] Courtois N., “Higher order correlation attacks, XL algorithm and cryptanalysis of Toyocrypt”, Lecture Notes Computer Sci., 2587, 2002, 182–199 | MR

[9] Courtois N., Klimov A., Patarin J., Shamir A., “Efficient algorithms for solving overdefined systems of multivariate polynomial equations”, Lecture Notes Computer Sci., 1807, 2000, 392–407 | MR | Zbl

[10] Hawkes P., Rose G., “Rewriting variables: the complexity of fast algebraic attacks on stream ciphers”, Lecture Notes Computer Sci., 3152, 2004, 390–406 | MR | Zbl

[11] Menezes A., van Oorschot P., Vanstone S., Handbook of applied cryptography, CRC Press, Boca Raton, FL, 1996

[12] Mihaljevic M., Imai H., “Cryptanalysis of Toyocrypt-HS1 stream cipher”, IEICE Trans. Fund., E85-A (2002), 66–73

[13] Saarinen M.-J., “A time-memory tradeoff attack against LILI-128”, Lecture Notes Computer Sci., 2365, 2002, 231–236 | Zbl

[14] Simpson L., Dawson E., Golic J., Millan W., “LILI keystream generator”, Lecture Notes Computer Sci., 2012, 2000, 248–261 | MR