Welcome to the resource topic for 2010/009
Title:
The Lower Bounds on the Second Order Nonlinearity of Cubic Boolean Functions
Authors: Xuelian Li, Yupu Hu, 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).
ePrint: https://eprint.iacr.org/2010/009
See all topics related to this paper.
Feel free to post resources that are related to this paper below.
Example resources include: implementations, explanation materials, talks, slides, links to previous discussions on other websites.
For more information, see the rules for Resource Topics .