互补对称布尔函数的非线性度

J4 ›› 2011, Vol. 33 ›› Issue (10): 51-56.

互补对称布尔函数的非线性度

陈银冬1,陆佩忠2

(1.汕头大学工学院计算机系,广东汕头 515063;2.复旦大学计算机科学技术学院,上海 200433)

收稿日期:2011-05-15 修回日期:2011-07-20 出版日期:2011-10-25 发布日期:2011-10-25

The Nonlinearity of Complementary Symmetric Boolean Functions

CHEN Yindong1,LU Peizhong2

(1.Department of Computer Science,Shantou University,Shantou 515063;2.School of Computer Science,Fudan University,Shanghai 200433,China)

Received:2011-05-15 Revised:2011-07-20 Online:2011-10-25 Published:2011-10-25

摘要/Abstract

摘要：

互补对称布尔函数是一类特殊的对称布尔函数。在所有代数免疫最优的对称布尔函数中，有相当的比例均属此类函数。特别是当变元数量为2〖WTBX〗m〖WTBZ〗元时，有2/3比例的代数免疫最优对称布尔函数都是互补对称布尔函数。通过布尔函数非线性度、Walsh谱和Krawtchouk多项式间的关系，计算出互补对称布尔函数的非线性度。结果表明，任意n元互补对称布尔函数的非线性度为2n－1－ 1/2(nn/2)。

关键词: 非线性度, 代数免疫度, 互补对称布尔函数, 对称布尔函数

Abstract:

Complementary symmetric Boolean functions are a special class of symmetric Boolean functions. A high proportion of symmetric Boolean functions with optimum algebraic immunity are complementary symmetric Boolean functions. Especially for the case of 2〖WTBX〗m〖WTBZ〗 variables, it reaches a high proportion of 2/3. By the relationship between the nonlinearity and the Walsh spectrum of the Boolean functions, and that between the Walsh spectrum of the Boolean functions and the Krawtchouk polynomial, the nonlinearity of complementary symmetric Boolean functions is determined. As a result, the nonlinearity of all complementary symmetric Boolean functions with n variables is2n－1－ 1/2(nn/2)。

Key words: nonlinearity;algebraic immunity;complementary symmetric Boolean function;symmetric Boolean function

陈银冬1,陆佩忠2. 互补对称布尔函数的非线性度[J]. J4, 2011, 33(10): 51-56.

CHEN Yindong1,LU Peizhong2. The Nonlinearity of Complementary Symmetric Boolean Functions[J]. J4, 2011, 33(10): 51-56.