Paper 2018/1159

Improved upper bound on root number of linearized polynomials and its application to nonlinearity estimation of Boolean functions

Sihem Mesnager, Kwang Ho Kim, and Myong Song Jo

Abstract

To determine the dimension of null space of any given linearized polynomial is one of vital problems in finite field theory, with concern to design of modern symmetric cryptosystems. But, the known general theory for this task is much far from giving the exact dimension when applied to a specific linearized polynomial. The first contribution of this paper is to give a better general method to get more precise upper bound on the root number of any given linearized polynomial. We anticipate this result would be applied as a useful tool in many research branches of finite field and cryptography. Really we apply this result to get tighter estimations of the lower bounds on the second order nonlinearities of general cubic Boolean functions, which has been being an active research problem during the past decade, with many examples showing great improvements. Furthermore, this paper shows that by studying the distribution of radicals of derivatives of a given Boolean functions one can get a better lower bound of the second-order nonlinearity, through an example of the monomial Boolean function $g_{\mu}=Tr(\mu x^{2^{2r}+2^r+1})$ over any finite field $GF{n}$.

Note: The list of references was not compiled.

Metadata
Available format(s)
PDF
Publication info
Preprint. MINOR revision.
Keywords
Boolean FunctionsNonlinearityLinearized PolynomialRoot Number
Contact author(s)
smesnager @ univ-paris8 fr
History
2018-12-04: last of 2 revisions
2018-12-03: received
See all versions
Short URL
https://ia.cr/2018/1159
License
Creative Commons Attribution
CC BY

BibTeX

@misc{cryptoeprint:2018/1159,
      author = {Sihem Mesnager and Kwang Ho Kim and Myong Song Jo},
      title = {Improved upper bound on root number of linearized polynomials and its application to nonlinearity estimation of Boolean functions},
      howpublished = {Cryptology ePrint Archive, Paper 2018/1159},
      year = {2018},
      note = {\url{https://eprint.iacr.org/2018/1159}},
      url = {https://eprint.iacr.org/2018/1159}
}
Note: In order to protect the privacy of readers, eprint.iacr.org does not use cookies or embedded third party content.