譙通旭,申 兵,吉慶兵,王 堅,張文政

(中國電子科技集團(tuán)公司第三十研究所,四川成都610041)

函數(shù)全局雪崩特征的推廣*

譙通旭,申 兵,吉慶兵,王 堅,張文政

(中國電子科技集團(tuán)公司第三十研究所,四川成都610041)

ZHANG Xian-Mo和ZHENG Yu-liang提出單輸出布爾函數(shù)f的全局雪崩特征的概念,并且給出單輸出布爾函數(shù)雪崩特征的平方和指標(biāo)σf與絕對指標(biāo)Δf的上下界。周宇等將上面的概念作了推廣,提出了兩個單輸出布爾函數(shù)f和g全局雪崩特征的概念。他們給出了兩個函數(shù)全局雪崩特征的平方和指標(biāo)σf,g與絕對指標(biāo)Δf,g。將GF(2)變?yōu)槭Ｓ囝惌h(huán)Zq和將單輸出變?yōu)槎噍敵?可以進(jìn)一步推廣上述兩個指標(biāo)。設(shè)f和g是到的函數(shù),定義指標(biāo)ξf,g和ρf,g,給出了ξf,g和ρf,g的上界和下界。

剩余類環(huán) 移位互相關(guān) 全局雪崩特征 完全非線性

0 引 言

函數(shù)是密碼學(xué)中研究的對象之一。首先回顧函數(shù)相關(guān)免疫的發(fā)展歷史。1984年,Siegenthaler提出了單輸出布爾函數(shù)相關(guān)免疫的概念[1]。后來,他將2元域推廣為q元域,提出了從GF(q)n到GF(q)的函數(shù)相關(guān)免疫的概念[2]。再后來,單煒娟提出了多輸出布爾函數(shù)(從GF(2)n到GF(2)j)相關(guān)免疫的概念[3]?，F(xiàn)在回到函數(shù)全局雪崩特征。ZHANG Xian-mo和ZHENG Yu-liang提出了單個函數(shù)全局雪崩特征的概念[4]。它是整體上度量單個單輸出布爾函數(shù)的擴(kuò)散特性。它以研究單個函數(shù)的自相關(guān)為基礎(chǔ)。以兩個單輸出布爾函數(shù)的互相關(guān)為基礎(chǔ),周宇等提出了兩個單輸出布爾函數(shù)的全局雪崩特征[5]。與相關(guān)免疫函數(shù)的推廣相仿,一步到位,將2元域推廣為剩余類環(huán)Zq,將單輸出函數(shù)推廣為多輸出函數(shù),定義兩個指標(biāo)ξf,g和ρf,g。最后研究這兩個指標(biāo)的性質(zhì)。

1 準(zhǔn)備工作

令q是大于或等于2的整數(shù),Zq是整數(shù)模q剩余類環(huán)。設(shè),eiθ=cosθ+isinθ。。那么有下面的引理1。

設(shè)f和g是到Zq的函數(shù)。則由文獻(xiàn)[6-7]知道,它們的移位互相關(guān)定義為

稍作修改,定義移位互相關(guān)

在q和n給定時,它們只相差一個常數(shù)倍。當(dāng)q不等于2時,它為一個復(fù)數(shù)。而復(fù)數(shù)之間不好比較大小。自然而然地想到將它取模。當(dāng)f(x+w)與g完全不相關(guān),即,當(dāng)f(x+w)-g(x)=k}=qn-1對任意k成立時,。將它取模也為0,為最小,是相吻合的。當(dāng)f(x+w)與g(x)完全相關(guān),即,當(dāng)|{x| f(x+w)-g(x)=k} |=qn對某個k成立時,c(f,g)(w)=qnuk,將它取模后為qn,它為最大(因?yàn)閨c(f,g)(w)|≤qn),也是吻合的。

當(dāng)q等于2時,周宇等用(c(f,g)(w))2,也就是(w)來度量f和g的互相關(guān)性?；蛴昧硪粋€指標(biāo)|c(f,g)(w)|來度量f和g的互相關(guān)性。它們有一個特點(diǎn),當(dāng)

對任意q,令

由上面可知,當(dāng)q=2時,如果(b(w,0),b(w,1))是(b1(w,0),b1(w,1))的置換,則f和g的互相關(guān)值等于f1和g1的互相關(guān)值。當(dāng)q大于2時,希望(b1(w,0),b1(w,1),…,b1(w,q-1))為(b(w,0),b(w,1),…,b(w,q-1))的置換時,f和g的互相關(guān)值等于f1和g1的互相關(guān)值。先看一個例子。q=4,n=2時,(b(w,0),b(w,1),b(w,2),b(w,3))=(4, 5,4,3)是(b1(w,0),b1(w,1),b1(w,2),b1(w,3))= (4,5,3,4)的置換。

當(dāng)f和g是到(這里假定n≥m)的函數(shù)時,對k∈,令b(w,k)=#{x|f(x+w)-g(x)=k},作自然的推廣,用(b(w,k)-qn-m)2來度量f和g的互相關(guān)性。下面給出f和g全局雪崩特征的兩個指標(biāo)。

定義1設(shè)f和g是到的函數(shù),

定義2設(shè)f和g是到的函數(shù),

定義3如果對任何k∈,方程f(x)=k恰好有qn-m個解,則稱f是平衡函數(shù)。

定義4如果對任何w∈,w≠(0,0,…,0),f(x+w)-f(x)為平衡函數(shù),則稱函數(shù)f(x)是完全非線性的。

下一節(jié)將描述并證明主要的結(jié)果。

2 主要結(jié)果

定理10≤(b(w,k)-qn-m)2≤q2n-q2n-m,且上下界可以達(dá)到。

證明:左邊不等式顯然成立。

當(dāng)f(x)=(c1,c2,…,cm),這里c1,c2,…,cm是常數(shù),且g(x)為平衡函數(shù)時,左邊的等式成立。給定h= (h1,h2,…,hm),給定f,令g(x)=f(x+w)-h,則(b(w,k)-qn-m)2等于q2n-q2n-m,所以,上界也能達(dá)到。

推論10≤ρf,g≤。

定理20≤ξf,g≤q3n-q3n-m,且上下界可以達(dá)到。

證明:由ξf,g的定義以及定理1,不等式成立。由上面知道,當(dāng)函數(shù)f等于常向量,g(x)為平衡函數(shù)時,對任何w,(b(w,k)-qn-m)2等于0。所以,下界可以達(dá)到。但是函數(shù)f太特殊,當(dāng)n＞m時,有一個不特殊的構(gòu)造。f(x1,x2,…,xn)=(f1(x1,x2,…,xn-m),f2(x1,x2,…,xn-m),…,fm(x1,x2,…,xn-m)),這里,f1,f2,…,fm是關(guān)于x1,x2,…,xn-m的任意m個函數(shù)。g(x1,x2,…,xn)=(xn-m+1,xn-m+2,…,xn)。顯然,對任何w,k,b(w,k)=qn-m。所以,ξf,g= 0,下界能夠達(dá)到。稱a1x1+a2x2+…+anxn+b為到Zq的仿射函數(shù)。設(shè)函數(shù)f=(f1(x1,x2,…,xn),f2(x1,x2,…,xn),…,fm(x1,x2,…,xn)),這里,f1,f2,…,fm均為仿射函數(shù),c2,…,fm+cm),那么,f(x+w)-g(x)=(a1kwk-)(將它命名為k(w))。因此,對任何w,f(x+w)-g(x)=k(w)有qn個解;而f(x+w)-g(x)=k,k≠k(w),沒有解。所以,ξf,g=q3n-q3n-m,即,可達(dá)到上界。

定義5給定函數(shù)f,令ξf=ξf,f。

因?yàn)閒=g時,b((0,0,…,0),(0,0,…,0))=qn,對其它k≠(0,0,…,0),b((0,0,…,0),k)=0,所以,

顯然,有下列定理3。

定理3ξf≥q2n-q2n-m,當(dāng)且僅當(dāng)f是完全非線性函數(shù)時,等號成立。

設(shè)q=p為奇素數(shù)。由文獻(xiàn)[8]知道,x2是GF(pn)上的完全非線性函數(shù)。設(shè)α是n次不可約多項式的根,將中的(x1,x2,…,xn)映射成GF(pn)中元素x1+x2α+…+xnαn-1。設(shè)它在GF(pn)中的平方為元素y1+y2α+…+ynαn-1。定義f(x1,x2,…,xn) =(y1,y2,…,yn),則它為到的完全非線性函數(shù)。令f′(x1,x2,…,xn)=(yj1,yj2,…,yjm),這里{j1,j2,…,jm}?{1,2,…,n}。由文獻(xiàn)[7]的定理3.1知道,f′是到的完全非線性函數(shù)。由此有下列定理。

定理4存在到的函數(shù)f,滿足ξf=p2np2n-m。這里,p為奇素數(shù)。

設(shè)q為偶數(shù),q=2v。w=(w1,w2,…,wn),這里wj為0或v,j=1,2,…,n。w1,w2,…,wn不全為0。c=(c1,c2,…,cn)。這里cj為0或v,j=1,2,…,n。則w+w=(0,0,…,0),c=-c。f(x+w)-f(x)=c要么無解,要么解的個數(shù)大于或等于2。這是因?yàn)閒((x+w)+w)-f(x+w)=f(x)-f(x+w)=-c=c,且x+w≠x。因此,對2n-1個w,(b(w,k)-qn-n)2≥2n。由此得下列定理。

定理5設(shè)q為偶數(shù),f是到的函數(shù),則,ξf≥q2n-qn+(2n-1)2n。

由此定理可推出,當(dāng)q為偶數(shù)時,不存在到的完全非線性函數(shù)。

當(dāng)q為2時,由文獻(xiàn)[7]的定理3.1和定理2.3知道,從到的函數(shù)f為完全非線性,當(dāng)且僅當(dāng)對每一個c∈,c≠0,c·f(x)為bent函數(shù)。當(dāng)n為奇數(shù)時,沒有到Z2的bent函數(shù),因此,當(dāng)n為奇數(shù)時,對任何n≥m,從到的任何函數(shù)f都不是完全非線性的。結(jié)合文獻(xiàn)[7]的定理3.2的推論以及文獻(xiàn)[7]中第4節(jié)的構(gòu)造,有下列定理。

定理6①當(dāng)n為奇數(shù)時,f為從到的任何函數(shù),則ξf＞22n-22n-m。

②當(dāng)n為偶數(shù),且n≥2m,則存在從到的函數(shù)f滿足ξf=22n-22n-m。當(dāng)n為偶數(shù),且n＜2m,從到的任何函數(shù)f皆有ξf＞22n-22n-m。

3 結(jié) 語

推廣函數(shù)全局雪崩特征的兩個指標(biāo)是有原因的。將GF(2)推廣到剩余類環(huán)Zq是很有必要的,如來學(xué)嘉和Massey提出的IDEA的一個部件就用了剩余類環(huán)Zq中的運(yùn)算。并且密碼學(xué)中經(jīng)常要考慮多輸出函數(shù)。給出的兩個指標(biāo)非常簡潔,容易計算。由定義可知,如果ξf和ρf,f都很小,則能夠抗差分密碼攻擊,如果ξf和ρf,f都很大,則容易受到差分攻擊。下一步的重點(diǎn)是對特定的q,n,m,計算指標(biāo)ξf,g和ρf,g。并且計算ξf。重中之重是考慮f等于g,q等于2,且n等于m的情形。因?yàn)樗c通常的分組密碼算法相對應(yīng)。當(dāng)然,還要綜合考慮其它密碼學(xué)指標(biāo)[9-11]。

[1] SIEGENTHALER T.Correlation-Immunity of Nonlinear Combining Functions for Cryptographic Applications[J]. IEEE Transactions on Information Theory,1984,30(05): 776-780.

[2] SIEGENTHALER T.Methoden Fur Den Entwurf Von Stream Cipher System[D].Zurich,Switzerland:ADAG Administration and Durch,1986.

[3] 單煒娟.相關(guān)免疫函數(shù)的結(jié)構(gòu)與構(gòu)造及其在流密碼中的應(yīng)用[D].西安:西北電訊工程學(xué)院,1987.

SHAN Wei-juan.Structure and Construction of Correlation-Immune Functions and Their Applications in Stream Cipher[D].Xi'An:Northwest Radio Engineering University,1987.

[4] ZHANG X.M.,ZHENG Y.L.GAC-the Criterion for Global Avalanche Characteristics of Cryptographic Functions[J].Journal for Universal Computer Science,1995, 1(05):316-333.

[5] ZHOU Yu,XIE Min,XIAO Guo-zhen.On the Global Avalanche Characteristics between Two Boolean Functions and the Higher Order Nonlinearity[J].Information Sciences,2010,180(02):256-265.

[6] NYBERG K.Constructions of Bent Functions and Difference Sets[C]//Advances in Cryptology-EUROCRYPT' 90.Berlin:Springer-Verlag,1991:151-160.

[7] NYBERG K.Perfect Nonlinear S-boxes[C]//Advances in Cryptology-EUROCRYPT'91.Berlin:Springer-Verlag,1992:378-386.

[8] 郭腓望,張習(xí)勇,韓文報.一種完全非線性函數(shù)的構(gòu)造[J].山東大學(xué)學(xué)報:理學(xué)版,2011,46(03):26-30,40.

GUO Fei-wang,ZHANG Xi-yong,HAN wen-bao.A Construction of Perfect Nonlinear Functions[J].Journal of Shandong University.2011,46(3):26-30,40.

[9] 王林,譙通旭,趙偉,等.關(guān)于完全非線性函數(shù)的非線性度的界[J].信息安全與通信保密,2011(11):66-67.

WANG Lin,QIAO Tong-xu,ZHAO Wei,et al.On Nonlinearity Bounds of Perfect Nonlinear Functions[J].Information Security and Communications Privacy,2011(11):66-67.

[10] 譙通旭,祝世雄,王運(yùn)兵,等.單圈T函數(shù)序列與M序列研究[J].信息安全與通信保密,2013(01):36-39.

QIAO Tong-xu,ZHU Shi-xiong,WANG Yun-bing,et al.Study on Single-Cycle T-Function Sequences and M -Sequences[J].Information Security and Communications Privacy,2013(1):36-39.

[11] 譙通旭,王運(yùn)兵,謝上明,等.具有最大代數(shù)免疫度函數(shù)的研究[J].通信技術(shù),2013(11):86-89.

QIAO Tong-xu,WANG Yun-bing,XIE Shang-ming,et al.Study on Functions with Optimum Algebraic Immunity [J].Communications Technology,2013(11):86-89.

QIAO Tong-xu(1963—),male,B.Sci., senior engineer,mainly engaged in cryptography.

申 兵(1971—),男,碩士,高級工程師,主要研究方向?yàn)樾畔踩c通信保密;

SHEN Bing(1971—),male,M.Sci.,senior engineer,mainly engaged in information security and communications privacy.

吉慶兵(1976—),男,碩士,高級工程師,主要研究方向?yàn)槊艽a分析;

JI Qing-bing(1976—),male,M.Sci.,senior engineer, mainly engaged in cryptanalysis;

王 堅(1975—),男,碩士,高級工程師,主要研究方向?yàn)樾畔踩c通信保密;

WANG Jian(1975-),male,M.Sci.,senior engineer,mainly engaged in information security and communications privacy.

張文政(1966—),男,碩士,研究員,主要研究方向?yàn)槊艽a學(xué)及其應(yīng)用。

ZHANG Wen-zheng(1966-),male,M.Sci.,research fellow, mainly engaged in cryptography and its application.

Popularization of Function Global Avalanche Characteristics between Two Functions

QIAO Tong-xu,SHEN Bing,JI Qing-bing,WANG Jian,ZHANG Wen-zheng
(No.30 Institute of CETC,Chengdu Sichuan 610041,China)

ZHANG Xian-mo and ZHENG Yu-liang propose the notion of global avalanche characteristics of single-output Boolean functionf,and give the upper and lower bounds of the sum of squares indicatorσfand the absolute indicator Δf.ZHOU Yu et al.popularize the above notions and propose the notion of global avalanche characteristics of two single-output Boolean functionsfandg,and define the sum of squares indicatorσf,gand absolute indicator Δf,gof global avalanche characteristics of two Boolean functionfandg. By changing GF(2)into residue class ringZqand transferring single-output into multi-output,the above two indicators can be further popularized.Letfandgserve as the functions fromto,indicatorsξf,gandρf,gare defined,and the upper and lower bounds ofξf,gandρf,gare also given.

residue class ring;shifted cross-correlation;global avalanche characteristics;perfect nonlinear

TN918.1

A

1002-0802(2014)10-1203-04

10.3969/j.issn.1002-0802.2014.10.019

譙通旭(1963—),男,學(xué)士,高級工程師,主要研究方向?yàn)槊艽a學(xué);

2014-08-02;

2014-09-15 Received date：2014-08-02;Revised date：2014-09-15

國家自然科學(xué)基金(No.61309034);中國電子科技集團(tuán)公司技術(shù)創(chuàng)新基金項目(No.JJQN201332);四川省科技廳杰出青年

基金項目(No.2014JQ0055)資助

Foundation Item:National Natural Science Foundation of China(No.61309034),China Electronics Technology Group Corporation Innovative Technology Projects(No.JJQN201332),Outstanding Youth Foundation of the Science and Technology Department in Sichuan Province(No.2014JQ0055)