[精品论文] 布尔函数的密码学性质及构造.pdf

复旦大学 博士学位论文 布尔函数的密码学性质及构造 姓名：彭杰 申请学位级别：博士 专业：基础数学 指导教师：吴泉水 2011-04 摘要 本文对布尔函数的一些密码学性质进行了研究主要考虑了具有高代数免疫度 的布尔函数以及对称相关免疫布尔函数的构造问题并考察了所构造布尔函数的一 些其他的密码学性质，如平衡性，代数次数及非线性度等 布尔函数在许多密码体制中具有举足轻重的地位其密码学性质的好坏直接决 定着系统的安全性本文利用代数学和组合数学的知识，在前人的工作基础上提出 了多种构造具有好的密码学性质的布尔函数的新方法通过这些方法，我们构造了 多类具有最高代数免疫度的布尔函数，并且最终解决了构造所有具有最高代数免疫 度的偶元对称布尔函数的问题另外，我们还构造了几类对称非回文相关免疫布尔 函数，并考察了对称相关免疫布尔函数的代数免疫性质 下面简要介绍一下本文的结构安排以及各章节的主要内容 第一章是绪论，包括前言和基础知识介绍在前言部分我们主要介绍了问题的 背景，目前的研究进展以及本文的主要工作，以期读者对这类问题能有一个大致的 了解基础知识部分主要介绍了布尔函数研究中的一些基本概念，基本方法以及要 用到的一些基本工具，为后续部分的展开作好铺垫 第二章考察具有最高代数免疫度的布尔函数的构造问题我们推广了构造主函 数的方法，找到了一大类具有最高代数免疫度的布尔函数我们还考虑了这类布尔 函数的计数以及它们的代数次数 第三章主要考察具有最高代数免疫度的旋转对称布尔函数的构造问题我们将 奇元旋转对称函数的构造问题转化成对一个二项式系数和式的奇偶性判定问题和 一个构造二元域上可逆循环矩阵的问题并由此构造了几类具有最高代数免疫度的 旋转对称布尔函数从而推广了已有的构造方法 第四章构造了对称布尔函数的几类非常重要的低次零化子，并找出了它们函数 值的分布特征，从而构造了所有具有最高代数免疫度的偶元对称布尔函数我们还 考虑了这些函数的代数次数及非线性度此外，通过类似的方法，我们研究了具有较 高代数免疫度的偶元对称布尔函数，得到了偶元对称布尔函数达到较高代数免疫度 的一些必要条件，并对具有次高代数免疫度的偶元对称布尔函数作了重点研究 第五章主要考察对称非回文相关免疫布尔函数的构造对佗= 6 r ，6 r + 1 ，6 r + 2 ，6 r + 3 的情形，分别给出了几类这样的布尔函数从而证明了此类函数的存在性 并利用第四章的结论，证明了一大类对称相关免疫布尔函数，即对称回文布尔函数 的代数免疫度都不高 关键词；代数攻击，代数免疫，平衡性，代数次数，非线性度，相关攻击，相 关免疫，旋转对称布尔函数，对称布尔函数，k r a w t c h o u k 多项式 中图分类号： t p 3 0 9 7 a b s t r a c t t h e p r e s e n tp h d d i s s e r t a t i o ni sm a i n l yc o n c e r n e dw i t ht h ec r y p t o g r a p h i cp r o p e r t i e s o fb o o l e a nf u n c t i o l l 8 w bc o n s t r u c tb o o l e a nf u n c t i o n sw i t hh i g ha l g e b r a i ci m i n u n i t ya n d c o r r e l a t i o ni m m u n eb 0 0 1 e a nf u n c t i o 璐a n dw r ea l s oc o n s i d e ro t h e rp r o p e r t i e s ，s u c ha u s b a l a n c e d n e s s ，a l g e b r a i cd e g r e e sa n dn o n l i n e a r i t i e s ，o ft h ee o n s t r u c t e db o o l e a nf u n c t i o n s i nt h i st h e s i s b o o l e a nf u n c t i o 璐p l a yav e 珂i m p o r t a n tr 0 1 ei nm a r l yc r y p t o s y s t e m s t h es e c u r i t y o fs u e hac r y p t o s y s t e mm a i n l yd e p e n d so nt h ec r y p t o g r a p h i cp r o p e r t i e so ft h eb o o l e a n f u n c t i o ni tu s e s w 色t a k ea d v a i l t a g eo fs o m ek n o w l e d g eo fa l g e b r aa n dc o m b i n a t o r i c st o c o 璐t r u c tb o o l e a nf u n c t i o n sw i t hc r y p t o g r 印h i cs i g n i f i c a n c e s e v e r a lc l a s s e so fb o o l e a n f u n c t i o n sw i t hm a ) 【i m u ma l g e b r a i ci m i i 】【u i l i t ya r ec o m t r u c t e d i np a u r t i c u l a r ，a l lt h e8 y m - m e t r i cb o o l e a n 劬c t i o n sw i t hm a x i m u ma l g e b r a i ci m m u n i t yo ne v e nn u m b e ro fv a r i a b l e s 跗ed e t e r m i n e d w ba l s oc o 璐i d e rt h ec o n s t r u c t i o l l so fs y m m e t r i cn o n p a l i n d r o m i cc o r - r e l a t i o ni m m u n eb o o l e a nf u n c t i o 璐a n ds t u d yt h e 以g e b r a i ci m m u n i t yo ft h es y m m e t r i c c o r r e l a 土i o ni m i n u n eb o o l e a nf u n c t i o n s m o r ep r e c i s e l y t h ec o n t e n t so ft h i st h e s i s 盯eo r g a n i z e da sf 0 1 1 0 w s ： c h a p t e r1i sa ni n t r o d u c t i v ec h a p t e r i ti n c l u d e sn o to n l yt h eh i s t o r ya n dc u r r e n t r e s e a r c hs t a t e si nt h i sr e s e a r c ha r e aa sw e l la so u rm a i nr e s u l t s b u t 出s os o m eb a s i c so n b o o l e a nf u n c t i o n s ，o u rm e t h o d s ，a n ds o m eb a s i ct o o l s r eu s e w eh o p et h i sc h a p t e rc a n p r o v i d ea f u l lv i e wf o rt h er e a d e r s c h a p t e r2i sc o n c e r n e dw i t ht h ec o i l s t r u c t i o no fb 0 0 1 e a nf u n c t i o n sw i t hm a x i m u m a l g e b r a i ci m m n i t y w bg e n e r a l i z et h em e t h o do fc o l l s t r u c t i n gt h em a j o r i t yf u n c t i o n st o c o 璐t r u c tal a r g ec l a s so fb 0 0 1 e a nf u n c t i o n sw i t hm a _ ) ( i m u mm g e b r a i ci m m u n i t y w ba l s o c o 璐i d e rt h ee n u m e r a t i o na n dt h ea l g e b r a i cd e g r e e so ft h o s eb o o l e a nf u n c t i o l l s c h a p t e r3d e a l sw i t ht h ec o n s t r u c t i o no fr o t a t i o ns y m m e t r i cb o o l e a nf u n c t i o n sw i t h m a 撕m u ma l g e b r a i ci m m u n i t y w bc o n v e r tt h ep r o b l e mo ft h eb a s i cc o n s t r u c t i o no fo d d v a r i a b l er o t a t i o ns y m m e t r i cf u n c t i o n sw i t hm a x i m u ma l g e b r a i ci m m u n i t yt oap r o b l e mo f 1 1 l d e t e r i i l i n i n gt h ep 撕t y0 fas 眦o f b i n o l n i a lc o e m c i e n t sa n da n o t h e rp r o b l e mo ff i n d i n g n o n s i n g u l a rm a t r i c 髑o v e rt h eb i n a 科6 e l d a 8ac o n s e q u e n c e ，w eo b t a j ns e v e r 以c o 璐t r u c t i o 璐o fr o t a t i o ns y m m e t r i cb o o l e a nf u n c t i o n s 谢t hm a 菇衄a k r e b r a j ci m 珊m i 填 c h a p t e r4c 0 璐t r u c t sa ut h es y m m e t r i cb o o l e a nf u u t i o n s 丽t hm 戚m 哪a l l g e b r a i c i m m u i l i t yo ne v e nn u m b e ro fv a r i a b l 鹄a n ds t u d i 鹤t h e i rd e g r e e sa n dn 0 i l l i n e a r i t i 鹤t h e m a i nm e t h o di 8t o 矗n dt h el o wd e g r e ea n i l i 址l a t o r sw h op l a yap i 、r o t a l lr o l e ，o fs y m m e t r i c b 0 0 l e 龃矗l n c t i 0 璐，a n ds t u d yt h e i rs i m p l i 6 e dv a l u ev e c t o 瑙m o r e o v e r ，w es t u d yt h es y m - m e t r i cb o o l e a n 缸c t i o n s 谢t hh i g h 以g e b r a j ci m 珊l n i 时b yl l s i n go fa8 i m i l 盯t e c h i l i q m ， a n dc o n c e n t r a t eo ns t u d y i i 培t h o s ew i t hs u b m a 菇m u ma l g e b r a i ci m m u i l i t y a sac o n 8 争 q u e n c e ，w eo b t a i n8 0 m ei m p o r t 缸l tn e c e s s 甜yc o n d i t i o 璐f o rs y l n l e t r i c 缸c t i o 璐t o 诎1 i e 、他 l l i g h 虹g e b r a l i ci m m _ t 】n i t y - c l l a p t e r5i sm 出n l yc o n e e m e d 谢t ht h es y m m e t r i cc o r r e l a t i o ni m 姗m eb 0 0 l e a n f u n c - t i o 璐w - ec o 璐t r u c ts y m m e t r i cn o n p a l i n d r o m i cc o r r e l a t i o ni 瑚m u n eb 0 0 1 e a nf h n c t i o l l sf o r 几= 6 r ，6 r + 1 ，6 r + 2a n d6 r + 3r 鹪p e c t i v e l ya n dp r o v et h a tt h ea l g e b r a i c 妇1 衄i t yo f t h e s y 如1 e t r i cp a l i n d r o i i l i cb 0 0 l e a n c t i o 璐i 8n o th i g h k e r o r d s ：址g e b r a j ca t t a c k ，a l g e b r a i ci m 础l i l i t y b a l 删n e ，a l g e b r a i cd e f ， n o n l i n e a r i t y ；c o r r e l a t i o na t t a c k ，c o r r e l a t i o ni m 瑚u n i 锄r o t a t i o n 印诅m l e t r i cb o o l e a n f u n c t i o n ，町吼m e t r i cb o o l e a nf u n c t i o n ，k r a w t d l o l l l 【p o l y n o m i a l c h i n e s el i b r a r yc l 嬲s i n c a t i o n ： t p 3 0 9 7 l v 第一章绪论 近年来，随着通信技术前所未有的飞速发展，无线移动通信中的安全保密问题 显得日益突出众所周知，目前我们所使用的密码体制包括公钥密码体制和私钥密 码体制其中私钥密码体制又分为流密码和分组密码相对于分组密码，流密码在移 动通信的应用中具有易于实现、速度快、出错概率小等优点，因此流密码算法的设 计与分析一直是国内外学者研究的热点 在许多密码体制，特别是类基于线性反馈移位寄存器( l f s r ) 的流密码体制 中，布尔函数扮演着极为重要的角色在这种密码体制中，其密钥流生成器的功能是 通过布尔函数来实现的因此所选用的布尔函数必须具有良好的密码学性质，以抵 制针对密码体制的各种攻击例如为抵制b e r l e l ( a m p m a s s e y 攻击和快速相关攻击，所 用的布尔函数必须具有较高的代数次数和较高的非线性度【5 4 ，5 9 】；为抵制区分攻击， 所用的布尔函数必须是平衡的 67 1 ；在组合器模型中，为抵制相关攻击，所用的布尔函 数还必须具有较高的相关免疫度 8 4 ，8 5 】这方面的综述性文章可参考文献 1 7 ，6 8 ，9 4 丝 1 于 自2 0 0 2 年以来，n c o u r t o i s 等人提出了一种被称为代数攻击的新的分析手段 这一攻击采用了基于代数思想的方法与技巧，将一个密码体制( 例如t o y o c r y p t 和e o 等) 的安全性问题归约到求解个超定的多变元高次方程组的问题，这与以前主要 基于概率思想的分析方法有着本质的不同随着各种可有效求解超定多变元高次方 程组方法的出现，代数攻击对许多密码体制，特别是对基于线性反馈移位寄存器的流 密码体制构成了极大的威胁 2 3 ，2 5 ，2 6 ，2 7 ，6 0 ，7 3 】譬如，c o u r t o i s 在文献 2 6 中声称 只需2 0 k b y t e s 的密钥流便可在2 4 9 个c p u 时间内破解t o y o c r y p t ，并且可在2 5 7 个c p u 时间内破解l i l i 一1 2 8 而此前这两种密码系统被普遍认为是非常安全的 n c o u r t o i s 和w m e i e r 在文献f 2 6 1 中提出了布尔函数的代数免疫度的概念为 抵制代数攻击，用于上述密码体制中布尔函数必须具有高的代数免疫度m 元布尔 函数的代数免疫度最大可能值为等 目前已有多种方法能构造出达到最高代数免 疫度的布尔函数这些方法有：迭代构造法，该方法可以不断由变元少的布尔函数 得到变元多的布尔函数f 1 8 ，2 8 1 ；转化成判断某个齐次线性方程组是否只有零解的 第一章绪论 方法 4 ，3 0 ，6 9 】；利用线性空间的仿射子空间的性质的方法 1 3 ，3 9 ，8 8 】；寻找二元域 上非奇异矩阵的可逆子矩阵的方法f 4 8 ，4 9 】；重量支撑集方法 5 0 ，5 1 ，7 0 】以及其他方 法( 参见文献【3 5 ，3 6 ，1 0 2 】等) 但是通过这些方法所构造出来的布尔函数，其非线性 度往往还不够高这在一定程度上限制了它们的实用价值在2 0 0 8 年亚洲密码会 议( a s i a c r ：，t ) 上，c c a u r l e t 和k f e n g 提出了利用特征为2 的有限域中的本原元 来构造具有最高代数免疫度的布尔函数的新方法他们所构造的布尔函数不仅具有 最高的代数免疫度，而且具有很高的非线性度，并且其代数次数也达到最优【1 9 】此 后许多学者开始致力于寻找同时具有多种好的密码学性质的布尔函数【8 9 ，9 0 ，9 2 ，9 8 其中，z n 和y d e n g 在文献 1 9 】的基础上，基于一个排列组合的猜想在p 孓类b e n t 函数中发现了两类具有最高代数免疫度的偶元布尔函数这些布尔函数的非线性度 比之前构造的具有最高代数免疫度的布尔函数都要高他们的研究还表明，b e n t 函 数的代数免疫度可以取到除1 以外的任意值( 参见【9 0 】) 不足的是，由于这些布尔函 数都是由b e n t 函数构造而来，因此它们抵制快速代数攻击的能力不强 1 4 ，9 1 】 我们考虑了构造具有最高代数免疫度的布尔函数的新方法，推广了文献【3 0 】中 构造主函数的方法，得到了一大类新的具有最高代数免疫度的布尔函数此外，类似 于c c 甜l e t 和k f e n g 的构造，我们在文献 9 2 1 中利用特征为2 的有限域上的本原多 项式构造了几类具有最高代数免疫度的布尔函数所构造的函数的代数次数也达到 最优，并且我们还得到了更高的非线性度下界估计 旋转对称布尔函数中存在许多具有良好密码学性质的函数例如已经发现的 几类具有超高非线性度的奇元旋转对称布尔函数，它们的非线性度甚至超过了所谓 的b e n t 串联界( 参见 4 3 ，“，6 6 】) 因此，旋转对称布尔函数引起了众多学者的关注但 是寻找具有好的密码学性质的旋转对称布尔函数一般都需要依赖于计算机搜索然 而，由于旋转对称布尔函数空间规模相对较大，约为2 等，这样的搜索往往非常困难 目前，从理论上构造具有最高代数免疫度旋转对称布尔函数的工作，如文献 3 9 ， 6 1 ，8 0 1 等，大多是基于已有的构造具有最高代数免疫度的一般布尔函数的方法之上 的例如，文献【3 9 ，8 0 】利用改变主函数在某些轨道上的函数值的办法来构造具有最 高代数免疫度的奇元旋转对称布尔函数文献 3 9 】利用了文献【1 3 】中的结论来构造 具有最高代数免疫度的偶元旋转对称布尔函数此外，文献【8 0 】利用了f 2 0 】中的结论 来构造具有最高代数免疫度的偶元旋转对称布尔函数 本文研究了具有最高代数免疫度的奇元旋转对称布尔函数的基本构造问题我 们将该问题转化成一个二项式系数和式的奇偶性判定问题和二元域上可逆循环矩 2 第一章绪论 阵的构造问题对这两个问题的研究得到了部分结果，并由此构造了几类具有最高 代数免疫度的旋转对称布尔函数。这个工作是此前具有最高代数免疫度奇元旋转对 称布尔函数构造方法的推广 对称布尔函数是一类特殊的旋转对称布尔函数其结构简单，占用的存储空间 相对很小，因此实用性强，在流密码中应用非常广泛 9 3 1 国内外学者对对称布尔函 数密码学性质的研究也非常活跃 对于奇元的情形，n l i w q i ，l q u ，c “以及k f e n g 等证明了只有主函数及 其补函数才具有最高代数免疫度 4 7 ，7 2 】然而，这些函数的非线性度在所有具有最高 代数免疫度的布尔函数中是最低的 5 4 】在偶元对称布尔函数中，具有最高代数免疫 度的函数则要多得多a b r a u e k e n ，d k d a l a i ，s m a i t r a ，l q u ，k f e n g 以及y c h e n 等此前就已经分别构造出多类此种函数( 参见文献 4 ，2 1 ，2 9 ，3 0 ，5 1 ，6 9 ，7 l 】等) 此外， 文献 4 ，4 7 ，7 1 】中还得到了偶元对称布尔函数达到最高代数免疫度的一些必要条件 但是只有达到最高代数免疫度的2 m 一元对称布尔函数被完全找出 5 1 ，7 1 在这个工 作中，作者使用了一种被称之为重量支撑集的方法通过这种方法，构造所有代数免 疫度大于等于d 的伽元对称布尔函数的问题就转化成了确定集合w s m i n ( 礼，d ) 的问题， 即对任意整数o b d ，决定所有次数小于d 一6 的( 佗一2 6 ) 元对称布尔函数的重量 支撑集在包含关系下的极小元然而，这仍然是一个非常复杂的问题l q u 和c “ 确定了所有只含两个元素的极小元，并且研究了包含3 个或者4 个元素的极小元 7 0 】 此外，重量支撑集方法还被用来构造所有具有次高代数免疫度2 m _ 1 的( 2 m + 1 ) 一元对 称布尔函数 5 0 l 但总的来说，除了( 佗，d ) = ( 2 m ，2 m - 1 ) 或者( 2 仇+ 1 ，2 m _ 1 ) 的情形以外， 还没有很好的办法来确定集合w s m i n ( 佗，d ) 本文中我们研究了对称布尔函数的几类低次零化子值的分布虽然我们还不能 确定它们的重量支撑集是否都是极小的，但这些重量支撑集都满足某些特殊规律利 用这些规律我们得到了对称布尔函数达到较高代数免疫度的一些必要条件特别地， 我们找出了所有具有最高代数免疫度的偶元对称布尔函数我们发现这些函数都不 是平衡函数( n 4 ) 同时我们还研究了它们的代数次数及非线性度其最高可能达 到的非线性度为2 n 一 ( z 2 ) + ( n 2 2 。们j ) ，离b e n t 函数的非线性度2 舻1 2 1 还 有较大的差距因此我们又继续研究了具有次高代数免疫度的偶元对称布尔函数， 以期能在这类函数中找到同时还具有高非线性度的函数我们得到了( 2 七) 元对称布 尔函数达到次高代数免疫度七一1 的一些必要条件，且当后为奇数时我们猜想这些必 要条件同时也是充分的 3 第一章绪论 相关免疫性是衡量流密码体制安全性的另一个重要指标它是由t s i e g e n t h a l e r 在文献【8 4 】中提出的，主要是为了抵制相关攻击在本文中，我们研究了对称相关免 疫布尔函数的构造问题 经过2 0 多年的发展，对布尔函数相关免疫性的研究已经取得了非常丰富的理论 成果，例如文献 2 ，6 ，7 ，1 5 ，1 6 ，7 5 】等关于相关免疫布尔函数的构造与计数方面，读者 可参见文献【2 2 ，3 2 ，3 3 ，5 7 ，6 5 ，1 0 4 1 等还有许多学者研究了相关免疫函数的代数次数 及非线性度等性质，如文献【9 ，1 2 ，3 7 ，6 4 ，7 6 ，7 8 ，8 3 ，1 0 6 】等另外，对称相关免疫布尔函 数的性质及构造方面的研究也有很多重要的工作，读者可参见文献 1 0 ，4 1 ，6 3 ，7 9 ，9 5 】 等目前已经知道，对称回文布尔函数是结构最简单且数量最多的一类对称相关免 疫函数( 参见 6 3 ，8 7 ，9 5 】等) 而对于对称非回文相关免疫布尔函数，p s a r l c a r 和s m a i t r a 给出了几个构造方法在他们的构造中，礼+ 1 ，n + 2 或者礼+ 3 是完全平方 数【7 9 】 我们通过利用已经得到的对称布尔函数达到较高代数免疫度的必要条件，证明 了对称回文布尔函数的代数免疫度都不高因此，对称非回文相关免疫布尔函数的 构造就显得非常重要我们借助于3 次本原单位根的性质得到了一些二项式系数恒 等式，从而对死= 6 r ，6 r + 1 ，舒+ 2 ，6 r + 3 的情形分别构造了对称非回文相关免疫布 尔函数我们还得到了一个二次构造方法，可以通过己知的对称相关免疫布尔函数 来构造新的对称相关免疫布尔函数 1 2基本知识介绍 1 2 1 布尔函数的基本概念和基本性质 用昭表示二元域砸2 = o ，1 ) 上的m 维向量空间f 2 上的加法用。和0 t ( 连加) 来表示从叼到2 的映射称为伽元布尔函数，记为，= ，( z 1 ，z n ) 可以用一个长 为2 n 的二进制串 ，( 0 ，o ，o ) ，( 1 ，o ，o ) ，( 1 ，1 ，1 ) 】 来表示，这个二进制串称为，的真值表此外，每个伽元布尔函数都可以看成环 f 2 z 1 ，z 竹】( z ；oz 1 ，z ioz n ) 4 第一章绪论 相关免疫性是衡量流密码体制安全性的另一个重要指标它是由t s i e g e n t h a l e r 在文献【8 4 】中提出的，主要是为了抵制相关攻击在本文中，我们研究了对称相关免 疫布尔函数的构造问题 经过2 0 多年的发展，对布尔函数相关免疫性的研究已经取得了非常丰富的理论 成果，例如文献 2 ，6 ，7 ，1 5 ，1 6 ，7 5 】等关于相关免疫布尔函数的构造与计数方面，读者 可参见文献【2 2 ，3 2 ，3 3 ，5 7 ，6 5 ，1 0 4 1 等还有许多学者研究了相关免疫函数的代数次数 及非线性度等性质，如文献【9 ，1 2 ，3 7 ，6 4 ，7 6 ，7 8 ，8 3 ，1 0 6 】等另外，对称相关免疫布尔函 数的性质及构造方面的研究也有很多重要的工作，读者可参见文献 1 0 ，4 1 ，6 3 ，7 9 ，9 5 】 等目前已经知道，对称回文布尔函数是结构最简单且数量最多的一类对称相关免 疫函数( 参见 6 3 ，8 7 ，9 5 】等) 而对于对称非回文相关免疫布尔函数，p s a r l c a r 和s m a i t r a 给出了几个构造方法在他们的构造中，礼+ 1 ，n + 2 或者礼+ 3 是完全平方 数【7 9 】 我们通过利用已经得到的对称布尔函数达到较高代数免疫度的必要条件，证明 了对称回文布尔函数的代数免疫度都不高因此，对称非回文相关免疫布尔函数的 构造就显得非常重要我们借助于3 次本原单位根的性质得到了一些二项式系数恒 等式，从而对死= 6 r ，6 r + 1 ，舒+ 2 ，6 r + 3 的情形分别构造了对称非回文相关免疫布 尔函数我们还得到了一个二次构造方法，可以通过己知的对称相关免疫布尔函数 来构造新的对称相关免疫布尔函数 1 2基本知识介绍 1 2 1 布尔函数的基本概念和基本性质 用昭表示二元域砸2 = o ，1 ) 上的m 维向量空间f 2 上的加法用。和0 t ( 连加) 来表示从叼到2 的映射称为伽元布尔函数，记为，= ，( z 1 ，z n ) 可以用一个长 为2 n 的二进制串 ，( 0 ，o ，o ) ，( 1 ，o ，o ) ，( 1 ，1 ，1 ) 】 来表示，这个二进制串称为，的真值表此外，每个伽元布尔函数都可以看成环 f 2 z 1 ，z 竹】( z ；oz 1 ，z ioz n ) 4 第一章绪论 中的元素，反之亦然因此，每个m 元布尔函数都可以唯一地表示成如下的多项式： ，( 钆 ) = 0o ， j 1 ，2 ，n i ， 这里每个口，都是i 2 中的元素这个多项式称为，的代数标准型( a n f ) 其中具有 非零系数的单项式中最大的变量个数称为，的代数次数，记作d e g ( ，) ，即d e g ( ，) = m a x _ 1 ，i fo ，= 1 ) 我们这里规定零函数的代数次数为一。代数次数小于等于1 的布 尔函数称为仿射函数伽元仿射布尔函数的全体记为磊我们用如来表示所有伽元 布尔函数构成的集合。并用b ( 佗，d ) 表示所有次数小于d 的n 一元非零布尔函数构成的 集合 定义1 1 设s = ( s 1 ，) 昭，称集合s u p p ( s ) = is i = l 为向量s 的支撑集支 撑集中元素的个数称为s 的汉明重量，记为w t ( s ) ，即w t ( s ) = 警1 定义1 2 设，b 竹，我们称集合s u p p ( ，) = z 赡i ，( z ) = l 】为，的支撑集支撑集 中的元素个数称为，的汉明重量，记作w t ( ，) 我们称j p 是平衡函数，若w t ( ，) = 2 n 对于给定的布尔函数，b n ，任意满足，9 = o 的布尔函数9 称为，的零化 子 定义1 3 设厂，的代数免疫度，记作a i ( ，) ，是指，和厂o1 的非零零化子的最 低次数，即 a i ( ，) = m i n d e g ( 夕) l9 o ，9 = o 或者( ，o1 ) 9 = o 对一个扎元布尔函数，显然有，( 厂o1 ) = o 因此根据代数免疫度的定义可知， a i ( ，) d e g ( ，) 如果，在昭的一个舡维仿射子空间上为常数，则有a i ( ，) n 一忌 1 0 0 ，1 0 3 】另外，文献【2 7 ，6 0 】中已经证明，一定有a i ( ，) 等1 并且该上界是紧的， 即对任意自然数礼，都存在代数免疫度为登 的佗一元布尔函数： 命题1 1 膨，3 刃设，满足? ( 1 ) 若n 为奇数，则 ， 他) ： 1 1 09 “功孚； 【o ，学sw t ( z ) n 5 第一章绪论 m ，= 仁篙二 m ( ，) 2 忠d ( ，力 非线性度是衡量布尔函数密码学性质好坏的一个极为重要的指标 5 9 ，8 2 】一般 来说，如果一个布尔函数具有高的代数免疫度，那么它的非线性度也不会很低在文 献 5 4 】中，作者证明了 2 a 喜2 ( i l l ( ，) 2 ( n 了1 ) ， 扛：0 、 。 7 并且还构造了一类非线性度能达到该下界的布尔函数 设，b n ，的w 砒s h 变换是按如下方式定义的一个实值函数( 见【3 4 ，5 6 】) ： w 加) = ( 一1 ) m ) 一，vu 昭 z f 呈 这里u = ( u 1 ，) ，z = 1 ，z n ) ，它们的点积u z ：= 0 圣1 研 第一章绪论 称w ，) 昭) 为，的w a l s h 谱通过简单的计算可得非线性度与w a l s h 谱之 间的一个关系式： n l ( ，) = 2 肛1 一三躞1 w 加 由p a r s e 、r a l 公式u 昭w ；p ) = 2 2 n 可知，对于几为偶数的情形，当所有w a l s h 谱值都相等时，布尔函数的非线性度取得最大值2 竹一2 暑一这样的布尔函数称 为b e n t 函数关于b e n t 函数的构造及其非线性度等的研究工作非常多，读者可参见 文献 1 1 ，6 2 ，7 4 ，9 6 等当扎为奇数时，称由两个( 礼一1 ) 一元b e n t 函数的真值表串联起 来得到的一个伽元布尔函数的非线性度2 n 一2 孚为b e n t 串联界 定义1 5 称一个礼一元布尔函数，是对称的，如果函数值在对称群s n 的作用下不变 换言之，如果对任意两个具有相同汉明重量的输入向量z ，! ，赡，都有，( 茁) = ，( 可) ， 则称，是对称布尔函数 我们记全体伽元对称布尔函数的集合为s 硫，并记全体次数小于d 的伽元非零对 称布尔函数的集合为s b ( n ，d ) 根据定义，每个伽元对称布尔函数，可以由一个二元向量 叼= ( 口，( o ) ，u ，( 1 ) ，口，( 扎) ) f + 1 来表示，其中分量u ，( z ) 表示汉明重量为i 的输入向量的函数值口，称为，的简化值 向量对任意，s 取，如无特殊声明，我们都记，7 ( z 1 ，z n ) = ，( z 1o1 ，z no1 ) 易知，7 与，仿射等价，d e g ( 厂7 ) = d e g ( ，) ，且口，小) = 口，( 佗一i ) 对所有o z 佗成立 另一方面，的代数标准型也可写成 竹 ，( ，z n ) = 0a 巾) 回， i = 0 其中每个a ，( i ) 都是f 2 中的元素，每个盯表示次数为i 的n 一元齐次对称布尔函数即 礼 ，簖= 扛= l 二元向量a ，= ( a ( o ) ，a ( 1 ) ，a ( 礼) ) 昭+ 1 称为，的简化代数标准型可，与a ，都可 以看成是从集合 o ，l ，扎】到昭+ 1 的映射 7 巧 。一 = n 0 试 = 第一章绪论 定义1 6 俐布尔函数，b 几称为是相关免疫的，如果对任意1 i 佗，都有 p r 。6 ( ，( z 1 ，z n ) = z t ) = 三 成立，其中每个( z 1 ，z n ) 以相同概率从向量空间昭中选取 注意到代数次数为1 的布尔函数都是平衡函数，根据定义，显然两个次数为1 的伦元对称布尔函数都是相关免疫的 定义1 7 二项式系数( ? ) 是指个不同的物体中挑选出 个的方法数，用算式表示 就是 ( ：) = 鼎， 其中o i 仃而当i 佗时，定义( ? ) = o 定义1 8 对二元向量z = ( z l ，z 竹) 与秒= ( 耖1 ，) ，我们称z5 可，如果s u p p ( z ) s u p p ( 可) ，即甄玑对任意1 i n 都成立对两个非负整数。与6 ，设其二进制展开 分别为 n = ( ，一l ，d 0 ) 2 ，6 = ( 6 m ，6 m 一1 ，6 0 ) 2 ， 即o = 勘啦2 ，6 = 跺。幻，我们称n56 ，如果( ，一1 ，n o ) 5 ( 6 m ，h - 1 ，6 0 ) 若a56 且n 6 ，我们用口 6 来表示 例1 1 设口= 5 = ( 1 0 1 ) 2 则p 65o ) = 0 ，1 ，4 ，5 ) ， 6l6 o = t o ，1 ，4 ， 对任意z ，p 叼，我们记扩= 饕1 由定义1 8 知，= 1 当且仅当p ! z 由 此可得礼一元布尔函数，( 茁) = 0 p 巧的函数值与系数之间的转换关系式： ，( z ) = on p ，vz 赡， ( 1 2 1 ) p f 呈，p ! z 以及 = o ，( z ) ，v 肛昭 ( 1 2 2 ) 。f ；，霉! p 定义1 9 称65 ，o ，如果6 = o ，或者存在某个整数o f m ，使得6 = ( o f ，n f 一1 ，n o ) 2 换言之，61 7n 当且仅当6 的二进制展开向量是。的二进制展开向量的一个呢巴” 我们记6 _ 7o ，若65 7 口且6 口 8 第一章绪论 侈0 1 2 设o ；5 = ( 1 0 1 ) 2 ，贝0 6i 65o ) = o ，1 ，4 ，5 ， 661 7 口】= o ，1 ，5 ) ， 66 = o ，1 ) 由著名的l u c a s 公式( 可参见 3 8 】) 可知 ( 莒) 三( 芝) ( 砂- ( 芝) m o a 2 ， 所以( ；) 三1m o d 2 当且仅当6 墨o 由此可得 啪) 2 q 州七) ( 三) 2q 州七) ( 1 2 3 ) 后= 0 、7 知 o ，则c n 在n 维向量空间嵫上的 作用定义为 以( z 1 ，z 2 ，z 礼) = ( z l + i ，z 2 + t ，z n + t ) ， 这里七+ i ( 1 尼竹) 取值尼+ im o d 礼，为了与变量z 1 ，z 2 ，z 几的下标1 ，2 ，n 统一起来，当充+ m o dn = o 时，克+ i 取值为他而非o m 元布尔函数，称为旋转 对称函数是指对任意的输入向量( z 1 ，z 2 ，z 几) 昭及任意整数1 i 仃一1 ，都 有厂( p 毳( z 1 ，z 2 ，z n ) ) = ，( z 1 ，z 2 ，z n ) 我们记向量z = ( z 1 ，z 2 ，z 竹) 在循环群作 用下生成的轨道为g 茹，即有g z = _ 反( z 1 ，z 2 ，z 他) l1 z 礼) 所有这样的轨道个 数记为鼽则礼元旋转对称布尔函数的数量为2 鼽设妒是e u l e rp h i - 函数，由b u r n s i d e 引理可得( 参见 8 6 ) 铷= 击惫i n ( 惫) 2 鼍 1 2 2 布尔函数的重量支撑集 本小节我们简要介绍由k f e n g 等为便于研究对称布尔函数而提出的重量支撑 集的方法( 参见 5 0 ，5 1 1 ) 下面首先定义布尔函数的重量支撑集 9 第一章绪论 定义1 1 1 设几2 且= o ，1 ，礼 对于布尔函数，b n ，其重量支撑集定义为 w s ( ，) = i ijz 8 u p p ( ，) s t w t ( z ) = i ) 特别地，若，s b n ，我们有w s ( ，) = il ，( i ) = 1 ，对于集合t b 竹，记w s ( t ) = w s ( 9 ) i9 t ，并且记w s m i n ( t ) 为偏序集( w s ( t ) ，) 中的极小元全体 例1 3 设t = ( ，2 ，3 ) b 2 ，其中 = z 1 ，2 = z loz 2 且 = z 1o z 2o1 显然 有s u p p ( ) = ( 1 ，o ) ，( 1 ，1 ) ) ，s u p p ( 尼) = ( 1 ，o ) ，( o ，1 ) ) 山u p p ( ) = ( o ，o ) ，( 1 ，1 ) 所 以w s ( ) = 1 ，2 ) ，w s ( 丘) = 1 ，w s ( 矗) = o ，2 ，从而w r s m i n ( t ) = 1 ， o ，2 】| 对每个整数os6 【鸶j ，我们勘为依赖于变量茁n 一2 1 ，一2 2 ，的按如 下定义的( 2 6 ) 元布尔函数： 娜：卜一o ； l ( 一2 6 + 1o z n 一2 2 ) ( 一2 3 0 一2 4 ) ( 一lo ) ，6 1 易知w s 溉) = 6 并且对任意的布尔函数，s b n 一幼，我们有加，且d e g ( 伽) = d e g ( ，) + 6 w s ( ，珊) = w s ( ，) 舶这里对一个整数集的集合a 以及整数z ，我们记a + z = 【 s + fs s ) ，s a ) 下面的引理对于处理对称布尔函数的零化子非常重要该引理表明，当我们考 虑对称布尔函数的低次零化子时，只需考虑其中一类比较特殊，数量相对较少的零 化子即可 引理1 1 俐设佗2 且，s 取若存在某个非零布尔函数9 b n ，使向= 0 ，则