SAO 1-Resilient Functions With Lower Absolute Indicator in Even Variables

Abstract

In 2018, Tang and Maitra presented a class of balanced Boolean functions in $n$ variables with the absolute indicator $\Delta _{f}< 2^{n/2}$ and the nonlinearity $NL(f)> 2^{n-1}-2^{n/2}$ , that is, $f$ is SAO (strictly almost optimal), for $n=2k\equiv 2\,\,({\mathrm {mod}\,\,}4)$ and $n\geq 46$ in [IEEE Ttans. Inf. Theory 64 (1): 393-402, 2018]. However, there is no evidence to show that the absolute indicator of any 1-resilient function in $n$ variables can be strictly less than $2^{\lfloor ({n+1})/{2}\rfloor }$ , and the previously best known upper bound of which is $5\cdot 2^{n/2}-2^{n/4+2}+4$ . In this paper, we concentrate on two directions. Firstly, to complete Tang and Maitra’s work for $k$ being even, we present another class of balanced functions in $n$ variables with the absolute indicator $\Delta _{f}< 2^{n/2}$ and the nonlinearity $NL(f)> 2^{n-1}-2^{n/2}$ for $n\equiv 0~({\mathrm {mod}~}4)$ and $n\geq 48$ . Secondly, we obtain two new classes of 1-resilient functions possessing very high nonlinearity and very low absolute indicator, from bent functions and plateaued functions, respectively. Moreover, one class of them achieves the currently known highest nonlinearity $2^{n-1}-2^{n/2-1}-2^{n/4}$ , and the absolute indicator of which is upper bounded by $2^{n/2}+2^{n/4+1}$ that is a new upper bound of the minimum of absolute indicator of 1-resilient functions, as it is clearly optimal than the previously best known upper bound $5\cdot 2^{n/2}-2^{n/4+2}+4$ .

Keywords

• Absolute indicator
• balanced Boolean functions
• nonlinearity
• resilient functions
• SAO functions