Bent functions with stronger nonlinear properties: K-bent functions
Natalia Tokareva · Journal of Applied and Industrial Mathematics · 2008
We introduce the notion of k-bent function, i.e., a Boolean functionwith evennumber m of variables υ 1, …, υ m which can be approximated with all functions of the form 〈u, v〉 j ⊕ a in the equally poor manner, where u ∈ ℤ 2 , a ∈ ℤ2, and 1 ⩽ j ⩽ k. Here 〈·, ·〉 j is an analog of the inner product of vectors; k changes from 1 to m/2. The operations 〈·, ·〉 k , 1 ⩽ k ⩽ m/2, are defined by using the special series of binary Hadamard-like codes A of length 2 m . Namely, the vectors of values for the functions 〈u, v〉 k ⊕ a are codewords of the code A . The codes A are constructed using subcodes of the ℤ4-linear Hadamard-like codes of length 2 m+1, which were classified by D. S. Krotov (2001). At that the code A 1 is linear and A 1 , …, A /2 are pairwise nonequivalent. On the codewords of a code A , we define a group operation • coordinated with the Hamming metric. That is why we can consider k-bent functions as functions that are maximal nonlinear in k distinct senses of linearity at the same time. Bent functions in usual sense coincide with 1-bent functions. For k > ℓ ⩾ 1, the class of k-bent functions is a proper subclass of the class of ℓ-bent functions. In the paper, we give methods for constructing k-bent functions and study their properties. It is shown that there exist k-bent functions with an arbitrary algebraic degree d, where 2 ⩽ d ⩽ max {2, m/2 − k + 1}. Given an arbitrary k, we define the subset $$ \mathfrak{F}_m^k \mathcal{F}_m^k $$ of the set $$ \mathfrak{F}_m^k \mathcal{F}_m^k $$ $$ \mathcal{A}_m^k \mathcal{B}_m^k $$ of all Boolean functions in m variables with the following property: on this subset k-bent functions and 1-bent functions coincide.