**On the Lower Bounds of the Second Order Nonlinearity of some Boolean Functions **

*Sugata Gangopadhyay, Sumanta Sarkar, Ruchi Telang*

**Abstract: **The $r$-th order nonlinearity of a Boolean function is an important
cryptographic criterion in analyzing the security of stream as well
as block ciphers. It is also important in coding theory as it is
related to the covering radius of the Reed-Muller code $\mathcal{R}(r, n)$.
In this paper we deduce the lower bounds of the second order nonlinearity
of the two classes of Boolean functions of the form
\begin{enumerate}
\item
$f_{\lambda}(x) = Tr_1^n(\lambda x^{d})$ with $d=2^{2r}+2^{r}+1$
and $\lambda \in \mathbb{F}_{2^{n}}$ where $n = 6r$.
\item
$f(x,y)=Tr_1^t(xy^{2^{i}+1})$
where $x,y \in \mathbb{F}_{2^{t}}, n = 2t, n \ge 6$ and
$i$ is an integer such that $1\le i < t$, $\gcd(2^t-1, 2^i+1) = 1$.
\end{enumerate}
For some $\lambda$, the first class gives bent functions whereas
Boolean functions of the second class are all bent, i.e., they achieve
optimum first order nonlinearity.

**Category / Keywords: **secret-key cryptography / Boolean functions, second order nonlinearity

**Date: **received 24 Feb 2009, last revised 17 Mar 2009

**Contact author: **gsugata at gmail com

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

**Version: **20090317:092805 (All versions of this report)

**Short URL: **ia.cr/2009/094

[ Cryptology ePrint archive ]