一類密碼函數的構造與分析

歐智慧，趙亞群,2，李旭

(1. 信息工程大學 四院，河南 鄭州 450002；2. 數學工程與先進計算國家重點實驗室，河南 鄭州 450002)

1 引言

密碼函數包括布爾函數和多輸出布爾函數，它們是構成密碼系統的重要組件。特別是在密碼算法的非線性實現方面有著重要的應用，在序列密碼中，密碼函數多用于非線性反饋函數和非線性組合函數環節，在分組密碼中多用于實現混亂作用的S盒。因此，對密碼函數的研究是分析密碼算法的基礎性工作，具有十分重要的意義，國內外這方面的研究工作有許多[1~6]。因此，在密碼函數的研究中，構造具有良好密碼學性質的密碼函數十分重要。由于密碼函數的各個準則間具有一定的制約關系，構造具有良好密碼學性質的密碼函數并不容易。Bent函數是一類具有最大非線性度的布爾函數，在抵抗線性攻擊方面十分優越，但它有不平衡性、不具有相關免疫性等缺點。2001年，Zheng等[7]提出Plateaued函數的概念，它是一類比Bent函數更廣的布爾函數，具有很好的非線性度，可以滿足相關免疫性、平衡性，而且可以不具有非零的線性結構，近年來已成為密碼工作者研究的熱點之一[8~11]。密碼函數的各項刻畫指標多是應對某種具體的密碼攻擊而提出的，例如，布爾函數的相關免疫性主要是針對相關攻擊提出的，希望布爾函數具有較好的相關免疫性，布爾函數的代數免疫階主要是針對代數攻擊提出的，希望布爾函數具有較高的代數免疫階。級聯構造是一種常用的重要構造方法，形如的布爾函數，就是一種常見的級聯構造。通過分析 f (x)和g(x)的密碼學性質，得到 h (x,xn+1)的性質。反之，通過分析 h (x,xn+1)的性質，也有利于掌握 f (x)和g(x)的性質。

由于密碼算法的設計中更多的是涉及多輸出布爾函數，因此，在布爾函數研究相對成熟的基礎上，各種研究向多輸出布爾函數擴展。一方面，相關概念被推廣到多輸出布爾函數，如：相關函數、相關免疫性、擴散性、代數免疫性等，進而研究多輸出布爾函數的此類性質及具有良好性質的多輸出布爾函數的構造。另一方面，布爾函數與多輸出布爾函數的關系也是研究的一個重要方面。由于多輸出布爾函數的復雜性，關于它的研究，雖然國內外學者也做了不少工作[12~14]，總的來說相關研究并不像布爾函數那么成熟，因此還需做更深入的研究。

孫光洪等[11]通過級聯構造了一類布爾函數，詳細討論了此類函數的密碼學性質，指出當 f1(x)、 f2(x)、 f3(x)具有較好性質時，f 也具有較好的性質。受文獻[11]工作的啟發，通過級聯t+1個n 元布爾函數，筆者構造了 n+t元布爾函數 G(x,y)，它是文獻[11]工作的一般情況。以 Krawtchouk多項式[15]和Krawtchouk矩陣[16]為工具，給出了基函數和G(x,y)譜的確定關系，從而將對 G(x,y)的研究轉化為對Krawtchouk多項式和 Krawtchouk矩陣的研究。分析了 G(x,y)的相關免疫性、擴散性和代數免疫性，指出在基函數性質較好的情況下，G(x,y)也具有較好的密碼學性質。在特殊情況下，作為Plateaued函數，分析了基函數與G(x,y)的依賴關系。同時，更進一步將構造方法推廣到多輸出布爾函數，構造了一類多輸出布爾函數 H(x,y)，分析了H(x,y)的相關免疫性和代數免疫性。

2 預備知識

記二元域 F ={ 0,1}，n是一正整數，以 Fn表示22n個 F2的笛卡爾積，稱 F2n到 F2的任一映射 f (?)為n個變元的(Fn上的)布爾函數，即：若記2，則記x的漢明重量為(其中，#S表示集合S中元素的個數)，下面先給出一些基本定義和引理。

定義1[1]設 w ,x ∈F2n，x和w的點積定義為wx設f(x)為Fn2上的布爾函數， w ∈F2n，稱為f(x)的Walsh循環譜。

定義2[1]設 f (x)是 Fn2上的布爾函數，如果對任意的，稱f(x)為m階相關免疫的(m階彈性的)。

定義3[1]設 f1(x)，f2(x)是 Fn2上的布爾函數， s∈F2n， 稱為f1(x)和 f2(x)在點 s的互相關系數；稱為 f1(x)在點s的自相關系數。

定義4[1]設 f (x)是 Fn上的布爾函數，稱 f (x)2滿足嚴格雪崩準則(m階擴散準則)，當且僅當

定義5[17]設 f (x)是 Fn上的布爾函數2如果對任意的，則稱f(x)為r階Plateaued函數。

引理1[18]設f(x)是 F2n上的布爾函數，則

引理2[15,19]

引理3[19]對于，有，其中，當i=j時,當i≠j時，δi,j= 0 ，稱為Krawtchouk多項式的正交性。

3 級聯布爾函數G(x, y)的密碼學性質

3.1 基函數與G(x, y)的Walsh循環譜關系

下面的引理4和引理6從正反2個方面反映了G(x,y)與其基函數的關系，是考察G(x,y)的密碼性質與該性質與其基函數密碼學性質關系的基礎。

證明 對 s =(α,β)，可得

引理5 矩陣 At可逆，且

由引理4及引理5，易得下面的引理6。它是引理4的反演公式。

3.2 G(x, y)的相關免疫性

利用引理2的3)可得定理1和定理2。定理1是引理4的一個應用，這說明在一定條件下，基函數相關免疫性好時 G(x,y)相關免疫性也較好，這為構造高階相關免疫函數提供了可能。定理2是引理6的一個應用，說明 G(x,y)相關免疫性較好時基函數相關免疫性也較好。

3.3 G(x, y)的擴散性

下面的引理7是分析G(x,y)的擴散性的基礎，為方便，記

由引理7及推論4可得下面的定理3，它表明在一定條件下G(x,y)滿足嚴格雪崩準則。

滿足嚴格雪崩準則。

3.4 G(x, y)的代數免疫階

對于 n元布爾函數 f (x)，如果存在布爾函數g(x)使得 f (x)g(x) = 0 ，稱 g (x)為 f (x)的零化子。稱 f (x)和 f (x)+1的非零零化子的最小代數次數為f(x)的代數免疫階，記為 A I(f)。

另一方面，設h(x,y)為達到G(x,y)代數免疫階的布爾函數，則 h(x,y)可表示成如下形式：，其中，為i的二進制表示。如果，則即，取代入上述等式可得，其中，i的二進制表示為；如果同樣取，則其中，i的二進制表示為由題設條件知又由，其中

3.5 t=2時G(x, y)的性質

122

2) G是r階Plateaued函數，對任意 u ∈Fn，

2或，則都是r階Plateaued函數。

4) 對任意 u ∈Fn，若2，代入式(1)得；若，代入式(1)得且，又由于

是r階Plateaued函數，故G是r+2階Plateaued函數。

4 基函數與構造的多輸出布爾函數的關系

本節將上述構造推廣到多輸出布爾函數上，先引入一些基本的定義與結論。

設m，n為正整數且m≤n，稱F2n到F2m的任一映射為 (n, m)多輸出布爾函數，其中，是Fn2上的布爾函數。

定義 6[1]設 F(x)為(n, m)多輸出布爾函數，，稱為F(x)的廣義Walsh循環譜。

定義7[1]設F(x)為(n, m)多輸出布爾函數，，隨機向量如果對任意的及有uz與統計獨立，則稱多輸出函數 F (x)是k級j階相關免疫的。

定義8[20]設F(x)為(n, m)多輸出布爾函數，給定輸出，若存在n元布爾函數Fy(x)使得任意都有，則稱 F (x)為輸出y的y狀態函數。記 A Iy(F)為輸出非零狀態函數的代數次數的最小值，當輸出y遍歷時，稱 A Iy(F)的最小值為多輸出布爾函數F(x)的代數免疫階，記為 A I(F )。

引理8[1]設F(x)為(n, m)多輸出布爾函數，則F(x)是 k級 j階相關免疫的充要條件是對任意的及有

類似于引理4和引理6，可以得到下面的引理9和引理10，它們是互為反演的。

利用上面的 2個引理可以方便地討論基函數與H(x,y)的相互關系，從而構造密碼學性質好的多輸出布爾函數。作為應用，給出下面的定理6和定理7。

定理6 若任意 Fi(x)是k級j階相關免疫的，，對于u ∈ F2s+1及任意的，有，則H(x,y)是k級j階相關免疫的。

5 結束語

通過級聯t+1個n元布爾函數構造了n+t元布爾函數 (,)Gxy，將對G(x,y)與基函數的關系研究轉化為對Krawtchouk多項式和Krawtchouk矩陣的研究，得到了彼此間循環譜的相互表達式。分析了G(x,y)的相關免疫性、擴散性和代數免疫性。當t=2時，分析了該類函數與基函數作為 Plateaued 函數的依賴關系。同時將上述構造方法推廣到多輸出布爾函數，通過級聯t+1個(n, s+1)多輸出布爾函數的分量函數，構造了一類(n+t, s+1)多輸出布爾函數H(x,y)。同樣利用Krawtchouk矩陣給出了該類函數的廣義Walsh循環譜與基函數的廣義Walsh循環譜之間的相互表達式。分析了H(x,y)的相關免疫性和代數免疫性。對Krawtchouk多項式和Krawtchouk矩陣的深入研究是進一步分析 G(x,y)和 H(x,y)密碼學性質的基礎。

[1] 馮登國.頻譜理論及其在密碼學中的應用[M]. 北京: 科學出版社,2000.FENG D G. Sectrum Theory and the Application in Cryptography[M].Beijing: Publishing Company of Science, 2000.

[2] 何業鋒, 馬文平. 3類 semi-Bent函數的構造[J]. 電子學報, 2011,39(1):233-236.HE Y F, MA W P. Constructions of three classes of semi-Bent functions[J]. Chinese Journal of Electronics, 2011, 39(1):233-236.

[3] 謝佳, 王天擇. 尋找布爾函數的零化子[J].電子學報, 2010, 38(11):2686-2690.XIE J, WANG T Z. Finding the annihilators of a Boolean function[J].Chinese Journal of Electronics, 2010, 38(11):2686-2690.

[4] HU B, JIN C H, SHAO Z Y. Relationship among three kinds of cryptographic Boolean functions with special Walsh spectrum[J]. Journal on Communications, 2010, 31(7):104-109.

[5] MEIER W, PASALIC E, CARLET C. Algebraic attacks and decomposition of Boolean functions[A]. Advances in Cryptology-Eurocrypt 2004[C]. Berlin, Germany, 2004. 474-491.

[6] CLAUDE C. Relating three nonlinearity parameters of vectorial functions and building APN functions from bent functions[J]. Des Codes Cryptogr, 2011, 59(1-3):89-109.

[7] ZHENG Y, ZHANG X M. On Plateaued functions[J]. IEEE Transactions on Information Theory, 2001, 47(3):1215-1223.

[8] 胡斌, 金晨輝, 馮春海. Plateaued 函數的密碼學性質[J]. 電子與信息學報, 2008, 30(3): 660-664.HU B, JING C H, FENG C M. Cryptographic properties of Plateaued functions[J]. Journal of Electronics & Information Technology, 2008,30(3):660-664.

[9] 王維瓊, 周宇, 肖國鎮. Plateaued函數的正規性[J]. 電子與信息學報, 2008, 30(9): 2283-2286.WANG W Q , ZHOU Y, XIAO G Z. Normality of Plateaued functions[J]. Journal of Electronics & Information Technology, 2008,30(9):2283-2286.

[10] CARLET C, PROUF E. On Plateaued functions and their constructions[A].Fast Software Encryption 2003[C]. Lund, Sweden, 2887. 54-73.

[11] 孫光洪, 武傳坤. 級聯函數的密碼學性質[J]. 電子學報, 2009, 37(4):884-888.SUN G H, WU C K. Some cryptographic properties of Boolean functions by concatenation[J]. Chinese Journal of Electronics, 2009, 37(4):884-888.

[12] YING D H, ZHAO Y Q, FENG D G. Correlation functions of mulioutput m-valued logical functions and relation between correlation functions and spectra[J]. Zhengzhou Univ NatSci.Ed, 2007,39(2):21-24.

[13] 王秋艷, 金晨輝. 多輸出布爾函數與布爾函數代數免疫階之間的關系[J]. 電子學報, 2011, 39(1):124-127.WANG Q Y, JIN C H. Relationship between the algebraic immunity of multi-output Boolean functions and Boolean functions[J]. Chinese Journal of Electronics, 2011, 39(1):124-127.

[14] 胡斌, 金晨輝, 史建紅. 多輸出 Plateaued 函數的密碼學性質[J].電子與信息學報, 2009, 31(6):1433-1437.HU B, JIN C H, SHI J H. Cryptographic properties of multi-output Plateaued functions[J]. Journal of Electronics & Information Technology, 2009, 31(6):1433-1437.

[15] MACWILLIAMS F J, SLOANE N J. The Theory of Error-Correcting Codes[M]. North Holland: Elsevier, 1977.

[16] FEINSILVER P, KOCIK J. Krawtchouk matrices from classical and quantum random walks[J]. Contemporary Mathematics, 2007, 287(2001):83-96.

[17] CARLET C. Partially-bent functions[J]. Des Codes Cryptogr, 1993,3(2):135-145.

[18] 丁存生, 肖國鎮. 流密碼學及其應用[M]. 國防工業出版社, 1994.DING C S, XIAO G Z. Stream Cipher and Its Applications[M]. National Defence Industry Press, 1994.

[19] KRASIKOV I, LITSYN S. On integral zeros of krawtchouk polynomials[J]. Journal of Combinatorial Theory, 1996, 74(1):71-99.

[20] FISCHER S, MEIER W. Algebraic immunity of S-boxes and augmented functions[A]. Advances in FSE 2007[C]. Berlin, Germany,2007. 366-381.