On Boolean Functions with cardinality of propagation criteria equal to 2^n − 2

Gleb Isaev


The study of the propagation criterion for Boolean functions and its properties is one of the most important areas of research in the eld of cryptographic applications. Boolean function satises the propagation criterion to the direction (dened by a vector from the corresponding n-dimensional Boolean space) if the derivative of function in this direction is balanced. The set of all such directions (or vectors) for Boolean function is called the set of the propagation criterion. Note that for some classes of Boolean functions, the propagation criterion determines their extreme properties. For example, the propagation criterion of bent functions determines their maximum nonlinearity. In this paper we consider the question of the existence of Boolean functions, which are close enough to bent functions from the point of view of the propagation criterion, i. e. such class of Boolean functions, where all vectors, except for the zero and one non-zero vector, satisfy the propagation criterion. We show that a set of Boolean functions with such property exists only for an odd number of variables. In addition, we study the question of belonging a set of Boolean functions with this property to any cryptographic classes, including correlationimmune and resilient functions, and reveal a one-toone correspondence between these functions and bent functions.

Full Text:

PDF (Russian)


G.A. Isaev. "On Propagation Criteria of Some Classes of Boolean Functions" International Journal of Open Information Technologies, V. 9, No. 5, 2021, p. 1824 [in Russian].

O.A. Logachev, A.A. Salnikov, S.V. Smyshlyaev, V.V. Yashchenko. "Boolean Functions in Coding Theory and Cryptography" Moscow, URSS, 2015, pp. 583 [in Russian].

C. Carlet. "Boolean Functions for Cryptography and Coding Theory" Cambridge University Press, Cambridge, 2020, pp. 562.

E. Pasalic, T. Johansson. "Further Results on the Relation Between Nonlinearity and Resiliency for Boolean Functions" 7th IMA International Conference on Cryptography and Coding, LNCS 1746, 1999, p. 3544.

V.N. Potapov, A.A. Taranenko, Yu.V. Tarannikov. "Asymptotic bounds on numbers of bent functions and partitions of the Boolean hypercube into linear and ane subspaces" arXiv:2108.00232 [math.CO], 2021, pp. 10.

B. Preneel, W. Van Leekwijck, L. Van Linden, R. Govaerts, J. Vandewalle. "Propagation characteristics of Boolean functions" EUROCRYPT'90, LNCS 473, Springer-Verlag, 1990, p. 161173.

O.S. Rothaus. "On Bent¿ Functions" Journal of Combinatorial Theory (A), V. 20, No. 3, 1976, p. 300305.

J. Seberry, X.M. Zhang, Y. Zheng. "Nonlinearly Balanced Boolean Functions and Their Propagation Characteristics" CRYPTO'93, 13th Annual International Cryptology Conference, Santa Barbara, California, USA, 1993, p. 49-60.

Y. Zheng, X.M. Zhang. "On Relationships among Avalanche, Nonlinearity, and Correlation Immunity" ASIACRYPT 2000, 6th International Conference on the Theory and Application of Cryptology and Information Security, LNCS 1976, 2000, p. 470-482.


  • There are currently no refbacks.

Abava  Кибербезопасность MoNeTec 2024

ISSN: 2307-8162