一類密碼函數(shù)的構造與分析

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

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

1 引言

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

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

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

2 預備知識

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

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

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

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

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

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

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

引理2[15,19]

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

3 級聯(lián)布爾函數(shù)G(x, y)的密碼學性質

3.1 基函數(shù)與G(x, y)的Walsh循環(huán)譜關系

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

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

引理5 矩陣 At可逆，且

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

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

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

3.3 G(x, y)的擴散性

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

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

滿足嚴格雪崩準則。

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

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

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

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

122

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

2或，則都是r階Plateaued函數(shù)。

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

是r階Plateaued函數(shù)，故G是r+2階Plateaued函數(shù)。

4 基函數(shù)與構造的多輸出布爾函數(shù)的關系

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

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

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

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

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

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

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

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

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

5 結束語

通過級聯(lián)t+1個n元布爾函數(shù)構造了n+t元布爾函數(shù) (,)Gxy，將對G(x,y)與基函數(shù)的關系研究轉化為對Krawtchouk多項式和Krawtchouk矩陣的研究，得到了彼此間循環(huán)譜的相互表達式。分析了G(x,y)的相關免疫性、擴散性和代數(shù)免疫性。當t=2時，分析了該類函數(shù)與基函數(shù)作為 Plateaued 函數(shù)的依賴關系。同時將上述構造方法推廣到多輸出布爾函數(shù)，通過級聯(lián)t+1個(n, s+1)多輸出布爾函數(shù)的分量函數(shù)，構造了一類(n+t, s+1)多輸出布爾函數(shù)H(x,y)。同樣利用Krawtchouk矩陣給出了該類函數(shù)的廣義Walsh循環(huán)譜與基函數(shù)的廣義Walsh循環(huán)譜之間的相互表達式。分析了H(x,y)的相關免疫性和代數(shù)免疫性。對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] 何業(yè)鋒, 馬文平. 3類 semi-Bent函數(shù)的構造[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] 謝佳, 王天擇. 尋找布爾函數(shù)的零化子[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 函數(shù)的密碼學性質[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] 王維瓊, 周宇, 肖國鎮(zhèn). Plateaued函數(shù)的正規(guī)性[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] 孫光洪, 武傳坤. 級聯(lián)函數(shù)的密碼學性質[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] 王秋艷, 金晨輝. 多輸出布爾函數(shù)與布爾函數(shù)代數(shù)免疫階之間的關系[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 函數(shù)的密碼學性質[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] 丁存生, 肖國鎮(zhèn). 流密碼學及其應用[M]. 國防工業(yè)出版社, 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.