Discrete Functions
On the number of the closest bent functions to some Maiorana–McFarland bent functions
D. A. Bykova,
N. A. Kolomeetsb a Novosibirsk State University
b Sobolev Institute of Mathematics, Siberian Branch of the Russian Academy of Sciences, Novosibirsk
Abstract:
We consider the numbers of bent functions that are closest to some bent functions from the Maiorana — McFarland class
$\mathcal{M}_{2n}$, specifically, the numbers near to their lower
$\mathcal{l}_{2n} = 2^{2n + 1} - 2^n$ and tight upper
$\mathcal{L}_{2n}$ bounds. For a bent function $f(x, y) = \langle x, \sigma(y)\rangle \oplus \varphi(y) \in \mathcal{M}_{2n}$, where
$\sigma$ is a function based on the inverse function of elements of the finite field, the number of closest bent functions is calculated for identically zero
$\varphi$. Moreover, it is shown that this number is less than
$\mathcal{l}_{2n} + 82(2^n - 1)$ and asymptotically equals to
$\mathcal{l}_{2n} + o(\mathcal{l}_{2n})$ for some
$\varphi$. An explicit formula for the number of bent functions closest to $f(x, y) = \langle x, y\rangle \oplus y_1 y_2 \dots y_m$, where
$3 \leq m \leq n$, has been derived. The values for
$m = 3$ and
$m = n$ are equal to
$o(\mathcal{L}_{2n})$ and $\dfrac{1}{3}\mathcal{L}_{2n} + o(\mathcal{L}_{2n})$ respectively as
$n \to \infty$. A complete classification of
$\mathcal{M}_6$ using the number of closest bent functions is obtained.
Keywords:
affine subspaces, bent functions, Maiorana — McFarland class, minimal distance, the closest functions.
UDC:
519.7
DOI:
10.17223/2226308X/17/6