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

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

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

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

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

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

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

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

0 引 言

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

1 準備工作

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

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

稍作修改,定義移位互相關

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

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

對任意q,令

由上面可知,當q=2時,如果(b(w,0),b(w,1))是(b1(w,0),b1(w,1))的置換,則f和g的互相關值等于f1和g1的互相關值。當q大于2時,希望(b1(w,0),b1(w,1),…,b1(w,q-1))為(b(w,0),b(w,1),…,b(w,q-1))的置換時,f和g的互相關值等于f1和g1的互相關值。先看一個例子。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)的置換。

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

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

定義2設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é)將描述并證明主要的結果。

2 主要結果

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

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

當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,所以,上界也能達到。

推論10≤ρf,g≤。

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

證明:由ξf,g的定義以及定理1,不等式成立。由上面知道,當函數(shù)f等于常向量,g(x)為平衡函數(shù)時,對任何w,(b(w,k)-qn-m)2等于0。所以,下界可以達到。但是函數(shù)f太特殊,當n＞m時,有一個不特殊的構造。f(x1,x2,…,xn)=(f1(x1,x2,…,xn-m),f2(x1,x2,…,xn-m),…,fm(x1,x2,…,xn-m)),這里,f1,f2,…,fm是關于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,下界能夠達到。稱a1x1+a2x2+…+anxn+b為到Zq的仿射函數(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,即,可達到上界。

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

因為f=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,當且僅當f是完全非線性函數(shù)時,等號成立。

設q=p為奇素數(shù)。由文獻[8]知道,x2是GF(pn)上的完全非線性函數(shù)。設α是n次不可約多項式的根,將中的(x1,x2,…,xn)映射成GF(pn)中元素x1+x2α+…+xnαn-1。設它在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}。由文獻[7]的定理3.1知道,f′是到的完全非線性函數(shù)。由此有下列定理。

定理4存在到的函數(shù)f,滿足ξf=p2np2n-m。這里,p為奇素數(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。這是因為f((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設q為偶數(shù),f是到的函數(shù),則,ξf≥q2n-qn+(2n-1)2n。

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

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

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

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

3 結 語

推廣函數(shù)全局雪崩特征的兩個指標是有原因的。將GF(2)推廣到剩余類環(huán)Zq是很有必要的,如來學嘉和Massey提出的IDEA的一個部件就用了剩余類環(huán)Zq中的運算。并且密碼學中經(jīng)常要考慮多輸出函數(shù)。給出的兩個指標非常簡潔,容易計算。由定義可知,如果ξf和ρf,f都很小,則能夠抗差分密碼攻擊,如果ξf和ρf,f都很大,則容易受到差分攻擊。下一步的重點是對特定的q,n,m,計算指標ξf,g和ρf,g。并且計算ξf。重中之重是考慮f等于g,q等于2,且n等于m的情形。因為它與通常的分組密碼算法相對應。當然,還要綜合考慮其它密碼學指標[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] 單煒娟.相關免疫函數(shù)的結構與構造及其在流密碼中的應用[D].西安:西北電訊工程學院,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] 郭腓望,張習勇,韓文報.一種完全非線性函數(shù)的構造[J].山東大學學報:理學版,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] 王林,譙通旭,趙偉,等.關于完全非線性函數(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] 譙通旭,祝世雄,王運兵,等.單圈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] 譙通旭,王運兵,謝上明,等.具有最大代數(shù)免疫度函數(shù)的研究[J].通信技術,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—),男,碩士,高級工程師,主要研究方向為信息安全與通信保密;

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

吉慶兵(1976—),男,碩士,高級工程師,主要研究方向為密碼分析;

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

王 堅(1975—),男,碩士,高級工程師,主要研究方向為信息安全與通信保密;

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

張文政(1966—),男,碩士,研究員,主要研究方向為密碼學及其應用。

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—),男,學士,高級工程師,主要研究方向為密碼學;

2014-08-02;

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

國家自然科學基金(No.61309034);中國電子科技集團公司技術創(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)