Nonlinearity and Propagation Characteristics of Balanced Boolean Functions
Nonlinearity and Propagation Characteristics of Balanced Boolean Functions
复制标题
DOI：
10.1006/inco.1995.1073
复制
发表时间：
1995-05
期刊：
影响因子：
--
通讯作者：
J. Seberry;Xian-Mo Zhang;Yuliang Zheng
中科院分区：
文献类型：
--
作者：
J. Seberry;Xian-Mo Zhang;Yuliang Zheng
摘要布尔函数密码学强的三个重要准则是平衡性、非线性和传播准则。本文的主要贡献是揭示了一些有趣的性质的平衡和非线性，并研究系统的方法来构建布尔函数，满足部分或全部的三个标准。我们表明，连接，分裂，修改，乘法（在克罗内克意义上）序列可以产生平衡的布尔函数具有非常高的非线性。特别是，我们表明，平衡布尔函数通过修改和乘序列实现的非线性度高于任何以前已知的建设方法。我们还提出了构建平衡的布尔函数，是高度非线性的，满足严格雪崩准则（SAC）的方法。此外，我们提出的方法来构建高度非线性平衡布尔函数满足传播准则，但所有的一个或三个向量。一种技术的发展，以这样的方式，构造的函数满足传播准则的高度，同时保持平衡和非线性的功能，不满足传播准则的矢量进行变换。讨论了所构造函数的代数次数。
Abstract Three important criteria for cryptographically strong Boolean functions are balance, nonlinearity, and the propagation criterion. The main contributions of this paper are to reveal a number of interesting properties of balance and nonlinearity, and to study systematic methods for constructing Boolean functions that satisfy some or all of the three criteria. We show that concatenating, splitting, modifying, and multiplying (in the sense of Kronecker) sequences can yield balanced Boolean functions with a very high nonlinearity. In particular, we show that balanced Boolean functions obtained by modifying and multiplying sequences achieve a nonlinearity higher than that attainable by any previously known construction method. We also present methods for constructing balanced Boolean functions that are highly nonlinear and satisfy the strict avalanche criterion (SAC). Furthermore we present methods for constructing highly nonlinear balanced Boolean functions satisfying the propagation criterion with respect to all but one or three vectors. A technique is developed to transform the vectors where the propagation criterion is not satisfied in such a way that the functions constructed satisfy the propagation criterion of high degree while preserving the balance and nonlinearity of the functions. The algebraic degrees of functions constructed are also discussed.