兩類多輸出一階擬Bent函數(shù)的構(gòu)造

劉志高

(馬鞍山職業(yè)技術(shù)學(xué)院,安徽 馬鞍山 243031)

0 引 言

Bent函數(shù)是由Rothaus于1976年提出的一類特殊的非線性組合函數(shù)[1].它的非線性度達(dá)到最大,穩(wěn)定性強(qiáng),差分分布均勻.用于非線性組合器可以很好的抗擊最佳仿射逼近攻擊和差分分析攻擊.但Bent函數(shù)也存在著一些缺陷.如:它不具有平衡性和相關(guān)免疫性,n元Bent函數(shù)的代數(shù)次數(shù)不超過(guò)n/2,限制n為偶數(shù)等.為了彌補(bǔ)Bent函數(shù)的這些不足,為彌補(bǔ)Bent函數(shù)的這些不足,胡磊等定義了半Bent函數(shù)[2],李世取教授等提出了k階擬Bent函數(shù)的概念[3],它是包含Bent函數(shù)和半Bent函數(shù)的更大的函數(shù)類.它可以具有Bent函數(shù)所不具有的密碼學(xué)性質(zhì),如:平衡性、擴(kuò)散性、相關(guān)免疫性等.隨后,人們對(duì)擬Bent函數(shù)作出了一系列的研究成果[4-9].這些研究表明,擬Bent函數(shù)是一類密碼學(xué)性質(zhì)良好的布爾函數(shù),在密碼設(shè)計(jì)及通信領(lǐng)域中有著廣泛的應(yīng)用.

分組密碼的核心部件S-盒的設(shè)計(jì)中,常常采用具有多個(gè)良好密碼學(xué)性質(zhì)的多輸出布爾函數(shù).如何構(gòu)造具有多種良好密碼學(xué)性質(zhì)的多輸出布爾函數(shù)至為關(guān)鍵.人們?cè)谘芯慷噍敵龊瘮?shù)時(shí),總希望所選取的多輸出函數(shù)的某些線性組合譜的絕對(duì)值盡可能均勻.僅就這一點(diǎn)而言,多輸出Bent函數(shù)無(wú)疑就是最佳待選函數(shù).但多輸出Bent函數(shù)不可避免地帶有Bent函數(shù)所固有的一些缺陷,如:非平衡性,相關(guān)免疫階為零,其代數(shù)次數(shù)不超過(guò)變?cè)獢?shù)目n的一半,限制n為偶數(shù)等等.多輸出擬Bent函數(shù)[10]可以彌補(bǔ)多輸出Bent函數(shù)的這些不足,且具有多種良好的密碼學(xué)性質(zhì),可廣泛地應(yīng)用于多輸出前饋網(wǎng),分組密碼的S-盒設(shè)計(jì)等領(lǐng)域.

本文給出了兩類多輸出一階擬Bent函數(shù)的構(gòu)造方法,其中一類是平衡的,另一類是具有相關(guān)免疫性的.它們可廣泛應(yīng)用于分組密碼的S-盒設(shè)計(jì)和最佳信號(hào)設(shè)計(jì)等領(lǐng)域.

1 基本定義

易知,對(duì)于固定的u,S(f)(u,v)就是布爾函數(shù)u·f(x)的一階Walsh循環(huán)譜,即S(f)(u,v)=S(u·f)(v).

將此定義推廣到多輸出函數(shù)情形即得如下定義:

特別地,當(dāng)k=0時(shí),上述f(x)即為多輸出Bent函數(shù).當(dāng)k=1時(shí),上述f(x)即為多輸出半Bent函數(shù)[12].

由定義3易得如下結(jié)論:

結(jié)論1n元m輸出函數(shù)f(x)是多輸出k階擬Bent函數(shù)的必要條件是n與k奇偶性相同.

2 一類平衡多輸出一階擬Bent函數(shù)的構(gòu)造

文獻(xiàn)[2]給出了一類半Bent函數(shù)的構(gòu)造方法,具體如下:

設(shè)n是奇數(shù),n=2k-1,構(gòu)造n元半Bent函數(shù)如下:

令f(X)=τ(X1)X2=τ1(X1)xk+τ2(X1)xk+1+…+τk(X1)x2k-1

(1)

引理3[2]由(1)式定義的f(X)是n元半Bent函數(shù),并且

其中,W=(W1,W2),W1=(w1,…,wk-1),W2=(wk,wk+1,…,wn).

基于引理3,筆者于文獻(xiàn)[12]中給出了一類多輸出半Bent函數(shù)的構(gòu)造方法,具體如下:

一般地,多輸出一階擬Bent函數(shù)不一定是平衡函數(shù).下面將給出一類平衡多輸出一階擬Bent函數(shù)的構(gòu)造方法.

定理1 設(shè)f(X)是按引理4的方法所構(gòu)造的多輸出一階擬Bent函數(shù),則它為平衡函數(shù)的充要條件是對(duì)任意的1≤i1≤i2≤…≤ij≤m,矩陣Ei1⊕Ei2⊕…⊕Eij中均不存在全0的行向量.

3 一類具有相關(guān)免疫性的多輸出一階擬Bent函數(shù)的構(gòu)造

定理2 設(shè)f(X)是按引理4的方法所構(gòu)造的多輸出一階擬Bent函數(shù),則它具有m級(jí)l階相關(guān)免疫性的充要條件是對(duì)任意的1≤i1≤i2≤…≤ij≤m,矩陣Ei1⊕Ei2⊕…⊕Eij的任意行向量中1的個(gè)數(shù)均大于l.

參考文獻(xiàn):

[1]Rothaus O S.On Bent Functions [J].Journal of Combinatorial Theory:Series A,1976,20:300-305.

[2]胡磊,裴定一,馮登國(guó).一類bent函數(shù)的構(gòu)造[J].中國(guó)科學(xué)院研究生院學(xué)報(bào),2002,19(2):103-106.

[3]李世取,劉文芬,滕吉紅.k階擬Bent函數(shù)的性質(zhì)及其應(yīng)用[C]//謝仁宏.第7屆全國(guó)青年通信學(xué)術(shù)會(huì)議論文集.北京:電子工業(yè)出版社,2001:939-943.

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

[5]滕吉紅,李世取,劉文芬.k階擬Bent函數(shù)在密碼設(shè)計(jì)和通信中的應(yīng)用[J].通信學(xué)報(bào),2003,24(12):58-66.

[6]滕吉紅,張文英,李世取,等.一類k階擬Bent函數(shù)密碼性質(zhì)的矩陣特征[J].計(jì)算機(jī)學(xué)報(bào),2004,27(4):543-547.

[7]張習(xí)勇,韓文報(bào).擬Bent函數(shù)的性質(zhì)和構(gòu)造[J].數(shù)學(xué)學(xué)報(bào),2004,47(6):1175-1184.

[8]何軍,張建中.一類k階擬Bent函數(shù)的構(gòu)造[J].陜西師范大學(xué)學(xué)報(bào):自然科學(xué)版,2005,33(3):18-20.

[9]胡斌金,晨輝,馮春海.Plateaued函數(shù)的密碼學(xué)性質(zhì)[J].電子與信息學(xué)報(bào),2008,30(3):660-664.

[10]胡斌金,晨輝,史建紅.多輸出Plateaued函數(shù)的密碼學(xué)性質(zhì)[J].電子與信息學(xué)報(bào),2009,31(6):1433-1437.

[11]馮登國(guó).頻譜理論及其在密碼學(xué)中的應(yīng)用[M].北京:科學(xué)出版社,2000:95-132.

[12]劉志高,張福泰,徐倩.一類多輸出bent函數(shù)的構(gòu)造[J].南京師范大學(xué)學(xué)報(bào):工程技術(shù)版,2005,5(2):46-49.

[13]Pieprzyk J,Finkelstein G.Towards Effective Nonlinear Cryptosystem Design[C]//IEEE Proceedings,Part E: Computers and Digital Techniques.1998,135:325-335.

[14]劉志高,張福泰,徐倩.一類多輸出半bent函數(shù)的構(gòu)造及其密碼學(xué)性質(zhì)[J].南京師范大學(xué)學(xué)報(bào):工程技術(shù)版,2006,6(1):38-42.