杜蛟，溫巧燕，張劼，龐善起

（1. 北京郵電大學 網絡與交換技術國家重點實驗室，北京 100876；2. 新鄉(xiāng)學院 數學與信息科學系，河南 新鄉(xiāng) 453003；3. 北京郵電大學 理學院，北京 100876；4. 河南師范大學 數學與信息科學學院，河南 新鄉(xiāng) 453007）

1 引言

在流密碼和分組密碼的密碼系統中，所選用的布爾函數必須滿足各種不同的要求，以抵抗各種已有的攻擊方法，如1984年Siegenthaler提出的相關攻擊[1]，要求選用的布爾函數具有相關免疫性和平衡性[1,2]（彈性）。2003年，法國的密碼學家Nicolas和 Wilimeier提出了基于線性反饋移位寄存器的代數攻擊方法[3]，對密碼學中使用的布爾函數提出了更高的要求。近年來，代數攻擊引起了密碼學家們的廣泛關注[4~8]。為了衡量布爾函數抵抗代數攻擊的能力，Meier等人提出了代數免疫(AI, algebraic immunity)的概念[3]，由于代數免疫階高的函數同時具有較高的代數次數和非線性度，因此，如何構造同時具有最優(yōu)代數免疫性和彈性的布爾函數既是布爾函數研究領域的一個極具重要研究意義的課題，也是當前密碼函數研究的熱點問題。到目前為止，關于偶數元具有最優(yōu)代數免疫階的布爾函數的構造已經出現了很多研究成果[9,10]，然而關于同時具有彈性和最優(yōu)代數免疫性的奇數元布爾函數的構造問題的結果至今仍然很少，一個重要的原因是到現在為止，還沒有找到一個很有效的數學工具可以用來同時研究一個布爾函數的代數免疫性和彈性。

1999年，Pieprzyk和 Qu將旋轉對稱函數（RSBF）用于某些密碼算法如 MD4、MD5和HAVAL的快速實現中[11]，RSBF一經提出就引起了密碼學界的廣泛關注[12~16]，近年來，關于具有最優(yōu)代數免疫性或其他性質的旋轉對稱函數的構造已經出現了許多有價值的結果[15~18]，它是一類較對稱布爾函數更大的函數類，對稱布爾函數可以看成是一類特殊的旋轉對稱布爾函數，人們運用計算機搜索的方法發(fā)現了12個同時具有2階彈性和最優(yōu)代數免疫性的七元旋轉對稱布爾函數[7]，這就啟示筆者從旋轉對稱布爾函數類中去尋找同時具有彈性和最優(yōu)代數免疫性的奇數元布爾函數，為了縮小搜索空間，筆者有 2個思路：1）從已經得到的最優(yōu)代數免疫的 RSBF中去尋找彈性函數；2）從已經得到的具有彈性的 RSBF類中去尋找最優(yōu)代數免疫函數。如果從 1）的角度考慮去獲得具有彈性的最優(yōu)代數免疫函數，那么最優(yōu)代數免疫的RSBF具有彈性時的性質刻畫就尤為重要；如果從 2）的角度考慮去獲得具有彈性的最優(yōu)代數免疫函數，那么具有彈性的RSBF的構造與計數就是一個極有意義的研究課題，本文主要對素數元RSBF類具有彈性時其特征矩陣的性質進行了刻畫，并且研究了素數元旋轉對稱的彈性布爾函數的構造與計數問題。關于RSBF的構造與計數已經有了一些結果[17,18]，但它們都不是彈性的，具有彈性的RSBF的構造與計數這一問題的解決將有效地縮小筆者搜索具有彈性最優(yōu)代數免疫的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) 最優(yōu)代數免疫性：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)函數時，筆者對其特征矩陣的性質有了一個全面的認識，本節(jié)筆者討論彈性的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]可知，這些函數都不是最優(yōu)代數免疫函數，即不存在三元的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為奇數）元最優(yōu)代數免疫函數的彈性階最大為( 3)2n- ，筆者比較關注達到彈性階上界的這類最優(yōu)代數免疫函數，實際上它們的代數次數就等于它的代數免疫階，因而有如下的猜想。

猜想 對于奇素數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.