Paper 2009/094

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

Sugata Gangopadhyay, Sumanta Sarkar, and Ruchi Telang


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.

Available format(s)
Secret-key cryptography
Publication info
Published elsewhere. Unknown where it was published
Boolean functionssecond order nonlinearity
Contact author(s)
gsugata @ gmail com
2009-03-17: last of 4 revisions
2009-03-02: received
See all versions
Short URL
Creative Commons Attribution


      author = {Sugata Gangopadhyay and Sumanta Sarkar and Ruchi Telang},
      title = {On the Lower Bounds of the Second Order  Nonlinearity of some Boolean Functions},
      howpublished = {Cryptology ePrint Archive, Paper 2009/094},
      year = {2009},
      note = {\url{}},
      url = {}
Note: In order to protect the privacy of readers, does not use cookies or embedded third party content.