函数全局雪崩特征的推广*

谯通旭,申 兵,吉庆兵,王 坚,张文政

(中国电子科技集团公司第三十研究所,四川成都610041)

函数全局雪崩特征的推广*

谯通旭,申 兵,吉庆兵,王 坚,张文政

(中国电子科技集团公司第三十研究所,四川成都610041)

ZHANG Xian-Mo和ZHENG Yu-liang提出单输出布尔函数f的全局雪崩特征的概念,并且给出单输出布尔函数雪崩特征的平方和指标σf与绝对指标Δf的上下界。周宇等将上面的概念作了推广,提出了两个单输出布尔函数f和g全局雪崩特征的概念。他们给出了两个函数全局雪崩特征的平方和指标σf,g与绝对指标Δf,g。将GF(2)变为剩余类环Zq和将单输出变为多输出,可以进一步推广上述两个指标。设f和g是到的函数,定义指标ξf,g和ρf,g,给出了ξf,g和ρf,g的上界和下界。

剩余类环 移位互相关 全局雪崩特征 完全非线性

0 引 言

函数是密码学中研究的对象之一。首先回顾函数相关免疫的发展历史。1984年,Siegenthaler提出了单输出布尔函数相关免疫的概念[1]。后来,他将2元域推广为q元域,提出了从GF(q)n到GF(q)的函数相关免疫的概念[2]。再后来,单炜娟提出了多输出布尔函数(从GF(2)n到GF(2)j)相关免疫的概念[3]。现在回到函数全局雪崩特征。ZHANG Xian-mo和ZHENG Yu-liang提出了单个函数全局雪崩特征的概念[4]。它是整体上度量单个单输出布尔函数的扩散特性。它以研究单个函数的自相关为基础。以两个单输出布尔函数的互相关为基础,周宇等提出了两个单输出布尔函数的全局雪崩特征[5]。与相关免疫函数的推广相仿,一步到位,将2元域推广为剩余类环Zq,将单输出函数推广为多输出函数,定义两个指标ξf,g和ρf,g。最后研究这两个指标的性质。

1 准备工作

令q是大于或等于2的整数,Zq是整数模q剩余类环。设,eiθ=cosθ+isinθ。。那么有下面的引理1。

设f和g是到Zq的函数。则由文献[6-7]知道,它们的移位互相关定义为

稍作修改,定义移位互相关

在q和n给定时,它们只相差一个常数倍。当q不等于2时,它为一个复数。而复数之间不好比较大小。自然而然地想到将它取模。当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)的函数时,对k∈,令b(w,k)=#{x|f(x+w)-g(x)=k},作自然的推广,用(b(w,k)-qn-m)2来度量f和g的互相关性。下面给出f和g全局雪崩特征的两个指标。

定义1设f和g是到的函数,

定义2设f和g是到的函数,

定义3如果对任何k∈,方程f(x)=k恰好有qn-m个解,则称f是平衡函数。

定义4如果对任何w∈,w≠(0,0,…,0),f(x+w)-f(x)为平衡函数,则称函数f(x)是完全非线性的。

下一节将描述并证明主要的结果。

2 主要结果

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

证明:左边不等式显然成立。

当f(x)=(c1,c2,…,cm),这里c1,c2,…,cm是常数,且g(x)为平衡函数时,左边的等式成立。给定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,不等式成立。由上面知道,当函数f等于常向量,g(x)为平衡函数时,对任何w,(b(w,k)-qn-m)2等于0。所以,下界可以达到。但是函数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个函数。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的仿射函数。设函数f=(f1(x1,x2,…,xn),f2(x1,x2,…,xn),…,fm(x1,x2,…,xn)),这里,f1,f2,…,fm均为仿射函数,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给定函数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是完全非线性函数时,等号成立。

设q=p为奇素数。由文献[8]知道,x2是GF(pn)上的完全非线性函数。设α是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),则它为到的完全非线性函数。令f′(x1,x2,…,xn)=(yj1,yj2,…,yjm),这里{j1,j2,…,jm}⊆{1,2,…,n}。由文献[7]的定理3.1知道,f′是到的完全非线性函数。由此有下列定理。

定理4存在到的函数f,满足ξf=p2np2n-m。这里,p为奇素数。

设q为偶数,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要么无解,要么解的个数大于或等于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为偶数,f是到的函数,则,ξf≥q2n-qn+(2n-1)2n。

由此定理可推出,当q为偶数时,不存在到的完全非线性函数。

当q为2时,由文献[7]的定理3.1和定理2.3知道,从到的函数f为完全非线性,当且仅当对每一个c∈,c≠0,c·f(x)为bent函数。当n为奇数时,没有到Z2的bent函数,因此,当n为奇数时,对任何n≥m,从到的任何函数f都不是完全非线性的。结合文献[7]的定理3.2的推论以及文献[7]中第4节的构造,有下列定理。

定理6①当n为奇数时,f为从到的任何函数,则ξf＞22n-22n-m。

②当n为偶数,且n≥2m,则存在从到的函数f满足ξf=22n-22n-m。当n为偶数,且n＜2m,从到的任何函数f皆有ξf＞22n-22n-m。

3 结 语

推广函数全局雪崩特征的两个指标是有原因的。将GF(2)推广到剩余类环Zq是很有必要的,如来学嘉和Massey提出的IDEA的一个部件就用了剩余类环Zq中的运算。并且密码学中经常要考虑多输出函数。给出的两个指标非常简洁,容易计算。由定义可知,如果ξ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] 单炜娟.相关免疫函数的结构与构造及其在流密码中的应用[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] 郭腓望,张习勇,韩文报.一种完全非线性函数的构造[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] 王林,谯通旭,赵伟,等.关于完全非线性函数的非线性度的界[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函数序列与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] 谯通旭,王运兵,谢上明,等.具有最大代数免疫度函数的研究[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);中国电子科技集团公司技术创新基金项目(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)