Geodesic
An enhanced algorithm to search for low-degree annihilators for a~Zhegalkin polynomial
Diskretnaya Matematika, Tome 19 (2007) no. 4, pp. 132-138.

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

A Boolean function $g$ is said to be an annihilator of a Boolean function $f$ if $fg=0$. In some problems concerning finite automata, it is required to find non-zero annihilators of low algebraic degree for a function $f$. In this paper we suggest Algorithm M2 which, given the Zhegalkin polynomial for a function $f$, yields a basis of the space of its annihilators of degree not exceeding $d$. Algorithm M2 is an enhancement of a previously known algorithm and allows in a series of cases to decrease calculations. The total complexity of Algorithm M2 is the same as for the previous algorithm. 
@article{DM_2007_19_4_a8,
     author = {V. V. Baev},
     title = {An enhanced algorithm to search for low-degree annihilators for {a~Zhegalkin} polynomial},
     journal = {Diskretnaya Matematika},
     pages = {132--138},
     publisher = {mathdoc},
     volume = {19},
     number = {4},
     year = {2007},
     language = {ru},
     url = {http://geodesic.mathdoc.fr/item/DM_2007_19_4_a8/}
}
TY  - JOUR
AU  - V. V. Baev
TI  - An enhanced algorithm to search for low-degree annihilators for a~Zhegalkin polynomial
JO  - Diskretnaya Matematika
PY  - 2007
SP  - 132
EP  - 138
VL  - 19
IS  - 4
PB  - mathdoc
UR  - http://geodesic.mathdoc.fr/item/DM_2007_19_4_a8/
LA  - ru
ID  - DM_2007_19_4_a8
ER  - 
%0 Journal Article
%A V. V. Baev
%T An enhanced algorithm to search for low-degree annihilators for a~Zhegalkin polynomial
%J Diskretnaya Matematika
%D 2007
%P 132-138
%V 19
%N 4
%I mathdoc
%U http://geodesic.mathdoc.fr/item/DM_2007_19_4_a8/
%G ru
%F DM_2007_19_4_a8
V. V. Baev. An enhanced algorithm to search for low-degree annihilators for a~Zhegalkin polynomial. Diskretnaya Matematika, Tome 19 (2007) no. 4, pp. 132-138. http://geodesic.mathdoc.fr/item/DM_2007_19_4_a8/

[1] Alferov A. P., Zubov A. Yu., Kuzmin A. S., Cheremushkin A. V., Osnovy kriptografii, Gelios, Moskva, 2001

[2] Baev V. V., “O slozhnosti poiska annigilyatorov nizkoi stepeni dlya bulevykh funktsii”, Materialy Mezhdunarodnoi nauchnoi konferentsii po problemam bezopasnosti i protivodeistviyu terrorizmu, MTsNMO, Moskva, 2006, 198–204

[3] Baev V. V., “Nekotorye nizhnie otsenki na algebraicheskuyu immunnost funktsii, zadannykh svoimi treis-formami”, Trudy VII Mezhdunarodnoi konferentsii “Diskretnye modeli v teorii upravlyayuschikh sistem”, MAKS, Moskva, 2006, 25–29

[4] Baev V. V., “O nekotorykh algoritmakh postroeniya annigilyatorov nizkoi stepeni dlya bulevykh funktsii”, Diskretnaya matematika, 18:3 (2006), 138–151 | MR | Zbl

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

[6] Didier F., Tillich J. P., “Computing the algebraic immunity efficiently”, Lecture Notes Computer Sci., 4047 (2006), 359–374 | DOI

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