**The Lower Bounds on the Second Order Nonlinearity of Cubic Boolean Functions**

*Xuelian Li and Yupu Hu and Juntao Gao*

**Abstract: **It is a difficult task to compute the $r$-th order nonlinearity of a
given function with algebraic degree strictly greater than $r>1$.
Even the lower bounds on the second order nonlinearity is known only
for a few particular functions. We investigate the lower bounds on
the second order nonlinearity of cubic Boolean functions
$F_u(x)=Tr(\sum_{l=1}^{m}\mu_{l}x^{d_{l}})$, where $u_{l} \in
F_{2^n}^{*}$, $d_{l}=2^{i_{l}}+2^{j_{l}}+1$, $i_{l}$ and $j_{l}$ are
positive integers, $n>i_{l}> j_{l}$. Especially, for a class of
Boolean functions $G_u(x)=Tr(\sum_{l=1}^{m}\mu_{l}x^{d_{l}})$, we
deduce a tighter lower bound on the second order nonlinearity of the
functions, where $u_{l} \in F_{2^n}^{*}$,
$d_{l}=2^{i_{l}\gamma}+2^{j_{l}\gamma}+1$, $i_{l}> j_{l}$ and
$\gamma\neq 1$ is a positive integer such that $gcd(n,\gamma)=1$.
\\The lower bounds on
the second order nonlinearity of cubic monomial Boolean functions,
represented by $f_\mu(x)=Tr(\mu x^{2^i+2^j+1})$, $\mu\in F_{2^n}^*$,
$i$ and $j$ are positive integers such that $i>j$, have recently
(2009) been obtained by Gode and Gangopadhvay. Our results have the
advantages over those of Gode and Gangopadhvay as follows. We first
extend the results from monomial Boolean functions to Boolean
functions with more trace terms. We further generalize and improve
the results to a wider range of $n$. Also, our bounds are better
than those of Gode and Gangopadhvay for monomial functions
$f_\mu(x)$.

**Category / Keywords: **secret-key cryptography / cryptography, derivative, the second nonlinearity, trace function, quadratic form

**Publication Info: **This paper has not been published elsewhere.

**Date: **received 10 Jan 2010

**Contact author: **xuelian202 at 163 com

**Available format(s): **PDF | BibTeX Citation

**Version: **20100112:035616 (All versions of this report)

**Short URL: **ia.cr/2010/009

**Discussion forum: **Show discussion | Start new discussion

[ Cryptology ePrint archive ]