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

In 2018, Tang and Maitra presented a class of balanced Boolean functions in <inline-formula> <tex-math notation="LaTeX">$n$ </tex-math></inline-formula> variables with the absolute indicator <inline-formula> <tex-math notation="LaTeX">$\Delta _{f}&lt; 2^{n/2}$ </tex-math></inline-formula> and the nonlinearity <inline-formula> <tex-math notation="LaTeX">$NL(f)&gt; 2^{n-1}-2^{n/2}$ </tex-math></inline-formula>, that is, <inline-formula> <tex-math notation="LaTeX">$f$ </tex-math></inline-formula> is SAO (strictly almost optimal), for <inline-formula> <tex-math notation="LaTeX">$n=2k\equiv 2\,\,({\mathrm {mod}\,\,}4)$ </tex-math></inline-formula> and <inline-formula> <tex-math notation="LaTeX">$n\geq 46$ </tex-math></inline-formula> in [IEEE Ttans. Inf. Theory 64 <xref rid="deqn1" ref-type="disp-formula">(1)</xref>: 393-402, 2018]. However, there is no evidence to show that the absolute indicator of any 1-resilient function in <inline-formula> <tex-math notation="LaTeX">$n$ </tex-math></inline-formula> variables can be strictly less than <inline-formula> <tex-math notation="LaTeX">$2^{\lfloor ({n+1})/{2}\rfloor }$ </tex-math></inline-formula>, and the previously best known upper bound of which is <inline-formula> <tex-math notation="LaTeX">$5\cdot 2^{n/2}-2^{n/4+2}+4$ </tex-math></inline-formula>. In this paper, we concentrate on two directions. Firstly, to complete Tang and Maitra&#x2019;s work for <inline-formula> <tex-math notation="LaTeX">$k$ </tex-math></inline-formula> being even, we present another class of balanced functions in <inline-formula> <tex-math notation="LaTeX">$n$ </tex-math></inline-formula> variables with the absolute indicator <inline-formula> <tex-math notation="LaTeX">$\Delta _{f}&lt; 2^{n/2}$ </tex-math></inline-formula> and the nonlinearity <inline-formula> <tex-math notation="LaTeX">$NL(f)&gt; 2^{n-1}-2^{n/2}$ </tex-math></inline-formula> for <inline-formula> <tex-math notation="LaTeX">$n\equiv 0~({\mathrm {mod}~}4)$ </tex-math></inline-formula> and <inline-formula> <tex-math notation="LaTeX">$n\geq 48$ </tex-math></inline-formula>. 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 <inline-formula> <tex-math notation="LaTeX">$2^{n-1}-2^{n/2-1}-2^{n/4}$ </tex-math></inline-formula>, and the absolute indicator of which is upper bounded by <inline-formula> <tex-math notation="LaTeX">$2^{n/2}+2^{n/4+1}$ </tex-math></inline-formula> 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 <inline-formula> <tex-math notation="LaTeX">$5\cdot 2^{n/2}-2^{n/4+2}+4$ </tex-math></inline-formula>.

Abstract licence: CC BY-NC-ND

A person counts once a day per paper. We keep no cookie and no address: a reader is a hash that changes every day. Any month under five reads shows no number.