Paper 2010/009

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

Xuelian Li, 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)$.

Metadata
Available format(s)
PDF
Category
Secret-key cryptography
Publication info
Published elsewhere. This paper has not been published elsewhere.
Keywords
cryptographyderivativethe second nonlinearitytrace functionquadratic form
Contact author(s)
xuelian202 @ 163 com
History
2010-01-12: received
Short URL
https://ia.cr/2010/009
License
Creative Commons Attribution
CC BY

BibTeX

@misc{cryptoeprint:2010/009,
      author = {Xuelian Li and Yupu Hu and Juntao Gao},
      title = {The Lower Bounds on the Second Order Nonlinearity of Cubic Boolean Functions},
      howpublished = {Cryptology ePrint Archive, Paper 2010/009},
      year = {2010},
      note = {\url{https://eprint.iacr.org/2010/009}},
      url = {https://eprint.iacr.org/2010/009}
}
Note: In order to protect the privacy of readers, eprint.iacr.org does not use cookies or embedded third party content.