Monomial Boolean functions with large high-order nonlinearities
The \emph{nonlinearity} of a Boolean function \(f\colon \mathbb{F}_2^n \to \mathbb{F}_2\) is the distance from \(f\) to the closest linear function. More generally, the \(d\)-order nonlinearity of \(f\) is its distance to the closest degree \(d\) (or less) function. Here \emph{degree} is the degree of the unique multilinear \(\mathbb{F}_2\)-polynomial representing \(f\), and a function is \emph{linear} if it has degree at most~\(1\). A random function is highly nonlinear. It is more challenging to exhibit explicit functions which have high nonlinearity. One class of functions which can be used to that end is \emph{monomial (Boolean) functions}. In these functions, the input is interepreted as an element of the finite field \(\mathbb{F}_{2^n}\), and the function is the trace of a monomial, that is, the function has the form \(f(x) = \operatorname{tr}(\lambda x^d)\) for some \(\lambda \in \mathbb{F}_{2^n}\) and \(d \in \mathbb{Z}\); here \emph{trace} has its usual definition from algebraic number theory. In this paper, the authors give lower bounds on the high nonlinearity of several monomial functions: \begin{enumerate} \item[1.] Second-order nonlinearity of \(\operatorname{tr}(x^7)\). \item[2.] Second-order nonlinearity of \(\operatorname{tr}(x^{2^r+3})\), where \(n = 2r\). \\ This should be compared to an identical lower bound for \(\operatorname{tr}(x^{2^{r+1}+3})\), proved in [\textit{H. Yan} and \textit{D. Tang}, Discrete Math. 343, No. 5, Article ID 111698, 11 p. (2020; Zbl 1468.94977)]. \item[3.] Third-order nonlinearity of \(\operatorname{tr}(x^{15})\). \item[4.] \(r\)-order nonlinearity of \(\operatorname{tr}(x^{2^{r+1}-1})\). \item[5.] \(r\)-order nonlinearity of \(\operatorname{tr}(x^{2^n-2})\). \end{enumerate} All bounds are proved using the method of \textit{C. Carlet} [IEEE Trans. Inf. Theory 54, No. 3, 1262--1272 (2008; Zbl 1192.94145)]. The bounds on second-order nonlinearity match the best known lower bounds on any explicit function.
- On higher order nonlinearities of monomial partial spreads type Boolean functions
- Lower bounds on the second order nonlinearity of Boolean functions
- Improved lower bounds on higher order nonlinearity
- On third-order nonlinearity of biquadratic monomial Boolean functions
- The lower bounds on the second order nonlinearity of three classes of Boolean functions with high nonlinearity
- A new class of monomial bent functions
- A new lower bound on the second-order nonlinearity of a class of monomial bent functions
- A new proof of Szemerédi's theorem
- A new proof of Szemerédi's theorem for arithmetic progressions of length four
- Algebraic Immunity of S-Boxes Based on Power Mappings: Analysis and Construction
- Boolean functions for cryptography and coding theory
- Bounds on an exponential sum arising in Boolean circuit complexity
- Constructing new APN functions from known ones
- Estimation of certain exponential sums arising in complexity theory
- Higher-order nonlinearity of Kasami functions
- scientific article; zbMATH DE number 438988 (Why is no real title available?)
- scientific article; zbMATH DE number 1024657 (Why is no real title available?)
- Improving lower bounds on the second-order nonlinearity of three classes of Boolean functions
- Inverse-exponential correlation bounds and extremely rigid matrices from a new derandomized XOR lemma
- Lower bounds on the second order nonlinearity of Boolean functions
- Lower bounds on the size of bounded depth circuits over a complete basis with logical addition
- Majority gates vs. general weighted threshold gates
- More vectorial Boolean functions with unbounded nonlinearity profile
- Multiparty protocols, pseudorandom generators for Logspace, and time- space trade-offs
- Norms, XOR lemmas, and lower bounds for polynomials and protocols
- On ``bent functions
- On the higher-order nonlinearity of a Boolean bent function class (constructed via Niho power functions)
- On the lower bounds of the second order nonlinearities of some Boolean functions
- On the number of the rational zeros of linearized polynomials and the second-order nonlinearity of cubic Boolean functions
- On the second-order nonlinearities of some bent functions
- On third-order nonlinearity of biquadratic monomial Boolean functions
- Recursive Lower Bounds on the Nonlinearity Profile of Boolean Functions and Their Applications
- Some lower bounds on the algebraic immunity of functions given by their trace forms
- Some new three-valued crosscorrelation functions for binary m-sequences
- The lower bound on the second-order nonlinearity of a class of Boolean functions with high nonlinearity
- The lower bounds on the second order nonlinearity of three classes of Boolean functions with high nonlinearity
- The lower bounds on the second-order nonlinearity of three classes of Boolean functions
- Third-order nonlinearities of a subclass of Kasami functions
- XOR lemmas for resilient functions against polynomials
This page was built for publication: Monomial Boolean functions with large high-order nonlinearities
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q6204170)
