摘要：本文介紹了在容錯分布、量子密碼學(xué)中的密鑰分配以及流密碼中的隨機序列產(chǎn)生等領(lǐng)域都有著廣泛應(yīng)用的一類多輸出布爾函數(shù)——彈性函數(shù)。彈性函數(shù)和0，1上多維空間的正交分劃(一個正交矩陣組)是一致的。在此基礎(chǔ)上，介紹了彈性函數(shù)的正交分劃的遞歸構(gòu)造方法和簡單計數(shù)。

關(guān)鍵詞：彈性函數(shù)；相關(guān)免疫函數(shù)；正交矩陣；計數(shù)

中圖分類號：TN911文獻(xiàn)標(biāo)識碼：A文章編號：1009-3044(2008)16-21353-03

Review of Resilient Functions of Modern Cryptography

SUN Jing-jing， WANG Yun

(School of Mathematics，Huaibei Coal Industry Teachers College，Huaibei 235000，China)

Abstract:Constrction of resilient functions that some possible applications of which involve the fault-tolerant distributed computing， quantum-cryptographic key distribution，and random sequence generation for stream ciphers are introduced.Recurive construction and enumeration of resilient functions are introduced.

Key words:resilient functions;correlation-immune functions;orthogonal array;enumeration

1 引言

彈性函數(shù)首先由B.chor等和C.H.Bennett等提出并研究。這類函數(shù)可用于容錯分布計算、量子密碼學(xué)中的密鑰分配，以及流密碼中隨機序列的產(chǎn)生。相關(guān)免疫函數(shù)是由 提出的一類抵抗相關(guān)攻擊的重要的密碼函數(shù)，而彈性函數(shù)實際上就是無偏的多輸出相關(guān)免疫函數(shù)。

2 定義及引理

定義1. 記F(x)=(f1(x)，f2(x)，…fm(x))，其中f1，…fm為F2n→F2m的布爾函數(shù)，則F:F2n→F2m，稱F為多輸出布爾函數(shù)。

對于多輸出布爾函數(shù)F，定義其非線性度為■的代數(shù)次數(shù)定義為■。這里■。

定義2. 設(shè)F(x)是GF(2)n→GF(2)m的函數(shù)，若對任意的β∈GF(2)m，F(xiàn)-1(β)={x∣F(x)= β}有相同的元素個數(shù)，則稱F(x)是無偏的。

著名的XOD引理揭示了多輸出函數(shù)和其分量函數(shù)之間的關(guān)系。

引理1. (XOD引理) 設(shè)F(x)=(f1(x)，f2(x)，…fm(x))是F2n→F2m的函數(shù)，其中fi（1≤i≤m）是F2n→F2的函數(shù)，F(xiàn)(x)是無偏的■f1(x)， f2(x)，…fm(x)的任意非零線性組合是平衡的。

定義3. 設(shè)有 平衡函數(shù)F:F2m→F2n，其中1≤m≤n. 如果對任意的下標(biāo)集{j1，j2，…jt∈}{1，2，…n}，對任意a{a1，a2，…at}∈GF(2)t，任意b∈GF(2)m，有■，即當(dāng)任意t個輸入固定，而其余n-t個輸入跑遍所有2n-t個輸入串時，F(xiàn)以相同的次數(shù)取到所有可能的輸出m元串。如果F是(n，mt)彈性函數(shù)，但不是(n，m，t+1)彈性函數(shù)，則稱F的彈性階為t。

顯然，彈性函數(shù)即為無偏的相關(guān)免疫函數(shù)。

引理2. 設(shè)F(x)=(f1(x)，f2(x)，…fm(x))是F2n→F2m的函數(shù)，其中fi(1≤i≤m)是F2n→F2的函數(shù)，F(xiàn)(x)是(n，m，t)彈性函數(shù)■f1(x)， f2(x)，…fm(x)的任意非零線性組合是(n，1，t)彈性函數(shù)。

3 彈性函數(shù)的構(gòu)造

文獻(xiàn)5~7中重點討論了彈性函數(shù)的構(gòu)造，主要為由線性彈性函數(shù)構(gòu)造高非線性度的非線性彈性函數(shù)。其主要方法是借助線性碼構(gòu)造成一些線性函數(shù)或借助線性碼理論從已有的彈性函數(shù)構(gòu)造新的彈性函數(shù)（這些函數(shù)是線性的或代數(shù)次數(shù)較低的），然后再通過置換或無偏多輸出函數(shù)復(fù)合出代數(shù)次數(shù)較高的函數(shù)。 那么，如何構(gòu)造一些彈性函數(shù)做為基礎(chǔ)，下面介紹其中一種——正交分劃的遞歸構(gòu)造法。這種方法直觀簡單，便于實現(xiàn)。

定義4. 設(shè) 是GF(2)上的w×n矩陣，1≤t≤n，如果對任意給定的t列，每一個行向量a∈F2t恰好重復(fù)w/2t次，則稱A為正交矩陣，記為(w，n，2，t).

定理1. 布爾函數(shù)f(x1，x2，…xn)是t階相關(guān)免疫函數(shù)■其特征矩陣為(w，n2，t)正交矩陣(w為f(x)的漢明重量)。

定義5. 設(shè)A1，A2，…Ak均是GF(2)上的(w，n2，t)正交矩陣，若GF(2)n的每個向量必且只在一個Ai(1≤i≤k)的行中出現(xiàn)，即Ai(1≤i≤k)的行互不相交，且■，則稱A1，A2，…Ak是GF(2)n的一個t正交分劃，這時■。

定理2. 設(shè)F(x)是F2n→F2m上的無偏的t階相關(guān)免疫函數(shù)，即F(x)是t階彈性函數(shù)■Aβ1，…，Aβ2m是GF(2)n的一個t正交分劃，其中Aβ1={x∣F(x)=β1}，βi∈GF(2m)， 1≤i≤2m。

根據(jù)定理2，構(gòu)造t彈性函數(shù)等價于構(gòu)造GF(2)n的一個t正交分劃。

引理3. 設(shè)A，B都是w×n矩陣，若A，B都是(w，n，2，t)正交矩陣，則■是(2w，n+1，2，t)正交矩陣。

引理4. 設(shè)A是2n-1×n矩陣，若A是(2n-1，n，2，t)正交矩陣，則■是(2n，n+1，2，t+1)正交矩陣。其中A-表示GF(2)n中除A的向量以外的向量組成的矩陣。

引理5. 設(shè)A，B是w×n矩陣，若A，B都是(w，n，2，t)正交矩陣，且A，B無相同行，則■亦無相同行，且都是(2w，n+1，2，t)正交矩陣.

定理3. 對任意的t≥1，m≥1，GF(2mt+1)可寫成分塊形式：■，Ci是(2mt+1，mt+1，2，t)正交矩陣，1≤i≤2m。 即GF(2mt+1)有t正交分劃C1，C2，…C2m。

定理4. 對任意的■有t-正交分劃。

證明：由條件知mt+1≤n，若mt+1=n，由定理3即得證。

若mt+1

C11，C21，…C2m1都是(2mt-m+2，mt+2，2，t)正交矩陣，則C11，C21，…C2m1是GF(2)mt+2的t-正交分劃.對任意1≤k≤n-(mt+1)，令

■.C1k，C2k，…，C2mk是GF(2)mt+k+1的t-正交分劃.重復(fù)以上過程，當(dāng)k=n-(mt+1)時就得GF(2)n到的一個正交分劃C1*，C2*，…，C2m*。

定理4的構(gòu)造性證明實際上給出了正交分劃的一個遞歸構(gòu)造方法.相應(yīng)的就構(gòu)造出了一個GF(2)n→GF(2)m的t-彈性函數(shù).

4 彈性函數(shù)的計數(shù)

設(shè)A1，A2…A2m是GF(2)n的一個t-正交分劃. 對x∈Ai∩GF(2)n，令F(x)=βi，

βi ∈GF(2)m，則GF(2)n→GF(2)m是的t-彈性函數(shù). 顯然，交換f(x)在Ai(1≤i≤2m)Ai上的取值得到的t-彈性函數(shù)是不同的. 所以，有一個t-正交分劃，相應(yīng)可得到2m！個t-彈性函數(shù).所以，可以通過討論正交分劃的個數(shù)來推導(dǎo)出彈性函數(shù)的個數(shù).

設(shè)A1，A2，…A2m是GF(2)n的一個t-正交分劃，n≥m≥1，這些2n×m×n矩陣都是t-正交矩陣，從而2t∣2n-m，故t≤n-m，由于t的大小刻畫了函數(shù)抗信息泄露能力的大小，所以我們希望盡可能的大. 但當(dāng)達(dá)到最大值，即t=n-m時，(n，m，t)彈性函數(shù)的個數(shù)將會受到很大限制.

我們用Nt(2t，n)記t-正交的2t×n矩陣的個數(shù)，用N(n，m，t)記(n，m，t)彈性函數(shù)的個數(shù)(此時t=n-m)。

定理5. 設(shè)t≥2，則■

即t-正交的2t×n矩陣，當(dāng)n=t時有 個，n=t+1時有2個，其余情況為0個.

由前述，存在(n，m，t)彈性函數(shù)，則存在GF(2)n的t-正交分劃A1，A2，…A2m，這些Ai(1≤i≤2m 是t-正交的2n-m×n矩陣，當(dāng)t=n-m時成為t-正交的2t×n矩陣，由定理5可知，t-正交的2t×n矩陣僅當(dāng)n=t+1存在，且只有 個：A1，A2（即m=1）。所以，t=n-m時，GF(2)n僅有一個t-正交分劃：A1，A2，從而只有2m！=21！=2個(n，m，t)彈性函數(shù)，于是有

定理6. 對任意n≥m≥1，t≥2，滿足t=n-m的(n，m，t)彈性函數(shù)只有2個.這時n=t+1，m=1.即為布爾函數(shù)。

推論1. 平衡的n+1元n階相關(guān)免疫函數(shù)只有2個.

推論2. m≥2，n-m≥2時GF(2)n→GF(2)m，的多輸出函數(shù)(m≥2)的彈性性t不能達(dá)到最大值n-m。

定理7. 設(shè)n≥m≥1，用N(n，m，t)記(n，m，t)彈性函數(shù)的個數(shù)，若t=n-m，則

1）當(dāng)t=0時，N(n，m，t)=2n！。

2）當(dāng)t=1時，N(n，m，t)=2n-1！。

3）當(dāng)t≥2時，N(n，m，t)=2。

以上結(jié)果表明，t=n-m時，即彈性性能最佳的函數(shù)除m=n和m=n-1這些特殊情況外太少。彈性性t是衡量抗信息泄露能力大小的一個重要指標(biāo)，若這樣的函數(shù)個數(shù)太少其應(yīng)用將受到很大限制。當(dāng)t最大時，函數(shù)個數(shù)很少且都是線性函數(shù)，所以并不是t越大越好。所以，不能片面追求高彈性性。密碼系統(tǒng)中使用的函數(shù)個數(shù)不能太少。因此，研究彈性函數(shù)的計數(shù)是一個很重要的課題。

參考文獻(xiàn)：

[1] ChorB，GoldreichO，astad J H，F(xiàn)riedman J，Rudich S，Smolensky R.The bit extraction problem or t-resilient functions[A].in Proc 26th IEEE Symp.Foundations of Computer Science[C].1985，26: 396-407.

[2] Bennett C H， Brassard G， Robert J M. Privacy amplification by public discussion[J].SIAM J. Comput， 1988， 17(2): 210-229.

[3] Rueppel R A.Analysis and design of stream ciphers[M].Berlin Germany: Springer-verlag，1996.

[4] Siegenthaler.Correlation immunity of nonlinear combining functions for cryptographic[J].IEEE Trans Inform. Theory， 1984.IT-30 sept，776-779.

[5] ZHANG Xiao-mo，ZHANG Yu liang. Cryptographically resilient functions[J].IEEE Trans Inform Theory， 1997，43:1740-1747

[6] ZHANG Xiao-mo，ZHANG Yu-liang. On nonlinear resilient functions[A].In Advance in cryptology- Eurocrypt' 95C .Berlin: spring –verlag，1996，274-290.

[7] CHEN Lu-sheng， FU Fang-wei. On the constructions of new resilient functions from old ones[J].IEEE Trans Inform Theory， 1999，45(6):2 077-2082.

[8] 溫巧燕，楊義先.彈性函數(shù)的遞歸構(gòu)造[J].北京郵電大學(xué)學(xué)報，2002，25(2):1007-5321(2002)02-0047-05.

[9] 溫巧燕， 楊義先.彈性函數(shù)的計數(shù)[J].北京郵電大學(xué)學(xué)報， 2002， 25(4):1007-5321，(2002)04-0021-05.

[10] 溫巧燕，鈕心忻，楊義先.現(xiàn)代密碼學(xué)中的布爾函數(shù).北京:科學(xué)出版社，2000.

注：本文中所涉及到的圖表、注解、公式等內(nèi)容請以PDF格式閱讀原文。