郑　东,严宏超,赵庆兰

(西安邮电大学 通信与信息工程学院， 陕西 西安 710121)

布尔函数在密码学[1]中具有广泛应用[2-5]，可以作为流密码的非线性组件[4]以及分组密码的S-盒[6]中的核心组件。

bent函数[7]是Walsh谱取值为±2n/2的一类布尔函数，与仿射函数集合具有最大汉明距离，能够有效抵抗线性攻击和最佳仿射逼近攻击。旋转对称(rotation symmetric boolean functions,RotS)布尔函数[5]也称为幂等函数[8]，当输入向量循环左移时其输出值保持不变。利用RotS布尔函数可实现Message Digest系列中的杂凑压缩算法，还可进行快速Walsh变换[9]。

当变元数n=2m,且m/gcd (m,t)是奇数时(1≤t≤m-1)，可构造出一类二次和三次旋转对称bent函数ft(x)[4,10]。代数次数从2到m的2m元旋转对称bent函数的构造[11]，首次将旋转对称bent函数的代数次数提高至大于3。通过修改代数次数较低的旋转对称bent函数，也可得到两类代数次数为d(3≤d≤m)的旋转对称bent函数[12]。

本文将在文献[4，12]的基础上，深究旋转对称bent函数的性质和构造，给出一个Maiorana-McFarland类[13]函数，并证明该函数为旋转对称bent函数。当变元数n=2m(m∈+)为偶数时，所给新函数的代数次数可达m。

1　基础知识

任一n元布尔函数f均可以用其代数正规型(algebraic normal form,ANF)唯一表示为

(1)

其中，向量

α=(α0,α1,…,αn-1),x=(x0,x1,…,xn-1)，

的系数取值。

定义向量x的支撑集为

supp(x)={i:xi=1}。

其中所含元素“1”的个数称为向量x的汉明重量，记为w(x)。布尔函数f(x)的支撑集定义为

其中所含元素“1”的个数称为函数f(x)的汉明重量，记为w(f)。任意的两个布尔函数f(x)和g(x)的汉明距离满足

dH(f,g)=w(f+g)。

如果布尔函数的f(x)汉明重量w(f)=2n-1，则称该布尔函数是平衡的。

(2)

布尔函数f(x)的代数次数是其代数正规型中系数非零的单项式的最大变元个数，记为