International Association for Cryptologic Research

International Association
for Cryptologic Research

CryptoDB

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

Authors:
Sugata Gangopadhyay
Sumanta Sarkar
Ruchi Telang
Download:
URL: http://eprint.iacr.org/2009/094
Search ePrint
Search Google
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.
BibTeX
@misc{eprint-2009-18204,
  title={On the Lower Bounds of the Second Order  Nonlinearity of some Boolean Functions},
  booktitle={IACR Eprint archive},
  keywords={secret-key cryptography / Boolean functions, second order nonlinearity},
  url={http://eprint.iacr.org/2009/094},
  note={ gsugata@gmail.com 14305 received 24 Feb 2009, last revised 2 Mar 2009},
  author={Sugata Gangopadhyay and Sumanta Sarkar and Ruchi Telang},
  year=2009
}