具有线性结构的弹性函数非线性度的新上界

New Upper Bound on Nonlinearity of Resilient Function with Linear Structure

讨论了具有线性结构的弹性函数的两个指标:沃什谱和非线性度,得到了具有线性结构的布尔函数的一些性质。利用沃尔什变换和汉明重量的方法,发现了:如果V是n元布尔函数f(x)的线性结构,那么得到f(x)的沃尔什变换在Fn2\V⊥或V⊥为零这一事实,同时得到了一个布尔函数没有k(k≥0)维线性结构的充分条件。最后,利用以上结果推出了具有线性结构的弹性函数的非线性度的上界表达式。

The two criteria were discussed： the Walsh spectral and the nonlinearity of resilient functions with a linear structure,some properties of Boolean functions with linear structure were presented. By the methods of Walsh transform and Hamming weight,the fact that the Walsh transform of Boolean functions f（x） with n variables are zero with respect to F2^n／V^⊥ or V^⊥, if V is a linear structure of f（x）, was found. A sufficient condition was derived to determine whether a Boolean function has no a linear structure with dimension k（k≥0） or not. Finally, a new upper bound on nonlinearity of a resilient function with linear structure was deduced by using these results.