現代密碼學上的彈性函數綜述

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

關鍵詞：彈性函數；相關免疫函數；正交矩陣；計數

中圖分類號：TN911文獻標識碼：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 引言

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

2 定義及引理

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

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

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

著名的XOD引理揭示了多輸出函數和其分量函數之間的關系。

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

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

顯然，彈性函數即為無偏的相關免疫函數。

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

3 彈性函數的構造

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

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

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

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

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

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

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

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

引理5. 設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-正交分劃.重復以上過程，當k=n-(mt+1)時就得GF(2)n到的一個正交分劃C1*，C2*，…，C2m*。

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

4 彈性函數的計數

設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-彈性函數. 顯然，交換f(x)在Ai(1≤i≤2m)Ai上的取值得到的t-彈性函數是不同的. 所以，有一個t-正交分劃，相應可得到2m！個t-彈性函數.所以，可以通過討論正交分劃的個數來推導出彈性函數的個數.

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

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

定理5. 設t≥2，則■

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

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

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

推論1. 平衡的n+1元n階相關免疫函數只有2個.

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

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

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

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

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

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

參考文獻：

[1] ChorB，GoldreichO，astad J H，Friedman 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] 溫巧燕，楊義先.彈性函數的遞歸構造[J].北京郵電大學學報，2002，25(2):1007-5321(2002)02-0047-05.

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

[10] 溫巧燕，鈕心忻，楊義先.現代密碼學中的布爾函數.北京:科學出版社，2000.

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