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

Abstract

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.