Nonlinearity Bounds and Constructions of Resilient Boolean Functions
Nonlinearity Bounds and Constructions of Resilient Boolean Functions
复制标题
DOI：
10.1007/3-540-44598-6_32
复制
发表时间：
2000-08
期刊：
影响因子：
--
通讯作者：
P. Sarkar;S. Maitra
中科院分区：
文献类型：
--
作者：
P. Sarkar;S. Maitra
在本文中，我们研究了布尔函数的非线性与弹性阶数之间的关系。我们首先证明了适用于弹性函数的 Reed-Muller 码的 McEliece 定理的更清晰版本，这也概括了众所周知的肖-马西特征。因此，获得了弹性函数非线性的非平凡上限。这一结果与西根塔勒不等式相结合，得出了参数之间最佳可能权衡的概念：变量数量、弹性阶数、非线性和代数度。我们进一步表明，可以通过类似 Maiorana-McFarland 的技术来构造实现最佳可能权衡的函数。我们还提供了一些以前未知的函数的构造。
In this paper we investigate the relationship between the nonlinearity and the order of resiliency of a Boolean function. We first prove a sharper version of McEliece theorem for Reed-Muller codes as applied to resilient functions, which also generalizes the well known Xiao-Massey characterization. As a consequence, a nontrivial upper bound on the nonlinearity of resilient functions is obtained. This result coupled with Siegenthaler’s inequality leads to the notion of best possible trade-off among the parameters: number of variables, order of resiliency, nonlinearity and algebraic degree. We further show that functions achieving the best possible trade-off can be constructed by the Maiorana-McFarland like technique. Also we provide constructions of some previously unknown functions.