Geodesic
Functions without short implicents.Part I: lower estimates of weights
Diskretnaya Matematika, Tome 27 (2015) no. 2, pp. 94-105.

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

The paper is concerned with $n$-place Boolean functions not admitting implicents of $k$ variables, $1\le k$. Estimates for the minimal possible weight $w\left( {n,\;k} \right)$ of such functions are obtained. It is shown that $w\left( {n,\;1} \right) = 2$, $n = 2,3,...$, and $w\left( {n,\;2} \right)\sim{\log _2}n$ as $n \to \infty$, and moreover, for $k > 2$ there exists ${n_0}$ such that $w\left( {n,\;k} \right) > {2^{k - 2}} \cdot {\log _2}n$ for all $n > {n_0}$.
Keywords: Boolean function, implicent, combinatorially complete matrix. 
@article{DM_2015_27_2_a5,
     author = {Pavel V. Roldugin and Alexey V. Tarasov},
     title = {Functions without short {implicents.Part} {I:} lower estimates of weights},
     journal = {Diskretnaya Matematika},
     pages = {94--105},
     publisher = {mathdoc},
     volume = {27},
     number = {2},
     year = {2015},
     language = {ru},
     url = {http://geodesic.mathdoc.fr/item/DM_2015_27_2_a5/}
}
TY  - JOUR
AU  - Pavel V. Roldugin
AU  - Alexey V. Tarasov
TI  - Functions without short implicents.Part I: lower estimates of weights
JO  - Diskretnaya Matematika
PY  - 2015
SP  - 94
EP  - 105
VL  - 27
IS  - 2
PB  - mathdoc
UR  - http://geodesic.mathdoc.fr/item/DM_2015_27_2_a5/
LA  - ru
ID  - DM_2015_27_2_a5
ER  - 
%0 Journal Article
%A Pavel V. Roldugin
%A Alexey V. Tarasov
%T Functions without short implicents.Part I: lower estimates of weights
%J Diskretnaya Matematika
%D 2015
%P 94-105
%V 27
%N 2
%I mathdoc
%U http://geodesic.mathdoc.fr/item/DM_2015_27_2_a5/
%G ru
%F DM_2015_27_2_a5
Pavel V. Roldugin; Alexey V. Tarasov. Functions without short implicents.Part I: lower estimates of weights. Diskretnaya Matematika, Tome 27 (2015) no. 2, pp. 94-105. http://geodesic.mathdoc.fr/item/DM_2015_27_2_a5/

[1] Glushkov V.M., Sintez tsifrovykh avtomatov, M.: GIFML, 1962

[2] Courtois N., Meier W., “Algebraic attacks on stream ciphers with linear feedback”, EUROCRYPT, Lect. Notes Comput. Sci., 2656, Springer-Verlag, 2003, 346-359

[3] Logachev O.A., Salnikov A.A., Smyshlyaev S.V., Yaschenko V.V., Bulevy funktsii v teorii kodirovaniya i kriptologii, M.: MTsNMO, 2012, 583 pp.

[4] Dalai D., Maitra S., Sarkar S., “Basic theory in construction of Boolean functions with maximum possible annihilator immunity”, Designs, Codes and Cryptography, 40:1 (2006), 41-58 | DOI

[5] Jiao L., Wang M., Li Y., Liu M., “On annihilators in fewer variables: basic theory and applications”, Chinese Journal of Electronics, 22:3 (2013), 489-494

[6] Glukhov M.M., Shishkov A.B., Matematicheskaya logika. Diskretnye funktsii. Teoriya algoritmov, SPb.: Lan, 2012

[7] Gorshkov S.P., “Primenenie teorii NP-polnykh zadach dlya otsenki slozhnosti resheniya sistem bulevykh uravnenii”, Obozr. prikl. i prom. matem., 2:3 (1995), 325–399

[8] Roldugin P.V., Tarasov A.V., “O bulevykh funktsiyakh bez verkhnikh biyunktivnykh analogov”, Matematicheskie problemy kriptografii, 4:1 (2013), 123–140

[9] Slovar kriptograficheskikh terminov. Pod red. B.A. Pogorelova i V.N. Sachkova, M.: MTsNMO, 2006