素数元旋转对称弹性布尔函数的构造与计数

杜蛟，温巧燕，张劼，庞善起

（1. 北京邮电大学 网络与交换技术国家重点实验室，北京 100876；2. 新乡学院 数学与信息科学系，河南 新乡 453003；3. 北京邮电大学 理学院，北京 100876；4. 河南师范大学 数学与信息科学学院，河南 新乡 453007）

1 引言

在流密码和分组密码的密码系统中，所选用的布尔函数必须满足各种不同的要求，以抵抗各种已有的攻击方法，如1984年Siegenthaler提出的相关攻击[1]，要求选用的布尔函数具有相关免疫性和平衡性[1,2]（弹性）。2003年，法国的密码学家Nicolas和 Wilimeier提出了基于线性反馈移位寄存器的代数攻击方法[3]，对密码学中使用的布尔函数提出了更高的要求。近年来，代数攻击引起了密码学家们的广泛关注[4~8]。为了衡量布尔函数抵抗代数攻击的能力，Meier等人提出了代数免疫(AI, algebraic immunity)的概念[3]，由于代数免疫阶高的函数同时具有较高的代数次数和非线性度，因此，如何构造同时具有最优代数免疫性和弹性的布尔函数既是布尔函数研究领域的一个极具重要研究意义的课题，也是当前密码函数研究的热点问题。到目前为止，关于偶数元具有最优代数免疫阶的布尔函数的构造已经出现了很多研究成果[9,10]，然而关于同时具有弹性和最优代数免疫性的奇数元布尔函数的构造问题的结果至今仍然很少，一个重要的原因是到现在为止，还没有找到一个很有效的数学工具可以用来同时研究一个布尔函数的代数免疫性和弹性。

1999年，Pieprzyk和 Qu将旋转对称函数（RSBF）用于某些密码算法如 MD4、MD5和HAVAL的快速实现中[11]，RSBF一经提出就引起了密码学界的广泛关注[12~16]，近年来，关于具有最优代数免疫性或其他性质的旋转对称函数的构造已经出现了许多有价值的结果[15~18]，它是一类较对称布尔函数更大的函数类，对称布尔函数可以看成是一类特殊的旋转对称布尔函数，人们运用计算机搜索的方法发现了12个同时具有2阶弹性和最优代数免疫性的七元旋转对称布尔函数[7]，这就启示笔者从旋转对称布尔函数类中去寻找同时具有弹性和最优代数免疫性的奇数元布尔函数，为了缩小搜索空间，笔者有 2个思路：1）从已经得到的最优代数免疫的 RSBF中去寻找弹性函数；2）从已经得到的具有弹性的 RSBF类中去寻找最优代数免疫函数。如果从 1）的角度考虑去获得具有弹性的最优代数免疫函数，那么最优代数免疫的RSBF具有弹性时的性质刻画就尤为重要；如果从 2）的角度考虑去获得具有弹性的最优代数免疫函数，那么具有弹性的RSBF的构造与计数就是一个极有意义的研究课题，本文主要对素数元RSBF类具有弹性时其特征矩阵的性质进行了刻画，并且研究了素数元旋转对称的弹性布尔函数的构造与计数问题。关于RSBF的构造与计数已经有了一些结果[17,18]，但它们都不是弹性的，具有弹性的RSBF的构造与计数这一问题的解决将有效地缩小笔者搜索具有弹性最优代数免疫的RSBF空间范围。

2 基础知识

任何布尔函数 ()f x∈nB，都可以唯一地表示为如下的代数标准型（ANF）。

其中，系数 a0, a1, ⋅ ⋅ ⋅,a12⋅⋅n∈ F2，代数标准型中最高次项的次数称为 f ( x)的次数，记为deg(f( x) )。

定义 1[11]布尔函数 f ( x)称为旋转对称布尔函数（RSBF），当且仅当对于任意的输入⋅⋅⋅,xn)对0 ≤ k ≤ n -1成立。

下文中，用RSBF表示旋转对称布尔函数的缩写，用 Gn( x)表示向量x在变换下生成的轨道，即，n元RSBF的轨道个数为，其中，φ为欧拉函数，因而n元RSBF的总个数为2gn。将每个轨道Gn( x)中的元素按照字典排列法排序，将排在第一位的所有向量按照重量大小以及字典排列法依次记为其中，w表示轨道中向量的重量，i表示重量为w的轨道中的第i个轨道， gn,w表示重量为w的轨道总数，则所有重量为w的轨道可以表示为注意到两元平衡的相关免疫旋转对称布尔函数只有2个，即 f1( x1, x2) = x1+ x2和f2( x1, x2)= 1 + x1+ x2，下文中，只考虑当p满足p≥3的素数时的情形。

定义2[19]设 f ( x)是一个n元布尔函数，x ∈，若 f ( x) = 1 ，则称x为 f ( x)的一个特征向量，记 f ( x)的全体特征向量的集合为D，即：D={α|f(α)其中，w表示函数 f ( x)的Hamming重量，D称为 f ( x)的支撑集，将集合D中的向量按行排列，记第i个向量1≤i≤w，则称如下的0、1矩阵

为 f ( x)的特征矩阵，在不引起混淆的情况下简记为C。下文中不考虑特征矩阵的行置换。

布尔函数与特征矩阵是一一对应的，对布尔函数有关问题的研究等价于对布尔函数特征矩阵的研究，下文中把布尔函数的特征矩阵与该布尔函数均称为布尔函数。

定义3[19]设A是一个w行n列的矩阵，称A是一个(w, n, 2,m)正交矩阵是指A的任m列构成矩阵的行向量中，中的每个向量都出现且出现的次数相同。

定义 4[19]如果一个布尔函数 f ( x)的特征矩阵 Cf是一个(w, n, 2,m)正交矩阵，则称 f ( x)是一个m（m≥1）阶相关免疫函数，简称f( x)是相关免疫函数或 f ( x)是CI函数。

定义5[3]设 f ( x)， g ( x)∈ B，若 f ( x) g( x)n= 0 ，称 g ( x)是 f ( x)的零化子， f( x)的零化子集合记为 A N( f)， f ( x)的代数免疫阶AI(f)定义为

定义6 设 f ( x)是一个n元布尔函数，它可能满足如下的性质。

1) 平衡性：n元布尔函数 f ( x)是平衡函数，即它的输出中0和1各半。

2) 相关免疫性：n元布尔函数 f ( x)是CI函数，即它的特征矩阵是(w, n, 2,m)正交矩阵。

3) 旋转对称性：n元布尔函数 f ( x)是RSBF。

4) 最优代数免疫性：n元布尔函数 f ( x)是MAI函数。

笔者称n元布尔函数 f ( x)是一个 P(i1, i2,… ,it)函数是指 f ( x)同时满足上述的性质 1)~4)，P(1,2)函数即为弹性函数，下文中主要研究p（p为素数）元 P(1,2,3)函数的构造问题，如未特别说明，均假设p为奇素数。

3 主要结果

3.1 对p元P(3)、P(2,3)、P(1,2,3)函数特征矩阵性质的刻画

当旋转对称布尔函数 ()f x的变元个数n为不小于3的奇素数p时，其特征矩阵有什么特征呢？下面的定理给出了回答。

定理1 p元RSBF ()f x的特征矩阵总可以写成如下的4种形式。

证明 由于 p是素数，空间 Fp被分成了

2个轨道，其中，和 1p=是2个单元素轨道，其他的个轨道中都含有p个点。而每个轨道构成的特征矩阵形式为，对于任意的x∉{0 ,1 }，下面证

p p M0是一个p×p对称矩阵。设x=(x1, x2,… ,xp)，M0的第i行第 j列的元素为 mij，第 j行第i列的元素为 mji，这里1 ≤ i, j≤ p ，根据旋转对称变换的意义，可知 mij= xi+j-1(modp)，mji=xj+i-1(modp)，这就是说 mij= mji，根据对称矩阵的定义可知 M0是对称的。因而 f ( x)的特征矩阵总可以写成如上的4种形式之一。

因此，由定理 1很快可以判断文献[20]中给出构造得到的P(2,3)函数都不是P(1)函数，因为它们所得的函数具有 Cf3或者 Cf4的形式。笔者有如下的推论。

推论1 设 f ( x)是一个p元P(3)函数（ p ≥ 3 ），其特征矩阵为 Cf，则 Cf的任意2列中0和1的个数相同。

证明 由定理1可知，若 f ( x)是一个p元P(3)函数（ p ≥ 3 ），那么特征矩阵为 Cf一定可以写成上述的 Cf1、 Cf2、 Cf3或 Cf4的形式，由于 Ai， Bj，Ck， Dl都具有对称矩阵 M0的形式，因而其行向量和列向量都有相同的重量，并且都是对称的p×p方阵，因而无论 Cf是哪种形式， Cf的任意2列中0和1的个数均相同。

文献[20]通过计算也得到了与推论1相同的结论，推论1刻画了p元P(3)函数特征矩阵的一个简单性质，由此还可得如下的推论。

推论 2 p(p≥3)元 P(3)函数 f(x)是一阶 P(2)函数，当且仅当它的特征矩阵的第一列中0和1的个数相等。

证明 一方面，若 f ( x)是P(2)函数，由一阶相关免疫函数的定义可知，它的第一列中0和1的个数相等。

另一方面，对于P(3)函数 f ( x)，如果它的特征矩阵的第一列中0和1的个数相等，由推论1可知，Cf的任意2列中0和1的个数相同，那么它所有的列中0和1的个数相等，因而它是一阶P(2)函数。

文献[21]研究了 P(2)函数阶的判别方法，由上述的推论2可知，要判断一个P(3)函数是否是一阶的P(2)函数，只需要判断它的第一列中0和1的个数是否相等即可。当 f ( x)是P(1)函数时，其特征矩阵又有什么性质呢?下面的定理对这一问题做了回答。

定理 2 p元旋转对称布尔函数 f ( x)是平衡函数，那么 f ( x)特征矩阵的形式一定是定理1中的Cf1或者 Cf2的形式，并且，向量 0p和 1p有且仅有一个在 f ( x)的支撑集中。

证明 p元旋转对称布尔函数 f ( x)是平衡函数，那么 f ( x)的支撑集中一定含有长度为p的轨道个，因而向量 0p和 1p有且仅有一个在f( x)的支撑集中才能保证 f ( x)是平衡函数。也就是说平衡函数 f ( x)的特征矩阵只能是 Cf1或者Cf2的形式。

上述的定理1、定理2、推论1和推论2从不同的角度刻画了p元 P(3)函数 f ( x)特征矩阵的性质。

3.2 对文献[14,20]构造方法的改进

当变元个数n为奇素数p时，文献[14,20]给出了一类P(2,3)函数的构造方法如下。

1) 对于任意给定的1 ≤ w ≤ ( n -1)2，从重量为w的轨道中取出任意的k个（ 0 ≤ k ≤ gn,w）轨道作为矩阵 Cf的行向量。

文献[20]中还给出了上述方法构造得到的P(2,3)函数的准确计数为

假设重量依次为 w1、 w4、 n - w2、 n - w3的轨道以及满 足 1≤w1＜w2＜w3＜ w4≤(n -1)2且 w1+w4任取整数k满足0≤k≤ m in{gn,w1,gn,n-w2,gn,n-w3,gn,w4}，按照如下的方法构造函数。

定理3 上述方法得到的函数是P(2,3)函数。

证明 一方面，从 1)~5)可以看出，每次选出的都是整个轨道，因而上述方法构造的函数是P(3)函数。

另一方面，考查上述的 1)~4)步选取的行向量构成的矩阵 P1，其行数为4kn，其第一列中1的个数是 k w1+ k w4+ k ( n - w2)+ k ( n - w3)=2kn，考查 5)选取的行向量构成的矩阵 Q1，其行数为2ln，其第一列中1的个数是 lw0+ l ( n - w0)=ln，由推论1可知 P1和 Q1都是正交矩阵，若重复操作1)~4)和5)，分别得到若干个 Pi和 Qj，类似地，它们都是正交矩阵，因而所有的 Pi和 Qj（包括 P1和 Q1）一起构成的特征矩阵仍然是正交矩阵，由定义4可知，上述函数是P(2)函数。

综上所述，上述方法得到的函数是P(2,3)函数。

显然，当 1)~4)步得到的向量个数不为 0时，上述方法构造得到的函数与文献[14,20]中构造的函数是不同的，当 1)~4)步得到的向量个数为 0时，文献[14,20]的方法就是笔者方法的特例，实际上反复运用上述方法1)~5)，笔者可以得到比文献[14,20]中方法更多的P(2,3)函数。

3.3 P(1,2,3)函数的构造与精确计数

当P(3)函数是P(2)函数时，笔者对其特征矩阵的性质有了一个全面的认识，本节笔者讨论弹性的RSBF构造与计数问题。这一问题等价于从个p长轨道中选出个，加上向量0p或 1p，构成一个 2p-1⋅p的矩阵，使得该矩阵的第一列中0和1的个数相等，下文中笔者都假设向量 0p在 f ( x)的支撑集中， 1p在 1+ f( x)的支撑集中，下面笔者构造具有某些密码学性质的p元P(3)函数 f ( x)，有如下的结果。

定理4 设p元P(3)函数 f ( x)的支撑集中重量为i的轨道个数为 ni(1 ≤ i≤ p -1)，那么 f ( x)是P(1,2)函数的充要条件是如下的方程组有解。

证明 先证必要性。

首先，若 f ( x)是P(1)函数，且 0p在 f ( x)的支撑集中，而每个轨道都有p个点，因而 f ( x)的支撑集中还需要 ( 2p-1- 1 )p 个p长轨道，因而(2p-1- 1 )/p 成立；其次，要保证 f ( x)是P(2)函数，则由推论1可知它的第一列中0和1的个数相等，从而由定理2可知 f ( x)的特征矩阵一定具有定理2中 Cf1的形式，并且对应的，因而它的第一列中1的总个数必为，所以如果 f ( x)是P(1,2)函数，那么如下的方程组

再证充分性。

定理 5 如果上述方程组(1)有q组不同的解n1i,n2i,…,nqi(1 ≤ i≤ p -1)，对于上述方程组的一组解 nji（1 ≤ i≤ p-1，1≤j≤q），可以得到不同的p元 P(1,2,3)函数 f ( x)的个数为2Tj，其中，由q组解得到不同的p元P(1,2,3)函数的总个数

证明 一方面，对于方程组（1）的一组解 nji(1≤i≤6，1≤ j ≤ q )，由于 f ( x)是P(1,2)函数，nji是指 f ( x)的支撑集中重量为i的轨道个数，而重量为i的轨道总个数为，因而选择nji个重量为i的轨道（可以看成向量的集合）放入 f ( x)的支撑集中的方法有种，所以对于方程组（1）的一组解nji(1≤i≤6，1≤ j ≤ q )，可以得到的函数个数为个，这些函数的支撑集中都含有向量 0p，得到的这 Tj个函数是互不相同的，注意到当 f ( x)是 P(1,2,3)函数，那么 1+ f( x)也是 P(1,2,3)函数，因此得到的互不相同的 P(1,2,3)函数的总个数为2Tj(1≤j≤q)。

另一方面，2组不同的解 nji和 nki，这里1 ≤ j, k ≤ q，j≠k，至少存在某个i满足nji≠nki，根据方程组（1）解的含义可知，在由解 nji和 nki所得到的函数的支撑集中，重量为i的轨道数是不等的，因而由解nji和nki所得到的函数一定是不同的，所以由q组解得到不同的p元P(1,2,3)函数的总个数为

下面笔者给出几个通过求解方程组（1）来构造P(1,2,3)函数的实例。

推论3 有且仅有2个三元P(1,2,3)函数。

证明 在方程组（1）中，令p=3，上述的方程组（1）简化为，这里 0 ≤ n1, n2≤1，解这个方程组可得，再由定理5可得：一共可得到2个三元P(1,2,3)函数。

由文献[22]可知，这些函数都不是最优代数免疫函数，即不存在三元的P(1,2,3,4)函数。

推论4 有且仅有10个五元P(1,2,3)函数。

证明 在方程组（1）中，令p=5，上述的方程组（1）简化为

解这个方程组可得如下的几组解：1)n1=0，n2=1， n3=2， n4=0；2)n1=0， n2=2， n3=0， n4=1；3)n1=1， n2=0， n3=1， n4=1。

再根据定理5，对于第1组解可得函数4个，对于第2组解可得函数2个，对于第3组解可得函数4个，因而一共可以得到10个五元平衡的相关免疫旋转对称布尔函数。

推论5 有且仅有13 394个七元P(1,2,3)函数。

证明 类似地，对于七元平衡的相关免疫旋转对称布尔函数，可以按照如下的方式获得：在方程组（1）中，令p=7，方程组（1）简化为

解这个方程组可得如表1的34组不同的解，根据定理5计算得到的函数总数为13 394个，所得到的函数个数情况（函数个数共计6 697）如表1所示。

可以证明存在8个五元弹性阶为1的P(1,2,3,4)函数，计算机搜索实验表明[7]：在七元P(1,2,3)函数中，存在12个代数次数为4，弹性阶为2，非线性度为 56的 P(1,2,3,4)函数，文献[22]的研究结果表明：n（n为奇数）元最优代数免疫函数的弹性阶最大为( 3)2n- ，笔者比较关注达到弹性阶上界的这类最优代数免疫函数，实际上它们的代数次数就等于它的代数免疫阶，因而有如下的猜想。

猜想 对于奇素数n( 5)n≥ ，弹性阶为( 3)2n- 的 P(1,2,3,4)函数存在。进一步地，n( 5)n≥ 为奇数时，弹性阶为( 3)2n- 的P(1,2,3,4)函数存在。

表1 34组解以及每组解所得到的P(1,2,3)函数的个数

如表 1所示，第一列表示解的序号，ni(1≤i≤6)所在的列表示的是ni的取值，“函数个数”所在的列表示的是根据这一组解得到的支撑集中含有的函数个数，例如：在表1的第一行中，组号1表示的是第一组解，1右边ni(1≤i≤6)下边的数值就是第一组解n1=0，n2=0， n3=4， n4=5， n5=0， n6=0；在这组解中：n1=0的意义是重量为1的轨道选取0个， n2=0的意义是重量为2的轨道选取0个， n3=4的意义是重量为3的轨道选取4个（重量为3的轨道一共有5个），n4=5的意义是重量为4的轨道选取5个（重量为4的轨道一共有5个）， n5=0的意义是重量为5的轨道选取0个，n6=0的意义是重量为6的轨道选取 0个，函数的个数“5”是这组解根据定理 5的方法计算出的支撑集中含有的函数个数，下面的类似。

4 结束语

本文首先改进了文献[20]中关于奇素数元P(2,3)函数的构造方法，提出了一种更一般的构造；然后通过对具有某些密码学性质的旋转对称布尔函数特征矩阵性质的研究，给出了满足多个密码学性质RSBF的构造与计数；通过解定理4中的方程组（1）的整数解完全确定了素数元 P(1,2,3)函数的构造方案以及这类函数的精确计数问题；其次给出了三元、五元、七元 P(1,2,3)函数的构造与计数；最后笔者还给出了一个猜想。

[1] SIEGENTHALER T. Correlation-immunity of nonlinear combining functions for cryptographic applications[J]. IEEE Transactions on Information Theory, 1984, 30(5):776-780.

[2] FILIOL E, FONTAINE C. Highly nonlinear balanced Boolean functions with good correlation immunity[A]. Advances in Cryptology-EUROCRYPT’98[C]. Espoo, Finland, 1998. 475-488.

[3] COURTOIS N, MEIER W. Algebraic attacks on stream ciphers with linear feedback[A]. Biham Eed Advances in Cryptology- EUROCRYPT 2003[C]. Warsaw, Poland, 2003.346-359.

[4] CANTEAUT A. Open problems related to algebraic attacks on stream ciphers[A]. WCC2005[C]. Bergen, Norway, 2006.120-134.

[5] DALAI D, MAITRA S, SARKAR S. Basic theory in construction of Boolean functions with maximum possible annihilator immunity[J].Des Code Crypt, 2006, 40(1):41-58.

[6] BRAEKEN A, PRENEEL B. On the algebraic immunity of symmetric Boolean functions[A]. IndoCRYPT[C]. Bangalore, India, 2005. 35-48 .

[7] CARLET C, DALAI D K, GUPTA K C, et al. Algebraic immunity for cryptographically significant Boolean functions: analysis and construction[J]. IEEE Transactions on Information Theory, 2006, 52(7): 3105-3121.

[8] DALAI D K, MAITRA S. Reducing the number of homogeneous linear equations in finding annihilators[EB/OL]. http://eprint.iacr.org/2006/032.

[9] TU Z, DENG Y. A conjecture about binary strings and its applications on constructing Boolean functions with optimal algebraic immunity[J].Designs, Codes and Cryptography, 60(2011):1-14.

[10] TU Z, DENG Y. Boolean functions optimizing most of the cryptographic criteria[J]. Discrete Applied Mathematics(2011), 2011, 160(4-5): 427-435.

[11] PIEPRZYK J, QU C X. Fast hashing and rotation symmetric functions[J]. Journal Universal Computer Science, 1999, 5(1):20-31.

[12] STANICA P, MAITRA S. Rotation symmetric Boolean functions count and cryptographic properties[J]. Discrete Applied Mathematics,2008, 156(10):1567-1580.

[13] CUSICK W, STANICA P, MAITRA S. Fast evaluation, weight and nonlinearity of rotation symmetric functions[J]. Discrete Mathematics,2002, 258(1-3):289-301.

[14] STANICA P, MAITRA S, CLARK J. Results on rotation symmetric bent and correlation immune Boolean functions[A]. Fast Software Encryption Workshop (FSE 2004)[C]. New Delhi, India, 2004.161-177.

[15] SARKAR S, MAITRA S. Construction of rotation symmetric Boolean functions with maximum algebraic immunity on odd number of variables[A]. AAECC 2007[C]. Bangalore, India, 2007. 271-280.

[16] FU S J, LI C, MATSUURA K, et al. Construction of rotation symmetric Boolean functions with maximum algebraic immunity[A]. CANS 2009[C]. Kanazawa, Japan, 2009. 402-419.

[17] STANICA P, MAITRA S. A constructive count of rotation symmetric functions[J]. Information Processing Letters, 2003, 88(6):299-304.

[18] FU S J, LI C, QU L, et al. On the number of rotation symmetric functions over GF(p)[J]. Mathematical and Computer Modelling, 2012, 55(1-2): 142-150.

[19] 温巧燕，钮心忻，杨义先. 现代密码学中的布尔函数[M]. 北京:科学出版社, 2000.WEN Q Y, NIU X X, YANG Y X. The Boolean Functions in Modern Cryptology[M]. Beijing: Science Press, 2000.

[20] 王永娟，韩文报，李世取. 满足CI的RotS函数的构造与计数[J]. 通信学报, 2007, 28(11A):6-9.WANG Y J, HAN W B, LI S Q. Construction and numeration of correlation immunity RotS Boolean function[J]. Journal on Communications, 2007, 28(11A):6-9.

[21] 庞善起，杜蛟，席金彦. 相关免疫函数阶的判别方法[J]. 应用数学学报，2009, 32(3):445-453.PANG S Q, DU J, XI J Y. Some methods for judging the order of correlation-immune functions[J]. Acta Mathematicae Applicacatae Sinica,2009, 32(3):445-453.

[22] 杜蛟，温巧燕，张劼等. 五元1阶弹性函数的代数免疫阶[J]. 通信学报, 2011, 32(4):17-24.DU J, WEN Q Y, ZHANG J, et al. On the algebraic immunity for 1st-resilience Boolean functions with five pvariables[J]. Journal on Communications, 2011, 32(4):17-24.