Discrete Functions

An estimation of the nonlinearity of balanced Boolean functions generated by generalized Dobbertin's construction

I. A. Sutormin<sup>ab

a</sup> Novosibirsk State University
^b Sobolev Institute of Mathematics, Siberian Branch of the Russian Academy of Sciences, Novosibirsk

Abstract: A generalization of the Dobbertin’s construction for highly nonlinear balanced Boolean functions is proposed. The Walsh — Hadamard spectrum is studied and estimates of the spectral radius of the proposed functions are obtained. An exact upper bound for the spectral radius (lower bound for nonlinearity) is proved, and a method for constructing a balanced function $\Theta$ in $2n$ variables using a balanced $\theta$ in $n-k$ variables with spectral radius $R_\Theta = 2^n + 2^{k} R_\theta $ is proposed. Here, $ R_\Theta $ and $ R_\theta $ are the spectral radii of $ \Theta $ and $ \theta $ respectively.

Keywords: boolean functions, bent functions, balancedness, nonlinearity, spectral radius.

UDC: 519.7

DOI: 10.17223/2226308X/13/9