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 Δf < 2n/2 and the nonlinearity NL(f) > 2n-1 - 2n/2, that is, f is SAO (strictly almost optimal), for n = 2k ≡ 2(mod4) and n ≥ 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⌊(n+1)/2⌋, and the previously best known upper bound of which is 5 · 2n/2 - 2n/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 Δf < 2n/2 and the nonlinearity NL(f) > 2n-1 - 2n/2 for n ≡ 0(mod4) and n ≥ 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 2n-1 - 2n/2-1 - 2n/4, and the absolute indicator of which is upper bounded by 2n/2 + 2n/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 · 2n/2 - 2n/4+2 + 4. CCBY