Improved Upper Bound on the Nonlinearity of High Order Correlation Immune Functions
Improved Upper Bound on the Nonlinearity of High Order Correlation Immune Functions
复制标题
DOI：
10.1007/3-540-44983-3_19
复制
发表时间：
2000-08
期刊：
影响因子：
--
通讯作者：
Yuliang Zheng;Xian-Mo Zhang
中科院分区：
文献类型：
--
作者：
Yuliang Zheng;Xian-Mo Zhang
当m> 1/2n- 1时，n元m阶相关免疫函数f的非线性度Nf满足Nf ≤ 2n-1- 2 m的条件;当m> 1/2n- 2且f是平衡函数时，非线性度Nf满足Nf ≤2n-1- 2 m +1.本文证明了一般不等式Nf ≤ 2n-1- 2 m可以从≥ 0.6n- 0.4改进为Nf ≤ 2n-1- 2 m +1，而与函数的平衡无关。我们还表明，相关免疫函数实现这些功能的最大非线性有密切的关系与平台功能。后者具有许多密码学上所需的属性。
It has recently been shown that whenm> 1/2n- 1, the nonlinearityNfof anmth-order correlation immune functionfwithnvariables satisfies the condition ofNf≤ 2n-1- 2m, and that whenm> 1/2n- 2 andfis a balanced function, the nonlinearity satisfiesNf≤2n-1- 2m+1. In this work we prove that the general inequality, namelyNf≤ 2n-1- 2m, can be improved toNf≤ 2n-1- 2m+1form≥ 0.6n- 0.4, regardless of the balance of the function. We also show that correlation immune functions achieving the maximum nonlinearity for these functions have close relationships with plateaued functions. The latter have a number of cryptographically desirable properties.