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

Sugata Gangopadhyay, Sumanta Sarkar, and 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.

Available format(s)
Category
Secret-key cryptography
Publication info
Published elsewhere. Unknown where it was published
Keywords
Boolean functionssecond order nonlinearity
Contact author(s)
gsugata @ gmail com
History
2009-03-17: last of 4 revisions
See all versions
Short URL
https://ia.cr/2009/094

CC BY

BibTeX

@misc{cryptoeprint:2009/094,
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{https://eprint.iacr.org/2009/094}},
url = {https://eprint.iacr.org/2009/094}
}

Note: In order to protect the privacy of readers, eprint.iacr.org does not use cookies or embedded third party content.