Geodesic
Level structure of Zhegalkin polynomials, properties of test sets, and an annihilator search algorithm
Žurnal vyčislitelʹnoj matematiki i matematičeskoj fiziki, Tome 50 (2010) no. 7, pp. 1334-1340 
K. N. Koryagin. Level structure of Zhegalkin polynomials, properties of test sets, and an annihilator search algorithm. Žurnal vyčislitelʹnoj matematiki i matematičeskoj fiziki, Tome 50 (2010) no. 7, pp. 1334-1340. http://geodesic.mathdoc.fr/item/ZVMMF_2010_50_7_a14/
@article{ZVMMF_2010_50_7_a14,
     author = {K. N. Koryagin},
     title = {Level structure of {Zhegalkin} polynomials, properties of test sets, and an annihilator search algorithm},
     journal = {\v{Z}urnal vy\v{c}islitelʹnoj matematiki i matemati\v{c}eskoj fiziki},
     pages = {1334--1340},
     year = {2010},
     volume = {50},
     number = {7},
     language = {ru},
     url = {http://geodesic.mathdoc.fr/item/ZVMMF_2010_50_7_a14/}
}
TY  - JOUR
AU  - K. N. Koryagin
TI  - Level structure of Zhegalkin polynomials, properties of test sets, and an annihilator search algorithm
JO  - Žurnal vyčislitelʹnoj matematiki i matematičeskoj fiziki
PY  - 2010
SP  - 1334
EP  - 1340
VL  - 50
IS  - 7
UR  - http://geodesic.mathdoc.fr/item/ZVMMF_2010_50_7_a14/
LA  - ru
ID  - ZVMMF_2010_50_7_a14
ER  - 
%0 Journal Article
%A K. N. Koryagin
%T Level structure of Zhegalkin polynomials, properties of test sets, and an annihilator search algorithm
%J Žurnal vyčislitelʹnoj matematiki i matematičeskoj fiziki
%D 2010
%P 1334-1340
%V 50
%N 7
%U http://geodesic.mathdoc.fr/item/ZVMMF_2010_50_7_a14/
%G ru
%F ZVMMF_2010_50_7_a14

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

Properties of the Boolean functions specified by the Zhegalkin polynomials in $n$ variables of degree not greater than $k$ are investigated from the viewpoint of placing their unit (zero) points on a unit cube. Properties of test sets for the Zhegalkin polynomials are considered, where the key role is played by the irredundant test sets. A deterministic algorithm for finding all the annihilators for a given polynomial is described including minimal-degree annihilators that have applications in cryptology. In the available algorithms for finding annihilators, the problem is reduced to solving systems of linear Boolean equations. Reducing the dimension of these systems decreases the algorithmic complexity of solving the problem. The proposed algorithm makes it possible to decrease the complexity of finding annihilators by reducing the dimension of such systems but it does not reduce the asymptotic complexity of solving systems of linear Boolean equations.

[1] Koryagin K. N., Khramkov S. S., “Svoistva razlozhimosti polinomov Zhegalkina”, Metody matem. modelirovaniya i obrabotki informatsii, MFTI, M., 1987, 159–161

[2] Zabaluev R. N., “O srednei slozhnosti bulevykh funktsii, zadannykh polinomami Zhegalkina”, Diskretnyi analiz i issled. operatsii. Ser. 1, 11:3 (2004), 3–15 | MR

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

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

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

[6] Baev V. V., “Usovershenstvovannyi algoritm poiska annigilyatorov nizkoi stepeni dlya mnogochlenov Zhegalkina”, Diskretnaya matem., 19:4 (2007), 132–138 | MR