（应用数学专业论文）低差分一致性函数的研究.pdf

博士学位论文 摘要 低差分一致性函数可分为几乎完全非线性( a b n o s tp e r f e c tn o n l i n e a r ，a p n ) 函 数、完全非线性l p e r f e c tn o n l i n e a r ，p n ) 函数和其它低差分一致性函数它们在密 码学和代数学中都有广泛的应用本文构造和分析了一批低差分一致性函数，具体 成果如下： 在第二章中，由已知的a p n 幂函数特例归纳出奇特征域中的两类a p n 幂函数， 并以二次特征和d i c k s o n 多项式为工具给出证明新的a p n 函数可用来解释h e l l e - s e t h 提出的两种公开情况，并且可用来证明d o b b e r t i n 猜想最后，将前面提出的两 类a p n 函数加以推广，得出特定形式下幂函数的差分一致属性在证明过程中创 造性地引入d i c k s o n 多项式来求解方程，使得方程的求解变得简单可行 在第三章中，首先讨论了特征为2 的域中已知的几类a p n 多项式函数的等价性 质，接着给出了一类新的a p n 多项式函数，并进一步分析了它的b e n t 属性该a p n 函数不c a r l e t c h a r p i n - z i n o v i e v ( c c z ) 等价于d o b b e r t i n 函数，且在特定条件下不 等价于已知的函数其次，将特征为3 的域中一类已知的a p n 函数推广到奇特征域 中，新的a p n 函数包含已知的a p n 函数为特例最后，利用线性多项式和迹函数， 通过引入中间变量的方法计算了一大类a p n 函数的w a l s h 谱计算结果表明该类函 数的w a l s h 谱和g o l d 函数的w a l s h 谱相同，从而确定了它们的非线性度，而函数的 非线性度可以衡量其抗线性分析能力 在第四章中，将已知的a p n 多项式函数推广到奇特征域中，加上特定的条件而 得出几类p n 多项式函数，且证明了其中两类p n 函数不c c z 等价于已知的p n 函数， 由此给出了两类半域在特定的条件下，所构造的半域也与已知的半域不合痕我 们在证明过程中给出了判断c c z 等价和扩张仿射( e x t e n d e da f f i n e ，e a ) 等价的一种 方法最后，讨论了特定条件下d i u o n 多项式的差分一致性 在第五章中，结合前面的工具和方法，构造了几类低差分一致性函数我们注 意到除- j e d e l 和p o t t 最近发现的a p n 函数外，其它已知的a p n 多项式函数都是二 次的，而且在易。中还没有发现a p n 置换函数我们构造的低差分一致性函数不限 于二次，而且具有置换特性，从而给设计和构造s 盒提供了更多的方法在第3 节中， 引入了几乎低差分一致性概念，并构造了几类几乎低差分致性函数 关键词：布尔函数；线性多项式；低差分一致性；完全非线性；几乎完全非线性； c c z 等价 低差分一致性函数的研究 m a b s tr a c t l o wd i f f e r e n t i a lu n i f o r m i t yf u n c t i o n sc a r lb ed i v i d e di n t ot h r e ec l a s s e s ：a l m o s t p e r f e c tn o n l i n e a r ( a p n ) f u n c t i o n s ，p e r f e c tn o n l i n e a r ( p n ) f u n c t i o n sa n d o t h e rl o w d i f f e r e n t i a lu n i f o r m i t yf u n c t i o n s t h e yp l a ya ni m p o r t a n tr o l ei nc r y p t o g r a p h ya n d a l g e b r a i nt h i sd i s s e r t a t i o n ，w ec o n s t r u c ta n da n a l y z ea s e r i e so fl o wd i f f e r e n t i a l u n i f o r m i t yf u n c t i o n s t h em a i nc o n t r i b u t i o n sa r e 嬲f o l l o w s i nc h a p t e r2 ，t w of a m i h e so fa p np o w e rf u n c t i o n so no d dp r i m ef i e l da r e d e d u c e df r o mt h ek n o w nr e s u l t so fa p np o w e rf u n c t i o n s t h e i ra p np r o p e r t yc a n b ep r o v e db ya p p l y i n gq u a d r a t i cc h a r a c t e ra n dd i c k s o np o l y n o m i a l b a s e do nt h e n e wa p nf u n c t i o n s ，w ec a l le x p l a i nt h et w oo p e nc a s e si n t r o d u c e db yh e l l e s e t ha n d t h e np r o v ed o b b e r t i n sc o n j e c t u r e f i n a l l y , w eg e n e r a l i z et h en e wa p nf u n c t i o n s a n dg e tt h ed i f f e r e n t i a lu n i f o r m i t yo fp o w e rf u n c t i o n sw i t hac e r t a i nf o r m w e i n n o v a t i v l yi n t r o d u c ed i c k s o np o l y n o m i a lt os o l v et h ee q u a t i o n ，w h i c hm a k e st h e p r o c e s se a s ya n df e a s i b l e i nc h a p t e r3 ，w ef i r s t l yd i s c u s st h ee q u i v a l e n c eo ft h ek n o w na p np o l y n o m i a l f u n c t i o n so i l b i n a r yf i e l d m o r e o v e r ，w ep r e s e n tan e wf a m i l yo fa p np o l y n o m i a l f u n c t i o n sa n da n a l y z et h e i rb e n tp r o p e r t y t h e s en e wa p np o l y n o m i a lf u n c t i o n s a r en o tc a r l e t c h a r p i n - z i n o v i e v ( c c z ) e q u i v a l e n tt od o b b e r t i nf u n c t i o n s ，a n da r e n o te q u i v a l e n tt ot h ek n o w nf u n c t i o n su n d e rc e r t a i nc o n d i t i o n s s e c o n d l y , f r o m t h ek n o w nr e s u l to nt h e 知l do fc h a r a c t e r3 ，w es i m i l a r l yc o n s t r u c taf a m i l yo f a p nf u n c t i o n so no d dp r i m ef i e l d t h ek n o w na p nf u n c t i o n sc a nb es e e n 嬲t h e s p e c i a lc a s e so fo u rn e wr e s u l t s f i n a l l y , w eo b t a i nt h ew 如hs p e c t r u mo fa f a m i l y o fa p nf u n c t i o n sb a s e do nl i n e a rp o l y n o m i a l ，t r a c em a p p i n ga n di n t e r m e d i a t e v a r i a b l e w ef i n dt h a tt h ew a l s hs p e c t r u mo ft h e s ef u n c t i o n si ss a m ea 8t h a to f g o l df u n c t i o n s o u rr e s u l t sd e t e r m i n a t et h en o n l i n e a r i t yo ft h ef u n c t i o n sw h i c h m e a s u r e st h e i rr e s i s t a n c et ol i n e a rc r y p t a n a l y s i s i nc h a p t e r4 ，w ef u r t h e rs t u d yt h ek n o w na p np o l y n o m i a lf u n c t i o n so no d d p r i m ef i e l da n dt h e ng e ts e v e r a lf a m i h e so fp np o l y n o m i a lf u n c t i o n su n d e r c e r t a i n c o n d i t i o n s w ep r o v et h a tt w of a m i l i e so ft h e ma r en o tc c ze q u i v a l e n tt ot h e k n o w np nf u n c t i o n s t h e nw eg e tt w of a m i l i e so fs e m i f i e l d s u n d e rc e r t a i nc o n - d i t i o n s ，t h en e ws e m i f i e l d sa r en o ti s o t o p i ct oa n yo t h e rk n o w no n e w ep r e s e n ta m e t h o dt od e t e r m i n ec c z - e q u i v a l e n c ea n de a ( e x t e n d e da f f i n e ) e q u i v a l e n c ei no u r i i 博士学位论文 p r o o f f i n a l l y , w ed i s c u 鼹t h ed i f f e r e n t i a lu n i f o r m i t yo fd i l l o n sp o l y n o m i a lu n d e r c e r t a i nc o n d i t i o n s i nc h a p t e r5 ，w eg i v es o m el o wd i f f e r e n t i a lu n i f o r m i t yf u n c t i o n sb yt h ew a y s i n t r o d u c e db e f o r e w bn o t et h a tt h ek n o w na p np o l y n o m i a lf u n c t i o n sa r ea l l q u a d r a t i ce x c e p tt h ea p n f u n c t i o n sr e c e n t l yf o u n db ye d e la n dp o t t i n 昱2 ，i ，t h e a p n p e r m u t a t i o nh a sn o ty e tb e e nf o u n d w ec o n s t r u c tl o wd i f f e r e n t i a lu n i f o r m i w f u n c t i o n sw h i c ha r en o tq u a d r a t i c e s p e c i a l l y , s o m eo ft h e ma r ep e r m u t a t i o n s w e p r o v i d em o r em e t h o d st od e s i g nt h es - b o xb yu s i n gt h e m i ns e c t i o n3 ，w ei n t r o - d u c et h ec o n c e p to fa l m o s tl o wd i f f e r e n t i a lu n i f o f r u i t ya n dc o n s t r u c ts e v e r a lf a m i l i e s o fa l m o s tl o wd i f f e r e n t i a lu n i f o r m i t yf u n c t i o n s k e yw o r d s ：b o o l e a nf u n c t i o n s ；l i n e a rp o l y n o m i a l ；l o w d i f f e r e n t i a lu n i - f o r m i t y ；p e r f e c tn o n l i n e a r ；a l m o s tp e r f e c tn o n l i n 黜, c c z - e q u i v a l e n c e i i i 湖南大学 学位论文原创性声明 本人郑重声明：所呈交的论文是本人在导师的指导下独立进行研究 所取得的研究成果。除了文中特别加以标注引用的内容外，本论文不包 含任何其他个人或集体已经发表或撰写的成果作品。对本文的研究做出 重要贡献的个人和集体，均已在文中以明确方式标明。本人完全意识到 本声明的法律后果由本人承担。 作者签名： 如长 l ，) 日期：垆苔年坛月7 e l 学位论文版权使用授权书 本学位论文作者完全了解学校有关保留、使用学位论文的规定，同 意学校保留并向国家有关部门或机构送交论文的复印件和电子版，允许 论文被查阅和借阅。本人授权湖南大学可以将本学位论文的全部或部分 内容编入有关数据库进行检索，可以采用影印、缩印或扫描等复制手段 保存和汇编本学位论文。 本学位论文属于 1 、保密口，在年解密后适用本授权书。 2 、不保密邑 ( 请在以上相应方框内打“”) 作者签名： 导师签名： 查压卵 a 溶沈 日期：少够年肜月7 日 日期：。孵1 2 月77 日 博士学位论文 第1 章绪论 1 1 低差分一致性函数的研究背景与意义 随着计算机技术与网络通信技术的迅速发展，社会生活中数字化、信息化、网 络化发展趋势正在影响并改变人们的生活方式网络和信息技术的研发与普及，极 大地促进了科学、技术、文化、经济、政治以及军事等领域的发展，给人们的社会 生活提供了便利然而，在享受网络与通信技术带来的便利的同时，人们也不得不 面对日益严峻的信息安全问题在信息采集、存储、传输等一系列过程中信息的保 密性、完整性、可用性等信息安全问题应运而生如在网络中存储和传输的大量数 据都需要对目标数据加以保护，以免被盗用、泄露、篡改、伪造等电子商务、电 子银行等基于网络的经济行为都有身份认证、签名和防否认等安全需求如何维 护信息安全是任何信息技术都必须解决的核心问题 密码学作为保障和实现信息安全的核心技术，在各个国家都受到了普遍重视 密码的研究与应用已有几千年的历史，但作为一门科学是2 0 世纪5 0 年代才开始的 密码学是研究密码系统和通信安全的一门学科，它的应用非常广泛，如网络上应用 的数据加密技术、数字签名技术、消息认证与身份识别技术、防火墙技术以及反病 毒技术等都是基于密码学技术来设计的互联网的广泛应用，无线通信，秘密共享 等都大大推动了密码学的研究和发展大多数国家和地区都已成立了密码学学会， 这些学会定期主办学术会议进行学术交流，也促进了密码学的研究与应用国内外 已出版了大量有关密码学的书籍和理论研究论文，人们对密码学的研究和发展越 来越关注无论是政府，企业，还是个人，都开始有意识的使用密码技术来保密信 息资料密码学的研究与应用可谓日新月异 密码分为私钥密码( 又称为对称密码) 和公钥密码，其中私钥密码又分为序列密 码和分组密码，具体的概念定义请参见文【1 ，2 】它们各有特点，从设计原理到安 全性机制都有很大差异公钥密码是一个单向陷门函数，其主要原理是计算的单 向可行性自从1 9 7 6 年d i f f e 和h e l l m a n 提出公钥密码的观点之后，大量的公钥密码 被陆续提出来，如r s a 公钥密码、m e r k e - h e l l m a n 背包公钥密码、m c e l i e c e 公钥密 码、e 1 g a m a l 公钥密码和椭圆曲线( e c ) 公钥密码等，所有这些公钥密码的安全性都 依赖于数学问题的难解性序列密码是一个伪随机序列发生器，它具有生成简洁、 伪随机性好等优点分组密码是一个伪随机置换，它具有快速、易标准化、伪随机性 好等优点分组密码有四个著名的算法标准：美国i b m 公司研究的“d e s ”；来学嘉 教授设计的“i d e a ；j a m e s l m a s s e y 设计的“s a f e r ；j o a nd a e m e n 和v i n c e n t r i j m e n 共同设计的“r i j n d a e l 私钥密码体制的安全性基础是伪随机性另外， 低差分一致件函数的研究 私钥密码与公钥密码的应用领域也有很大的不同序列密码体制以简捷，快速的生 成算法，使其成为新一代移动通信的主流加密算法；分组密码体制也具有简捷，快 速的特点，并且容易标准化，使其成为软硬件加密标准的主流而公钥密码体制的 运行速度则慢得多，占用空间也大得多，一般用于数字签名、电子商务等计算资源 相对宽松的领域 伴随着现代密码技术的发展，密码函数的设计与分析从来都是研究的热点众 所周知，现行的分组密码分析方法除了穷尽搜索之外最常用的就是线性分析和差 分分析相应地，一个安全的分组密码体制必须具有抗线性攻击和抗差分攻击的性 能我们知道s 盒是分组密码中最重要的加密部件，如何设计s 盒的构造函数来有效 的抵抗线性攻击和差分攻击就成为人们研究的热点1 9 9 4 年n y b e r g 在文 3 】中首次 提出了差分一致性函数的定义： 定义1 1 令，( z ) 表示函数f ：_ 岛，n ( a ，6 ) 表示在z 昂n 中所有满足方 程f ( x + 口) 一f ( x ) = 6 的解的数目，其中a ，b 昂n ( a ，6 ) 的最大值，定义为，= m a x n ( a ，b ) l a ，b 昂n ，a o ) 若，= k ，则称函数，( z ) 为差分七一致函数 在分组密码( 如d e s ) 中，差分密码分析和线性密码分析就是利用构造s 盒的函 数的一致性缺点进行攻击所以，在密码学应用中，使用的函数f ( x ) l 筝j a ，值越小越 好构造和设计低差分一致性函数不可避免地成为研究的热点和重点。 低差分一致性函数通常是指定义1 1 中满足a ，4 的函数，其中根据，值又 可具体地分为几类函数，值等于1 时函数称为平面函数或者完全非线性( p e r f e c t n o n l i n e a r 即p n ) 函数在这种情况下，( z + o ) 一，( z ) 对任意的n 瞄= 昂n o ) 而 言是一个置换多项式完全非线性函数在有限几何以及差集的构造上有着广泛的应 用它可用来构造一个拥有可递性群的投影平面，相关的几何构造是基于用来构造 所谓的超椭圆的毋型幂函数完全非线性d e m b o w s k i - o s t r o m 多项式函数还可用来 定义预半域和半域有关完全非线性函数的更多研究与应用请参见文 4 1 0 1 a f 值 等于2 时函数称为几乎完全非线性( a h n o s tp e r f e c tn o n l i n e a r 即a p n ) 函数a p n 函 数的定义和几乎本原( a l m o s tb e n t 即a b ) 函数的定义是密切相关的【1 1 】a b 函数只 存在于f 2 。m 为奇数) 中，且拥有最佳的抵抗线性密码分析性能1 1 2 ，1 s 1 任意的a b 函 数都是a p n 函数，而且当n 为奇数时，任意的二次函数为a p n 函数当且仅当它是a b 函数【1 4 1 在特征为2 的域中，因为，p + a ) 一f ( x ) = b = ，( 扛+ 口) + a ) 一f ( x + 口) ，。 所以，= 2 是最小的可能值因此，几乎完全非线性函数是构造s 盒函数的最佳 选择几乎完全非线性函数也可用于其它无线通信领域如几乎完全非线性函数 对应长度为2 n 一1 的2 n 维线性码的最小距离刚好为5 ，所以可以用它来构造和研 究线性码在奇特征域中，越来越多的几乎完全非线性函数也被发现和应用现 在，完全非线性函数和几乎完全非线性函数因其优良的差分性质被广泛应用到相 关的其它领域如它们可用来构造差集，几乎差集和扭曲映射等( 见文 1 5 , - , , 2 5 1 ) 另 博士学位论文 一方面，它们的w a l s h 谱和布尔函数都有很好的性质相关的研究见文 2 6 , - , - , 3 0 与a b 函数相对应地有b e n t 函数，它是r o t h a u s 在1 9 7 6 年在文【3 1 】中提出的w a l s h 谱 为0 ，z t ：2 詈的易。上的布尔函数称为b e n t 函数，b e n t 函数是与所有的仿射函数中具有 最大距离的函数，它只在n 为偶数时存在，相关地研究见文 3 2 4 2 由于考虑到其 它的密码学性质，如最大非线性，相关免疫性等，低差分一致性为3 或4 的函数也被 应用到密码体制中虽然它们差分一致性不及完全非线性函数和几乎完全非线性 函数，但是它们的置换属性等其它的优秀特性也使其有很大的应用价值如当礼为 偶数时，易。中的逆函数2 ：2 - - 2 是一个差分4 一致置换函数，其非线性度为2 俨1 2 号 当n = 8 时，该函数被选作高级加密标准( a e s ) 的s 盒函数【4 3 】 综上所述，低差分一致性函数具有较高的应用价值，而构造和分析低差分一致 性函数是密码工作者的重要任务之一本文致力于解决一些低差分一致性函数中 存在的问题，分析和构造了几类低差分一致性函数本文的研究结果丰富了低差分 一致性函数的内容，给密码设计者提供了更多的选择，同时我们的构造方法也可用 于对低差分一致性函数的进一步研究 1 2 低差分一致性函数研究进展 大多数针对对称密码算法的攻击是利用系统中的布尔函数的某些属性来进行 的在迭代块密码中，最主要的密码分析方法是线性密码分析和差分密码分析 而s 盒作为代换置换的主要执行部分不可避免地成为密码设计和密码分析的重 点b i h 锄和s h 8 m i r 在文【4 4 1 中讨论了s 盒的差分分析方法以及怎样保证s 盒的抗差 分分析能力自从n y b e r g a ，4 5 1 给出了差分一致性函数的定义后，大量的低差分一致 性函数特别是几乎完全非线性函数被构造和研究 人们最先考虑的是幂函数f ( x ) = 一的差分一致性在密码应用中，几乎完全 非线性函数在块密码和流密码中都有广泛应用为了有效的在硬件和软件上执行， 人们更多的考虑特征为2 的域( 即偶特征域) 上的几乎完全非线性函数已发现的偶 特征域上的几乎完全非线性幂函数如下： n y b e r g a l ，b e t h 和d i n g 4 6 1 i l t i t 韭 了d = 妒一2 ，礼为奇数时一为易。中的a p n 函 数( k l o o s t e r m a n 情况) ； n y b e r g 3 1 ，b 矗h 和d i n g 考虑了g o l d 指数而得出d = 2 k + 1 ，( n ，k ：；= l 时一为 易n 中的a p n i 函数( g o l d 情况) ； j a n w 灌】w i 妇由k a s a 蚵指数【4 9 】而得出d = 2 2 k - 2 毛+ 1 ，( 佗，k ) = 1 时为足n 中的a p n i 函数( k a s m i 情况) ； d o b b e r t i n 在文【5 0 】中证明了w _ e l c h 猜想【5 1 】而得出d = 2 七+ 3 ，n = 2 k + l l i 寸z d 为易 孓 低差分一致性函数的研究 中的a p n 函数( w e l c h 情况) ； d o b b e r t i n 在文【5 2 】中证明了n i h o 猜划5 1 】而得出d = 2 2 七+ 2 七一1 ，4 k + 1 三0 r o o dn 时为岛n 中的a p n 函数( n i h o 情况) ； d o b b e r t i n 在文 5 3 】中给出- j d = 2 4 七+ 2 3 七+ 2 2 七+ 2 七一1 ，钆= 5 七时为易n 中 的a p n 函数( d o b b e r t i n 情况) 到目前为止，在偶特征域中只发现上述六类a p n 幂函数( 在等价条件下) h e l l e - s e t h 等用计算机搜索证明了当钆1 1 时，足。中只存在上述六类a p n 幂函数酬。人 们猜想尼。中没有其它的a p n 幂函数( 在等价条件下) ，但到目前为止还无法证明它 在奇特征域中，新的a p n 函数陆续被构造h e u e s e t h 和s a n d b e r g 5 5 】用计算机进行了 大量搜索并找到了两类单项式a p n 幂函数：( 1 ) b 。中的函数f ( x ) = z 3 ，其中p 3 ； ( 2 ) d = 卫兰21 时，b n 中的函数f ( x ) = 一，其中p 三3 ，7m o d2 0 ，i f , 7 ，矿 2 7 且死为奇数除了己知的a p n 函数外，他们还发现了一些新的低差分一致性函数 h e l l e s e t h ，r o n g 和s a n d b e r g 酬用计算机搜索到部分特征为奇素数域上的a p n 函数， 并成功的构造几类a p n 幂函数来解释它们在易中，已被解释的情况为：( 1 ) d = 学+ 掣时一为a p n 函数，其中矿三3r o o d8 ；( 2 ) d = 型坐4 时 一- - 为a p n 函数， 其中p n 兰7m o d8 ；( 3 ) d = 垄时一为a p n 函数，其中矿三2r o o d3 ；( 4 ) d = 矿一3 1 j 寸x d 为a p n 函数，其中p = 3 ，n 1 为奇数但仍有几种情况不能解释( 见 表2 1 ) ，解释这几种公开情况就成了人们研究的方向之一d o b b e r t i n l 等解释了 其中的两种情况而得出两类新的a p n 幂函数( 见引理2 1 2 2 ) ，并且对另一种情况给 出了著名的d o b b e r t i n 猜想f e l k e 5 7 】利用多变量方法构造了一系列低差分一致性函 数，并且部分解决了d o b b e r t i n 猜想本文构造了两类a p n 函数，解释了表2 1 中其 它的两种情况并完全证明了d o b b e r t i n 猜想我们注意到：在构造a p n 幂函数的同 时，一些低差分一致性函数也被构造和讨论构造新的a p n 函数，一般先采用计算 机搜索一些单个的a p n 函数，然后将其推广为一类a p n 函数并用数学方法来证明 它 尽管大量的a p n 函数被构造和发现，但是一些特殊的a p n 函数仍没有找到， 如足。中的a p n 置换函数我们知道在对称密码体制中，执行的变量为偶数而 且s 盒其实就是一个代换置换网络，所以b ：。中的a p n 置换函数是构造s 盒的最佳 选择但是，到目前为止人们还没有找到这种函数，它是否存在是一个公开问题 h o u 在文f 5 8 ，5 9 1 中证明了在局。中，当n = 4 或f 只哥m 时，f 不可能是a p n 置换 已经发现的二元域中的a p n 多项式函数都是二次的，是否存在非二次的a p n 多项 式函数? 以及当n 3 k 且( 3 ，k ) = i n ，是否存在毋。中的二次a p n 函数不等价于 任意的幂函数? e d e l 和p o t t 在文【6 0 】中首次提出了两类非二次a p n 多项式函数并 证明其中一类a p n 函数与已知的a p n 函数不等价，利用该文的方法构造新的非二 垂 博士学位论文 次a p n 或p n 多项式函数将是我们未来研究的目标b e r g e r ，c a n t e a u t ，c h a r p i n 和 c h a p u y 在文 6 1 】中综合讨论了a p n 函数的公开问题并利用布尔函数得出a p n 函数 新的性质总之，a p n i 垂i 数还有更多的问题等待我们去发现和解决 由于完全非线性( p n ) 函数只能在奇特征域中存在，它的应用一般限于有限几 何最早被发现的三类p n 函数( 又称为平面函数) 如下( 参考文献见文【6 2 6 5 】) ： f ( x ) = x 2 在中为p n 函数，其中p 为奇素数； f ( x ) = 矿。+ 1 在中为p n 函数，其中p 为奇素数，佗( 死，s ) 为奇数； f ( x ) = z l o + z 6 一x 2 在玛。中为p n 函数，其中n 等于2 或奇数 p n 函数有一个有趣的性质：若q 为一个奇素数且f r 为一个p n i 函数，贝, l j f 等 价于z 2 d e m b o w s k i 和o s t r o m 6 5 1 提出一个问题：是否所有的p n 函数，( z ) 具有形 式，( z ) = 啦f 憎( d e m b o w s k i o s t r o m 多项式) ? c o u l t e r 和m a t t h e w s i e 治l 给出 i j 。- - 。o 一 了一类新的p n 函数：f s 。中，( z ) = z 孕，其中k 为奇数且( n ，后) ：1 这类p n 函数 否定地回答了上面的问题另外，y u a n i g l d i n g s 推广了上面的多项式p n 函数而得 出一类新的多项式p n 函数：b 。中的函数f ( x ) = z l o 一蚴6 一牡2 2 2 ，其中让b n ， 铊为奇数本文由已知的a p n 多项式函数构造出两类新的p n 多项式函数，该p n 多 项式函数不等价于已知的p n 函数由于p n 函数在有限几何以及差集的构造上的 应用【6 7 “倒，构造新的p n 函数特别是p n 多项式函数成为人们研究的热点 k r i s t e n s e n 在文 7 3 】中给出了用计算机搜索形为f ( x ) = z d z + z d ：的p n 函数和 a p n 函数的结果于是一系列研究p n 多项式函数和a p n 多项式函数的工作随之展 开由于a p n 函数的密码学用途更广泛，人们将研究的重点放在a p n 多项式函数 的构造和分析上一批新的a p n 多项式函数被构造和发现，但是我们发现：部分新 的a p n 函数和已提出的函数虽然形式不同，但实际上是相互等价的可是如何判定 两个a p n 函数是等价的呢? 当前我们评定的标准有两种：扩张仿射( e x t e n d e da 伍n e 即e a ) 等价和c a r l e t - c h a r p i n - z i n o v i e v ( c c z ) 等价【1 4 1 c c z 等价和码等价是相互对 应的，我们可以利用编码理论中的方法和工具来确定函数是否c c z 等价【7 如洲构 造出一类新的a p n 函数后，讨论它与已知的函数的不等价性也是一项重要的工作 目前a p n 多项式函数研究的主要成果如下： e d e l ，k y u r e g 蛳l 和p o t t 在文【8 1 】中首先在r ，。中构造出一类a p n 双项式函数 ，p ) = 矿+ t ，其中珏为巧。中特定的元素同时，另一个a p n 双项式函数 b ，。中，( z ) = z 3 + u t 5 2 8 ( u 为磁：中特定的元素) 也被提出； j e d u d c a 在文 8 2 】中给出了毋n 中的无限类a p n 单项式函数； 一5 低差分一致性函数的研究 b u d a g h y a n ，c a r l e t $ f l p o t t 在文 2 6 1 中给出了易n 中新的a p n 函数和a b 函数，并 且证明了它们e a 不等价于任意的幂函数和仿射函数之和： b u d a g h y a n 等在文阳，8 4 】中给出了易。中的一类二次a p n 双项式函数，其中他为 3 的倍数，并证明了函数不等价于幂函数； b u d a g h y a n 等在文i s 4 ，8 5 】中给出了f 2 。中的一类二次a p n 双项式函数，其中n 为 4 的倍数，并讨论了函数的不等价特性； b u d a g h y a n 在文 8 6 】中给出了利用e a 等价和逆置换构造了一类多项式a p n 函 数，该函数e a 不等价于幂函数； b u d a g h y a n 等在文 8 7 】中给出了一种由已知a p n 函数构造a p n 函数的方法，并 构造出一类a p n 函数他们讨论了该a p n 函数的c c z 等价特性和构造的可行 性，给以后的研究工作提供了方法和工具； b u d a g h y a n 弄f l c a r l e t 在文 8 8 】中给出了易n 中的几类二次a p n 三项式和六项式函 数，。其中凡为偶数，并简要讨论了函数的相关结构和不等价特性； b r a c k e n ，b y n e ，m a r k i n 和m c g u i r e i t 4 在扎为偶数和铊为3 的倍数时分别构造出易 中一类多项式a p n 函数，并讨论了其中该函数的c c z 等价特性和编码理论在 文 8 9 】中他们将文 7 4 】中的函数加以推广，得到一类二次四项a p n 函数并简要 讨论了其和d i l l o n 多项式间的等价关系： n e s s 承i h e l l e s e t h 在文 9 1 1 中给i 出t f 3 n 中的一类a p n 双项式函数f ( x ) = 一“一2 + 札z 华，其中u 为玛。中特定的元素，他们的结果给a p n 函数的研究开辟了新 的领域z e n g ，h u ，y a n g 和j i a n g 在文【9 2 】中证明了该类a p n i 函数c c z 不等价于 已知的a p n 函数； e d e l _ j g l p o t t 在文 删中给出了而中的一类非二次a p n 多项式函数f ( x ) = 护+ t 正1 7 ( z 1 7 + z 1 8 + z 加+ 护4 ) + t 1 8 2 9 + t 上3 6 2 1 8 + 让9 z 笳+ z 2 1 + z 4 2 + t r ( u 2 7 x + u 5 2 护+ 铲z 5 + t 1 9 2 7 + 1 2 2 8 x 1 1 + t 正2 2 1 3 ) ，其中毋是由。6 + x 4 + 护- i - z + 1 f 2 z t 糙 的分裂域，u 为上式在中的根该函数c c z 不等价于任意扭曲函数 在上述研究成果获得的同时，大量的a p n 函数研究的相关工作也得到了深入的研 究f 蜘卅如c h e o n 和i 艘在文【9 8 】中分析了a p n 幂函数的抗代数攻击性能，b y r n e 和 m c g 山r e 在文【9 9 】中证明了一类a p n 函数不可能是无限类等等 低差分一致性函数，特别是a p n 函数及p n i 爱数在相关领域中的应用也得到了 广泛的研究b r a c k e n ，b y r n e ，m a u r l 【i n 和m c g l l i r e 在文【1 0 0 ，1 0 1 】中研究了a p n 函数 博士学位论文 f 拘w a l s h 谱以及非线性特性y u a n 和d i n g 在文【8 】中利用新的p n 函数来构造h a d 扣 m a r d 差集，从而否定了长期存在的h a d a m a r d 猜想k y u r e g h y a n 和b i e r b r a u e r 在文 献 1 0 2 1 0 5 】中讨论a p n 函数与扭曲映射之间的关系，更多的研究见文【1 0 7 一1 1 6 - 1 3 主要成果和组织结构 由于低差分一致性函数在密码体制设计中有着举足轻重的地位，构造和设计 具有良好密码学性质的低差分一致性函数是当前应用密码学中的研究热点之一本 文在已知的a p n 函数及构造方法的基础上，利用二次特征，d i c k s o n 多项式，幂函数 以及仿射多项式等工具，构造并分析了几类具有低差分一致性的函数本文的主要 成果及章节安排如下： 在第二章中，我们首先以二次特征，d i c k s o n 多项式为工具构造并证明了一类 a p n 函数，新的a p n 函数解释了h e l l e s e t h 提出的一种公开情况然后我们利用同 样的方法证明了d o b b e r t i n 猜想并提出另一类新的a p n 函数，该类a p n 函数解释 了h e l l e s e t h 提出的另一种公开情况另外我们讨论了剩下的一种公开情况，给出一 类函数的差分一致性界最后我们将前面提出的两类a p n 函数加以推广，得出特 定形式下幂函数的差分一致属性我们的证明方法是将已往的传统方法中创新性 的引入d i c k s o n 多项式来讨论求解，这种新的方法使得方程的求解变得简单可行 在第三章中，我们分别考虑了偶特征域和奇特征域中的多项式a p n 函数首 先，我们讨论了偶特征域中已知的几种a p n 多项式函数的等价性质，接着给出了一 类新的a p n 函数并证明了它的b e n t 属性该a p n 函数c c z 不等价于d o b b e r t i n 函 数且在特定条件下不等价于已知的函数其次，我们将特征为3 的域中一类己知 的a p n 函数推广到奇特征域中，得到定义范围更广的a p n 函数，新的a p n 函数包 含已知的a p n 函数为特例最后，我们计算了一大类a p n 函数的w a l s h 谱，我们的 结果回答了文【l o o 】中提出的一个公开问题 在第四章中，我们将已知的a p n 函数推广到奇特征域中，加上特定的条件而 得出几类p n 函数我们证明了其中两类p n 函数c c z 不等价于所有已知的p n 函数， 由此给出了两类半域在特定的条件下，我们构造的半域也与已知的半域不合痕 其中二项式p n 函数主要用特殊的线性多项式为工具来证明，我们的方法可以对已 知的a p n 函数给出一个不同的证明，而多项式p n 函数则用第三章中所用的方法来 证明我们的结果给出了构造p n 函数的新方法，对现有的p n 函数是一个很好的补 充最后，我们讨论了特定条件下d i l l o n 多项式的差分一致性，得出了一些特殊的 低差分一致性函数 在第五章中，我们结合前面的工具和方法，给出了一些低差分一致性函数和 构造方法我们注意到除了e d e l 和p o t t 最近发现的非二次a p n 函数外，其它已知 的a p n 多项式函数都是二次的，而且在b h 中还没有发现a p n 置换函数我们构造 低差分一致性函数的研究 的低差分一致性函数已不限于二次，而且具有置换特性，从而给构造和设计s 盒提 供了更多的方法在第3 节中，我们引入了几乎低差分一致性概念并证明了几类几 乎低差分一致性函数 最后，我们对论文进行了总结，并讨论了今后所要做的工作 1 4 本文所用的记号 易 墨 c f ( p n ) l m a x ( ，) g c