Some cardinality estimates for the set of correlation-immune Boolean functions obtained by the mapping AC^w

Katerina Karelina


The mapping  was introduced in one of the works devoted to the study of correlation-immune functions. This mapping allows to quickly increase the number of function's variables. It is the base of recursive method of synthesis correlation-immune Boolean functions. However, applying a mapping to the function with all possible parameters allows constructing functions, which is equal to each other. In this paper, there is a criterion of functions equality, which can be produced by  mapping. Also, lower and upper bounds for the set of correlation-immune functions obtained using this mapping are proved. In the proof of these estimates, the function equality criterion is used. The paper presents examples of correlation-immune functions of various weights of a small number of variables and the values of the cardinalities of the corresponding sets, which are obtained by applying the mapping  to the given correlation-immune functions. These results are obtained using computer and they confirm the proved upper and lower bounds for the considered sets of functions.

Full Text:

PDF (Russian)


Y. V. Tarannikov, “Correlation-immune and resilient Boolean functions”, Mathematical Problems of Cybernetics, 11 (2002), 91-148

E. K. Alekseev, “Some algebraic and combinatorial properties of correlation-immune Boolean functions”, Discrete Math., 22:3 (2010), 110-126,

Alekseev E.K., Karelina E.K., Logachev O.A., “On construction of correlation-immune functions via minimal functions”, Mathematical Problems of Cryptography, 9:2, (2018), 7–21,

E. K. Alekseev, E. K. Karelina, “Classification of correlation-immune and minimal correlation-immune Boolean functions of 4 and 5 variables”, Discrete Math., 27:1 (2015), 22–33,

E. K. Karelina, “On a method of synthesis of correlation-immune Boolean functions”, Discrete Math., 30:4 (2018), 12–28,

O. A. Logachev, A. A. Salnikov, S. V. Smyshlyaev, V. V. Yashchenko, Boolean functions in coding theory and cryptology, URSS. ISBN 978-5-9710-0961-0, 576 c., 2015

Y. V. Tarannikov, Combinatorial properties of discrete structures and applications to cryptology, ISBN 978-5-94057-812-3, 2011, 152 pp


  • There are currently no refbacks.

Abava  Absolutech Convergent 2020

ISSN: 2307-8162