二次完备非线性函数的构造.pdfVIP

2012年 7月 西安石油大学学报(自然科学版) Ju1．2012 第27卷第4期 JournalofXianShiyouUniversity(NaturalScienceEdition) V01．27No．4 文章编号 ：1673-064X(2012)04-0101-04 二次完备非线性函数 的构造 何业锋 (西安邮电大学 通信与信息工程学院，陕西 西安 710121) 摘要：完备非线性函数能很好地抵抗差分密码分析，在密码和通信领域中有重要应用．构造了一族 代数次数为二次的完备非线性函数，该函数为具有四项的Dembowski—Ostrom多项式．证明了新构 造的完备非线性函数不但EA．不等价于已知的完备非线性方幂函数，而且也不等价于所有已知的 完备非线性函数． 关键词：密码学；差分密码分析；差分均衡度；完备非线性 中图分类号 ：TN918．1 文献标识码 ：A 差分密码分析是 以色列密码学家 Biham和 Shamir¨提出的，是迄今 已知的攻击类 DES分组密 1 基础知识 码最有效的方法之一．为了能够有效地抵抗差分密 码分析，人们希望能够找到差分均匀度 达到最小 令P是一个奇素数， 是一个有限域． 上的 的函数．在特征为2的域上，函数所能达到的最小差 任意函数F()在有限域 F。上都可以唯一地表示 分均匀度为2．一个差分2一均匀的函数称为几乎完 P 一l 备非线性函数 (简称 APN函数 )．当域的特征是 为次数小于P的多项式，即F()=∑ai，o∈ 奇素数时，还能找到差分均匀度为 1的函数．一个差 F 对于任意0≤m≤P 一1，m的P一重等于它的P- 分 1一均匀的函数称为完备非线性函数(简称 PN函 元表示的系数和．因此如果有m=∑bip，则m的 数 )或Planar函数 J．由于这类函数针对差分密 码分析能够提供最优的抵抗能力，因此密码工作者 P一重即为∑b∈z．有限域上F()的代数次数定 对其非常感兴趣．PN函数也能被广泛地应用到通信 义为所有非零项的指数 的最大P一重．函数F： 一 理论中，例如它们可以被用来构造线性码和符号 是线性函数当且仅当F()在域 上是一个线 集_6J．PN函数也可以用来描述奇数阶的有限交换 n一1 半域 ，并且文献 [8]中证 明了Dembowski—Os． 性化多项式(或p一多项式)，即F()=∑Ci，c∈ trom (简称 DO)多项式类的PN函数与奇数阶的有 F 一个线性函数和一个常数的和称为仿射函数． 限交换预半域是一一对应的．目前 已知的PN函数 定义 1[2 令 F()是有限域 上的函数．令 非常少．如何构造新的PN函数成了人们密切关注 △F=max{N(a，b)Ia，b∈F a≠0}，其中N(a， 的问题． b)表示方程 F(+a)一F()=b在域 F。上关于 的解 的个数．如果 △ =k，则称函数F()是差分 收稿 日期 ：2012-01—15 基金项 目：国家 自然科学基金项 目(编号；陕西省教育厅专项科研计划项 目(编号 ：2010JK825)；校青年教师 科研基金项 目(编号：ZL2010—16) 作者