(非)弱正则p值bent函数的间接构造_杨志耀.pdf

中国科学:数学2023年第53卷第2期:381394SCIENTIA SINICA Mathematica论文英文引用格式:Yang Z Y,Ke P H,Chen Z X,et al.Secondary constructions of p-ary(non-)weakly regular bent functions(inChinese).Sci Sin Math,2023,53:381394,doi:10.1360/SSM-2022-0068c 2022中国科学 杂志社(非)弱正则p值bent函数的间接构造献给朱烈教授80华诞杨志耀1,柯品惠2,陈智雄3,张胜元21.福建师范大学福建省网络安全与密码技术重点实验室,福州 350117;2.福建师范大学数学与统计学院,福州 350117;3.莆田学院福建省金融信息处理重点实验室,莆田 351100E-mail:,,,收稿日期:2022-04-26;接受日期:2022-06-23;网络出版日期:2022-09-07;*通信作者国家自然科学基金(批准号:61772292 和 61772476)和福建省自然科学基金(批准号:2019J01273 和 2020J01905)资助项目摘要Bent函数在对称密码、序列设计、组合理论和编码理论等领域都有着重要的应用.基于已有的非直和与半直和构造研究方法,本文给出一类bent函数的间接构造.利用所得构造,通过选取合适的初始(向量)bent函数及其组合构造出高代数次数的(非)弱正则bent函数.更准确地,本文借助向量M-M(Maiorana-McFarland)类和PS(partial spread)类bent函数,给出了一些(弱)正则bent函数.特别地,给出了这些bent函数的对偶函数的显式表达式.进一步地,应用向量完美非线性(perfectnonlinear,PN)函数,生成了无限类非弱正则bent函数.关键词(向量)bent 函数(非)弱正则 bent 函数非直和半直和MSC(2020)主题分类05E05,11T23,11T711引言1974年,Dillon9研究了一类具有最优非线性度的布尔函数.直到1976年,Rothaus30首次将其命名为布尔bent函数,并沿用至今.Bent函数作为一种有趣的组合对象,在密码学、组合理论和编码理论等领域中都有广泛的应用(参见文献2,25),近40多年来一直是诸多学者研究的热点课题(参见文献3).1985年,Kumar等14(也参见文献22)将布尔函数的概念推广到任意有限域上的函数,即广义布尔函数,并提出广义bent函数的概念.一般地,广义bent函数要比布尔情形下的结构更为复杂10,11,1517,19.迄今为止,学者们提出了若干(广义)bent函数的直接或间接构造18,20,21,23,24,34.令Fp表示含有p个元素的有限域,符号Vn表示有限域Fp上的n维向量空间.设函数f:Vn Fp(p为素数),则函数f在任意点u Vn处的(广义)Walsh-Hadamard变换(或称Walsh谱)为?f(u)=xVnf(x)p,杨志耀等:(非)弱正则 p 值 bent 函数的间接构造其中,p=e2ip为p次本原单位根,为Vn上的内积.若Vn=Fnp,则=u x为一般的向量内积;若Vn=Fpn,则=Trn(ux),其中Trn(z)表示z Fpn的绝对迹25.应注意到,(广义)Walsh-Hadamard变换作为特殊的离散Fourier频谱变换是研究布尔函数的有力工具,可以刻画如平衡性、非线性、弹性和扩散性等布尔函数的诸多密码学性质2.由Parseval能量守恒公式知,函数f:Vn Fp在点u Vn处满足uVn|?f(u)|2=p2n.若函数f在任意点u Vn处,Walsh谱的绝对值都满足|?f(u)|=pn2,即函数f的Walsh谱的绝对值是平坦的,则称函数f为p值bent函数(若无歧义,下文简称为bent函数).当p为奇数,变元空间n为偶数和奇数时,bent函数均存在.特别地,当p=2时,函数f即为布尔bent函数,此时仅当变元空间n为偶数时存在.若函数f为bent函数,则函数f在任意点u Vn处的Walsh谱为?f(u)=pn/2?f(u)p,pn 1(mod 4),ipn/2?f(u)p,pn 3(mod 4),(1.1)其中函数?f:Vn Fp称为函数f的对偶函数(参见文献10).若bent函数f在任意点u Vn处都满足?f(u)=pn/2?f(u)p,则称f为正则bent函数(布尔bent函数均为正则bent函数).若bent函数f在任意点u Vn处都满足?f(u)=pn/2?f(u)p,其中 1,i,则称f为弱正则bent函数(显然,弱正则bent函数包含正则bent函数);否则,称f为非弱正则bent函数.迄今为止,学者们提出了一系列bent函数的构造方法,这些构造方法大致可分为两类:一类是以经典的M-M(Maiorana-McFarland)类5,23、PS(partial spread)类19和GPS(generalized partialspread)等为代表的直接构造方法1,25(直接构造中在不使用已知密码函数的情况下设计bent函数);另一类则是以Rothaus构造21,30、Carlet构造18以及Mesnager构造24等为代表的间接构造方法12(间接构造中往往利用一些初始bent函数和附加条件来生成新的bent函数).除研究bent函数的构造方法外,文献13也较完整地刻画了bent函数的一些密码学性质,如平衡性、代数次数和弹性等.近年来,构造特殊的一类(非)弱正则bent函数或其推广函数(如三值Walsh谱的plateaued函数)成为研究的关注点,这些函数可以用来设计满足特殊性质的线性码,进而应用于通信、密码学和组合设计等相关领域(参见文献26,28,31,33,36,37).文献10,11,15,16,19,34均给出了具有特殊形式的弱正则bent函数的构造方法.然而,相较于庞大的bent函数族,仅有很少的非弱正则bent函数的构造方法是已知的.具体地,2010年,Tan等32利用函数的直和构造方法,并借助计算机遍历搜索,得到了第一类非弱正则bent函数的间接构造.之后,C?e?smelio?glu和Meidl4及C?e?smelio?glu等5,8利用plateaued函数研究了无限类的(非)弱正则bent函数的构造,并在文献6中给出半直和构造方法,得到了非对偶bent函数的研究结果.Meidl21提出了一类推广的Rothaus构造方法,并选用合适的向量bent函数构造了无限类的非弱正则bent函数.Mesnager等27利用半直和构造方法得到了(非)弱正则plateaued函数.此外,较近的关于构造非弱正则bent函数的研究结果参见文献35.构造和发现其他(非)弱正则bent函数的构造方法一直是值得探究的重要课题.本文将给出一个有效的(非)弱正则bent函数的构造方法.具体地,受文献6,12,21启发,本文给出一类具有一般形式的bent函数的间接构造.利用所得构造,选取一些合适的向量bent函数以及它们之间的组合,可以有效地构造(非)弱正则bent函数.令Vm和Vn分别表示有限域Fp上的m和n维向量空间.设函数F(x1,x2,.,xm)=(f1,f2,.,fn)(x1,x2,.,xm)382中国科学:数学第 53 卷第 2 期为从Vm映射到Vn上的向量函数(或称(m,n)-函数),其中f1,f2,.,fn:Vm Fp为m元函数,称为函数F的分量函数.设非零元 Vn(或记为 Vn),则函数F(x)=:Vm Fp称为函数F的组成函数.若函数F的每个组成函数都是bent函数,则称函数F为向量bent函数2,7,8.事实上,零函数和组成函数的集合构成了有限域Fp上bent函数的n维向量空间,集合f1,f2,.,fn为此n维向量空间的基.对向量bent函数而言,若p=2,则维数n至多为m/2;若p为奇数,则n 6 m.若n=m,则此时的向量bent函数称为完美非线性(prefect nonlinear,PN)29函数.本文余下内容安排如下:第2节回顾并归纳已有的bent函数的间接构造方法,并给出一类bent函数的一般构造方法.第3节利用所得构造,通过选取向量M-M类bent函数以及PS类bent函数,推导出(弱)正则bent函数,并计算它们的对偶函数.第4节应用向量PN函数与其他向量函数的组合,得到更多的非弱正则bent函数.第5节对本文工作进行总结.2Bent 函数的间接构造2.1一些已知的bent函数的间接构造方法本小节总结一些经典的bent函数的间接构造方法,并分析这些已有构造之间的联系.首先,回顾bent函数的半直和构造方法,该方法用来构造特征为奇数的有限域上的bent函数,之后被推广到构造向量bent函数6,8.定理2.1(半直和构造8)设函数f:Vm Fpk和函数g:Vn Fpk分别为(m,k)-bent函数和(n,k)-bent函数,函数H(x):Vm Vn为任意向量(m,n)-函数.定义函数F:Vm Vn Fpk为F(x,y)=f(x)+g(y+H(x),(2.1)其中,x Vm,y Vn.函数F为bent函数当且仅当对任意的v Vn和 Fpk,函数Gv,:Vm Fp,Gv,(x)=Trk(f(x)+为bent函数.特别地,若k=1,则定理2.1为文献6,定理1;若H(x)=0,则(2.1)为直和构造.半直和构造可用于构造(非)弱正则bent函数和非对偶bent函数.然而,对任意的v Vn和 Fpk,函数Gv,(x)满足成为bent函数的条件是较为苛刻的.Meidl21给出了推广的Rothaus构造,并得到一些无限类的(非)弱正则bent函数.定理2.2(推广的Rothaus构造21)设函数f0,f1,f2:Vm Fp为任意向量bent函数的线性无关的组成函数,a,b,c Fp.定义函数:Vm F2p Fp为(x,y0,y1)=f20(x)f0(x)f1(x)+f1(x)f2(x)f0(x)f2(x)+af0(x)+bf1(x)+cf2(x)+(f1(x)f0(x)y0+(f2(x)f0(x)y1+y0y1,(2.2)其中,x Vm,(y0,y1)F2p.函数为bent函数当且仅当a+b+c=0.特别地,若p=2,a=1,b=c=0,则(2.2)为布尔bent函数的Rothaus构造.事实上,推广的Rothaus构造可以看作定理2.1中半直和构造的特殊情形.由(2.1)知,当k=1时,令f(x)=af0(x)+bf1(x)+cf2(x),H(x)=(h0(x),h1(x)=(f2(x)f0(x),f1(x)f0(x)和g(y+H(x)=g(y0+h0(x),y1+h1(x)=(h0(x)+y0)(h1(x)+y1),则函数F为F(x,y0,y1)=af0(x)+bf1(x)+cf2(x)+(f2(x)f0(x)+y0)(f1(x)f0(x)+y1),383杨志耀等:(非)弱正则 p 值 bent 函数的间接构造即为推广的Rothaus构造.然而,推广的Rothaus构造的重要性在于它可以利用向量bent函数的3个分量函数的线性组合(简化条件),有效生成(非)弱正则bent函数21.其他重要的间接构造便是Carlet构造(或称非直和构造)和Mesnager构造,可用于构造布尔bent函数以及其他密码函数3,24.定理2.3(Carlet构造3)令x Vm,y Vn,其中m和n为正偶数.设函数f0,f1:Vm F2为m元布尔bent函数,函数g0,g1:Vn F2为n元布尔bent函数.若定义函数f:Vm Vn F2为f(x,y)=f0(x)+g0(y)+(f0+f1)(x)(g0+g1)(y),(2.3)则函数f为布尔bent函数.此外,函数f的对偶函数可由?f0、?f1、?g0和?g1得到,且与函数f在(2.3)中具有相同的公式.定理2.4(M