Search

The nonlinearity and additive nonlinearity of a function are defined as the Hamming distances, respectively, to the set of all affine mappings and to the set of all mappings having nontrivial additive translators. On the basis of the revealed relation between the nonlinearities and the Fourier coefficients of the characters of a function, convenient formulas for nonlinearity evaluation for practically important classes of functions over an arbitrary finite field are found. In the case of a field of even characteristic, similar results were obtained for the additive nonlinearity in terms of the autocorrelation coefficients. The formulas obtained made it possible to present specific classes of functions with maximal possible and high nonlinearity and additive nonlinearity. [ABSTRACT FROM AUTHOR]

An n-place function over a field with q elements is called maximally nonlinear if it has the greatest nonlinearity among all such functions. Criteria and necessary conditions for maximal nonlinearity are obtained, which imply that, for even n, the maximally nonlinear functions are bent functions, but, for q > 2, the known families of bent functions are not maximally nonlinear. For an arbitrary finite field, a relationship between the Hamming distances from a function to all affine mappings and the Fourier spectra of the nontrivial characters of the function are found. [ABSTRACT FROM AUTHOR]

An n-place function over a field F q with q elements is called maximally nonlinear if it has the largest nonlinearity among all q-valued n-place functions. We show that, for even n=2, a function is maximally nonlinear if and only if its nonlinearity is q n − 1 (q − 1) − q n 2 − 1 ; for n=1, the corresponding criterion for maximal nonlinearity is q − 2. For q > 2 and even n=2, we describe the set of all maximally nonlinear quadratic functions and find its cardinality. In this case, all maximally nonlinear quadratic functions are quadratic bent functions and their number is smaller than the halved number of the bent functions. [ABSTRACT FROM AUTHOR]

Keywords: Boolean function; discrete Fourier (Walsh-Hadamard) transform; maximum nonlinearity; amplitude; dimension of a Boolean function; extension of general affine group EN Boolean function discrete Fourier (Walsh-Hadamard) transform maximum nonlinearity amplitude dimension of a Boolean function extension of general affine group 177 192 16 06/17/22 20220601 NES 220601 Note: Originally published in Diskretnaya Matematika (2021) 33,No2, 66-85 (in Russian). Discrete Fourier (Walsh-Hadamard) transform, dimension of a Boolean function, extension of general affine group, Boolean function, maximum nonlinearity, amplitude It is important to note the value of group invariants in problems connected to classification of Boolean functions. [Extracted from the article]

We find a relation between the W-intersection matrix (which characterizes the degree of "nonhomomorphy") of a transformation and the difference distribution table and the correlation matrix (which characterize the degree nonlinearity of a transformation). An upper estimate for the dimension of a subspace invariant under almost bent functions is put forward. A formula for evaluation of the W-intersection matrix of a composition of two transformations is obtained. [ABSTRACT FROM AUTHOR]

A new approach to the study of algebraic, combinatorial, and cryptographic properties of Boolean functions is proposed. New relations between functions have been revealed by consideration of an injective mapping of the set of Boolean functions onto the sphere in a Euclidean space. Moreover, under this mapping some classes of functions have extremely regular localizations on the sphere. We introduce the concept of curvature of a Boolean function, which characterizes its proximity (in some sense) to maximally nonlinear functions. [ABSTRACT FROM AUTHOR]

We consider the functional system of vector functions of many-valued logic with the naturally defined operation of superposition and construct examples of closed classes of special type without a basis and with a countable basis. [ABSTRACT FROM AUTHOR]

We consider a sequence of almost critical branching processes with immigration supposing that the immigration process is weakly stationary. The rate of growth and asymptotic properties of fluctuations of such branching processes are investigated. [ABSTRACT FROM AUTHOR]

The paper is concerned with relations between the correlation-immunity (stability) and the perfectly balancedness of Boolean functions. It is shown that an arbitrary perfectly balanced Boolean function fails to satisfy a certain property that is weaker than the 1-stability. This result refutes some assertions by Markus Dichtl. On the other hand, we present new results on barriers of perfectly balanced Boolean functions which show that any perfectly balanced function such that the sum of the lengths of barriers is smaller than the length of variables, is 1-stable. [ABSTRACT FROM AUTHOR]

Boolean functions which satisfy the Strict Avalanche Criterion (SAC) play an important role in the art of information security. In this paper, we extend the concept of SAC to finite fields GF(p). A necessary and sufficient condition is given by using spectral analysis. Also, based on an interesting permutation polynomial theorem, we prove various facts about (n – 1)-th order SAC functions on GF(p). We also construct many such functions.

We prove various results on monotone Boolean functions. In particular, we prove a conjecture proposed recently, stating that there are no monotone bent Boolean functions. Further, we give an upper bound on the nonlinearity of monotone functions in odd dimension, we describe the Walsh-Hadamard spectrum and investigate some other cryptographic properties of monotone Boolean functions. [ABSTRACT FROM AUTHOR]

The multiplicative (or conjunctive) complexity of a Boolean function f(x1, . . . , xn) (respectively, of a system of Boolean functions F = {f1, . . . , fm}) is the smallest number of AND gates in circuits in the basis {x&y, x ⊕ y, 1} implementing the function f (respectively, all the functions of system F). The multiplicative complexity of a function f (of a system of functions F) will be denoted by μ(f) (respectively, μ(F)). It will be shown that μ(f) = n − 1 if a function f(x1, . . . , xn) is representable as x1x2 . . . xn ⊕ q(x1, . . . , xn), where q is a function of degree two (n ≥ 3).Moreover,we show that μ(f) ≤ n−1 if a function f(x1, . . . , xn) is representable as a XOR sum of two multiaffine functions. Furthermore, μ(F) = n−1 if F = {x1x2 . . . xn , f(x1, . . . , xn)},where f is a function of degree two or a multiaffine function. [ABSTRACT FROM AUTHOR]

Rotation symmetric Boolean functions have been extensively studied in the last 15 years or so because of their importance in cryptography and coding theory. Until recently, very littlewas known about such basic questions as when two such functions are affine equivalent. This question in important in applications, because almost all important properties of Boolean functions (such as Hamming weight, nonlinearity, etc.) are affine invariants, so when searching a set for functions with useful properties, it suffices to consider just one function in each equivalence class. This can greatly reduce computation time. Even for quadratic functions, the analysis of affine equivalence was only completed in 2009. The much more complicated case of cubic functions was completed in the special case of affine equivalence under permutations for monomial rotation symmetric functions in two papers from 2011 and 2014. There has also been recent progress for some special cases for functions of degree > 3. In 2007 it was found that functions satisfying a new notion of k-rotation symmetry for k > 1 (where the case k = 1 is ordinary rotation symmetry) were of substantial interest in cryptography and coding theory. Since then several researchers have used these functions for k = 2 and 3 to study such topics as construction of bent functions, nonlinearity and covering radii of various codes. In this paper we develop a detailed theory for the monomial 3-rotation symmetric cubic functions, extending earlier work for the case k = 2 of these functions. [ABSTRACT FROM AUTHOR]

We consider an approach to the classification of n-variable Boolean bent functions of the nonlinearity degree 3. We utilize the apparatus of bent rectangles introduced by S. V. Agievich. This apparatus was used for the classification of 8-variable Boolean cubic bent functions. The results of our research allow to construct cubic bent functions that depend on an arbitrary even number of variables; the construction is based on well studied quadratic bent functions. [ABSTRACT FROM AUTHOR]