Cryptology ePrint Archive: Report 2018/1159

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 ]