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

*Sihem Mesnager and 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}$.

**Category / Keywords: **Boolean Functions, Nonlinearity, Linearized Polynomial,Root Number

**Date: **received 27 Nov 2018, last revised 3 Dec 2018

**Contact author: **smesnager at univ-paris8 fr

**Available format(s): **PDF | BibTeX Citation

**Note: **The list of references was not compiled.

**Version: **20181204:055806 (All versions of this report)

**Short URL: **ia.cr/2018/1159

[ Cryptology ePrint archive ]