《武汉工程大学学报》 2010年09期
108-110
出版日期：2010-09-30
ISSN:1674-2869
CN:42-1779/TQ
两类多输出一阶拟Bent函数的构造
引言Bent函数是由Rothaus于1976年提出的一类特殊的非线性组合函数［1］.它的非线性度达到最大,稳定性强,差分分布均匀.用于非线性组合器可以很好的抗击最佳仿射逼近攻击和差分分析攻击.但Bent函数也存在着一些缺陷.如:它不具有平衡性和相关免疫性,n元Bent函数的代数次数不超过n/2,限制n为偶数等.为了弥补Bent函数的这些不足,为弥补Bent函数的这些不足,胡磊等定义了半Bent函数［2］,李世取教授等提出了k阶拟Bent函数的概念［3］,它是包含Bent函数和半Bent函数的更大的函数类.它可以具有Bent函数所不具有的密码学性质,如:平衡性、扩散性、相关免疫性等.随后,人们对拟Bent函数作出了一系列的研究成果［49］.这些研究表明,拟Bent函数是一类密码学性质良好的布尔函数,在密码设计及通信领域中有着广泛的应用.分组密码的核心部件S盒的设计中,常常采用具有多个良好密码学性质的多输出布尔函数.如何构造具有多种良好密码学性质的多输出布尔函数至为关键.人们在研究多输出函数时,总希望所选取的多输出函数的某些线性组合谱的绝对值尽可能均匀.仅就这一点而言,多输出Bent函数无疑就是最佳待选函数.但多输出Bent函数不可避免地带有Bent函数所固有的一些缺陷,如:非平衡性,相关免疫阶为零,其代数次数不超过变元数目n的一半,限制n为偶数等等.多输出拟Bent函数［10］可以弥补多输出Bent函数的这些不足,且具有多种良好的密码学性质,可广泛地应用于多输出前馈网,分组密码的S盒设计等领域.本文给出了两类多输出一阶拟Bent函数的构造方法,其中一类是平衡的,另一类是具有相关免疫性的.它们可广泛应用于分组密码的S盒设计和最佳信号设计等领域.1基本定义定义1［11］设f(x)是n元m输出函数,称S(f)(u,v)=2-n∑x∈Fn2(-1)u·f(x)+v·x为f(x)的广义一阶Walsh循环谱.其中u∈Fm2,v∈Fn2.易知,对于固定的u,S(f)(u,v)就是布尔函数u·f(x)的一阶Walsh循环谱,即S(f)(u,v)=S(u·f)(v).定义2［3］一个n元布尔函数f(x)称为k阶拟Bent函数,如果对任意的w∈Fn2,均有S(f)(w)=0或2-n-k2.将此定义推广到多输出函数情形即得如下定义:定义3设f(x)是n元m输出函数,若对一切固定的u,0≠u∈Fm2,v∈Fn2,均有S(f)(u,v)=0或2-n-k2,则称f(x)为多输出k阶拟Bent函数.特别地,当k=0时,上述f(x)即为多输出Bent函数.当k=1时,上述f(x)即为多输出半Bent函数［12］.由定义3易得如下结论:结论1n元m输出函数f(x)是多输出k阶拟Bent函数的必要条件是n与k奇偶性相同.结论2设f(x)是n元m输出函数,则f(x)是多输出k阶拟Bent函数的充要条件是0≠u∈Fm2,u·f(x)是n元k阶拟Bent函数.定义4［11］设f(x)是n元m输出函数,若对任意的a∈Fm2,P(f=a)=12m,即x∈Fn2|f(x)=a=2n-m,则称f(x)是平衡的或正交的.引理1［11］设f(x)是n元m输出函数,则f(x)是正交的充要条件是对任意的0≠u∈Fm2,u·f(x)是一个平衡布尔函数.定义5［11］设f(x):→Fm2,m≤n,x1,x2,…,xn是n个独立的、均匀分布的布尔随机变量,随机向量z=f(x)=f(x1,x2,…,xn).如果对任意的i1,i2,…,ij,1≤i1<…,<ij≤n及u∈Fm2:1≤WH(u)≤k,有u·z与(xi1,xi2,…,xij)统计独立,则称多输出函数f(x)是k级j阶相关免疫的.引理2［11］设f(x)如定义5中所述,1≤k≤m,则f(x)是k级j阶相关免疫的充要条件是对任意的v∈Fn2,1≤WH(v)≤j及u∈Fm2,1≤WH(u)≤k,有S(f)(u,v)=0.
第9期刘志高:两类多输出一阶拟Bent函数的构造
武汉工程大学学报第32卷
2一类平衡多输出一阶拟Bent函数
的构造文献［2］给出了一类半Bent函数的构造方法,具体如下:设n是奇数,n=2k-1,构造n元半Bent函数如下:令X1=(x1,x2,…,xk-1),X2=(xk,xk+1,…,xn),X=(X1,X2),再令τ是Fk-12→Fk2的单射,τ(X1)=(τ1(X1),…,τk(X1)),其中τi是k-1元布尔函数.令f(X)=τ(X1)X2=τ1(X1)xk+τ2(X1)xk+1+…+τk(X1)x2k-1(1)引理3［2］由(1)式定义的f(X)是n元半Bent函数,并且S(f)(W)=2-n-12若w2∈Im(τ)
0否则其中,W=(W1,W2),W1=(w1,…,wk-1),W2=(wk,wk+1,…,wn).基于引理3,笔者于文献［12］中给出了一类多输出半Bent函数的构造方法,具体如下:引理4［12］设n是奇数,n=2k-1,记X1=(x1,x2,…,xk-1),X2=(xk,xk+1,…,xn),X=(X1,X2),设πi:Fk-12→Fk2是满足下列条件的m个单射:对任意的1≤i1≤i2≤…≤ij≤m,πi1πi2…πij仍是单射.设fi∶Fn2=Fk-12×Fk2→F2,令fi(X)=πi(Xi)X2(1≤i≤m),则f(X)=(f1(X),f2(X),…,fm(X))是n元多输出半Bent函数.显然该方法的关键在于如何构造满足引理中条件的m个单射πimi=1.我们已于文献［12］中给出了构造这种单射集的一种具体方法,在此不再赘述.一般地,多输出一阶拟Bent函数不一定是平衡函数.下面将给出一类平衡多输出一阶拟Bent函数的构造方法.以引理4中单射πi(X1)=(φi1(X1),φi2(X1),…,φik(X1))的所有项为行向量作矩阵
Ei=φi1(X(0)1)φi2(X(0)1)…φik(X(0)1)
φi1(X(1)1)φi2(X(1)1)…φik(X(1)1)
φi1(X(2k-1-1)1)φi2(X(2k-1-1)1)…φik(X(2k-1-1)1)称Ei为πi(Xi)的特征矩阵,其中X(i)1,0≤j≤2k-1-1为j的二进制表示.Ei的各列恰好是单射πi(X1)相应分量函数的真值表.定理1设f(X)是按引理4的方法所构造的多输出一阶拟Bent函数,则它为平衡函数的充要条件是对任意的1≤i1≤i2≤…≤ij≤m,矩阵Ei1Ei2…Eij中均不存在全0的行向量.证明由引理1可知,f(X)是多输出平衡函数,当且仅当对一切固定的u,0≠u∈Fm2,u·f(X)是平衡布尔函数,当且仅当S(u·f)(0,0′)=0,其中0∈Fk-12.再由引理3可得,S(u·f)(0,0′)=0当且仅当对任意的1≤i1≤i2≤…≤ij≤m,0′Im(πi1πi2…πij),当且仅当对任意的1≤i1≤i2≤…≤ij≤m,矩阵Ei1Ei2…Eij中均不存在全0的行向量.上述定理1给出了一类平衡多输出一阶拟Bent函数的构造方法.J.Pieprzyk与G.Finkelstein在文献［13］中证明了n+1元平衡函数所具有的最高的非线性度是2n-2n2.笔者于文献［14］中已证明n+1元多输出一阶拟Bent函数的非线性度是2n-2n2.这说明平衡多输出一阶拟Bent函数已达到平衡函数所具有的最高非线性度.因此,定理1所构造出的平衡多输出一阶拟Bent函数是很有意义的,它具有很强的抵抗最佳仿射逼近攻击(BAA)的能力.3一类具有相关免疫性的多输出一
阶拟Bent函数的构造定理2设f(X)是按引理4的方法所构造的多输出一阶拟Bent函数,则它具有m级l阶相关免疫性的充要条件是对任意的1≤i1≤i2≤…≤ij≤m,矩阵Ei1Ei2…Eij的任意行向量中1的个数均大于l.证明由引理2知,f(x)是m级l阶相关免疫的充要条件是对任意的v=(v1,v2)∈Fn2,1≤WH(v)≤l,其中v1∈Fk-12,v2∈Fk2及u∈Fm2,1≤WH(u)≤m,有S(f)(u,v)=S(u·f)(v1,v2).=0再由引理3可得,S(u·f)(v1,v2)=0当且仅当对任意的1≤i1≤i2≤…≤ij≤m,v2Im(πi1πi2…πij),当且仅当对任意的1≤i1≤i2≤…≤ij≤m,矩阵Ei1Ei2…Eij中任意行向量中1的个数均大于l.