Geodesic
On construction of correlation-immune functions via minimal functions
Matematičeskie voprosy kriptografii, Tome 9 (2018) no. 2, pp. 7-22 
E. K. Alekseev; E. K. Karelina; O. A. Logachev. On construction of correlation-immune functions via minimal functions. Matematičeskie voprosy kriptografii, Tome 9 (2018) no. 2, pp. 7-22. http://geodesic.mathdoc.fr/item/MVK_2018_9_2_a1/
@article{MVK_2018_9_2_a1,
     author = {E. K. Alekseev and E. K. Karelina and O. A. Logachev},
     title = {On construction of correlation-immune functions via minimal functions},
     journal = {Matemati\v{c}eskie voprosy kriptografii},
     pages = {7--22},
     year = {2018},
     volume = {9},
     number = {2},
     language = {en},
     url = {http://geodesic.mathdoc.fr/item/MVK_2018_9_2_a1/}
}
TY  - JOUR
AU  - E. K. Alekseev
AU  - E. K. Karelina
AU  - O. A. Logachev
TI  - On construction of correlation-immune functions via minimal functions
JO  - Matematičeskie voprosy kriptografii
PY  - 2018
SP  - 7
EP  - 22
VL  - 9
IS  - 2
UR  - http://geodesic.mathdoc.fr/item/MVK_2018_9_2_a1/
LA  - en
ID  - MVK_2018_9_2_a1
ER  - 
%0 Journal Article
%A E. K. Alekseev
%A E. K. Karelina
%A O. A. Logachev
%T On construction of correlation-immune functions via minimal functions
%J Matematičeskie voprosy kriptografii
%D 2018
%P 7-22
%V 9
%N 2
%U http://geodesic.mathdoc.fr/item/MVK_2018_9_2_a1/
%G en
%F MVK_2018_9_2_a1

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

The use of correlation-immune functions in a cryptographic primitive may provide resistance against some key compromising methods. Designing of modern cryptographic primitives poses the challenge of constructing correlationimmune functions of a relatively large number of arguments. This paper proposes a method combining two basic approaches of solving this problem: iterative and a direct-search ones. Proposed method is based on minimal correlation-immune functions. The functions constructed by this method have no obvious structural characteristics that may be used to distinguish them from a random function. The first stage of the proposed method is an easily implemented iteration procedure, which allows to construct many special functions that depend on the desired number of variables. At the second stage the constructed functions are used by some search procedure to find functions with given cryptographic properties. For the second stage the paper presents the reduction of the problem of searching for a resilient function with a preassigned order to the problem of solving a system of linear pseudo-Boolean equations. We also study how to apply a modification of the proposed method in order to improve the cryptographic parameters of the known “good” functions by means of small changes. Examples of successful applications of the methods described are given.

[1] Alekseev E. K., “Some algebraic and combinatorial properties of correlation-immune Boolean functions”, Diskretnaya matematika, 22:3 (2010), 110–126 (in Russian) | DOI | MR | Zbl

[2] Alekseev E. K., “Some measures of nonlinearity of Boolean functions”, Prikladnaya diskretnaya matematika, 2 (2011), 5–16 (in Russian)

[3] Alekseev E. K., “Filtering generator attacks with function close to algebraically degenerate”, Sbornik statej molodyh uchenyh fakul'teta VMK MSU, 8 (2011), 19–32 (in Russian)

[4] Alekseev E. K., Karelina E. K., “Classification of correlation-immune and minimal correlationimmune functions of 4 and 5 variables”, Diskretnaya matematika, 27:1 (2015), 22–33 (in Russian) | DOI | MR | Zbl

[5] Kuschinskaja L. A., Research in applicability limits of shift register-based stream ciphers cryptanalysis methods, Master degree thesis, MSU, CMC Faculty, 2015, 34 pp. (in Russian)

[6] Logachev O. A., Salnikov A. A., Smyshlyaev S. V., Yashchenko V. V., Boolean functions in coding theory and cryptology, URSS, M., 2015, 576 pp. (in Russian) | MR

[7] Information technology. Information security. Block ciphers, GOST R 34.12-2015, Federal Agency on Technical Regulating and Metrology, 2015 (in Russian)

[8] Tarannikov Yu. V., “Correlation-immune and resilient Boolean functions”, Matematicheskie voprosy kibernetiki, 11 (2002), 91–148 (in Russian) | MR | Zbl

[9] Siegenthaler T., “Decrypting a class of stream cipher using ciphertext only”, IEEE Trans. Comput., 34:1 (1985), 81–85 | DOI

[10] Meier W., Staffelbach O., “Fast correlation attacks on certain stream ciphers”, J. of Cryptology, 1 (1989), 159–176 | DOI | MR | Zbl

[11] Courtois N., Meier W., “Algebraic attacks on stream ciphers with linear feedback”, EUROCRYPT'03, Lect. Notes Comput. Sci., 2656, 346–359 | MR

[12] Matsui M., “Linear cryptanalysis method for DES cipher”, EUROCRYPT'93, Lect. Notes Comput. Sci., 765, 1994, 386–397 | DOI | Zbl

[13] Dawson E., Clark A., Golich J., Millan W., Penna L., Simpson L., “The LILI-128 keystream generator”, Proc. of the first NESSIE workshop, 2000, 1–14 | MR | Zbl