（基础数学专业论文）对称布尔函数的密码学性质及应用.pdf

中文摘要 摘要 布尔函数广泛应用于密码体制和密码协议的构造中它的密码学性质直接 影响着密码体制和密码协议的安全，因此对布尔函数的研究具有十分重要的意 义本文主要讨论一类特殊的布尔函数一对称布尔函数的密码学性质，并且利用 对称布尔函数构造出具有较好密码学性质的新函数 对称布尔函数是一类特殊的函数，它的输出值只与输入变量的权重有关输 入变量的权重相同，则函数值相同那么一个扎元对称布尔函数就可以由一个 佗+ 1 维向量表示，这种表示简单方便，更有利于对函数进行研究所有的n 元对 称布尔函数构成一个佗+ 1 维向量空间因此佗元对称布尔函数的计数为2 - + 1 由于对称布尔函数形式的特殊性，我们有必要研究它具有哪些特殊的密码学性 质 平衡性是密码函数应具备的基本性质，同时具备平衡性和对称性的函数叫做 平衡对称布尔函数许多文献已经证明了存在这样的函数，但是对这类函数的密 码学性质的研究却很少因此，这类函数中是否存在具有优良性质的，可以应用于 密码体制中的布尔函数，就成了一个公开的问题要弄清这些问题，就要研究这类 函数的密码学性质对于变元的个数n 取不同值时，这类函数的性质是完全不同 的于是我们分别对佗取奇数和偶数两种情况进行讨论 本文从对称布尔函数的表示方法出发，通过建立它的简化值向量与简化的代 数正规型向量之间的关系，分别详细研究了对称布尔函数的代数次数，非线性度， 弹性，扩散性质，线性结构以及对称布尔函数的代数免疫等性质同时，对于行为 奇数时，我们研究了平凡平衡布尔函数的某些性质；对于仃为偶数时，我们研究了 非平凡平衡对称布尔函数的性质最后我们还讨论了如何应用对称布尔函数构造 出具有较好密码学性质的布尔函数 关键词：布尔函数；对称布尔函数；平衡性；非线性度；弹性；扩散性质；代数免疫 湖北大学硕士学位论文 a b s t r a c t b o o l e a nf u n c t i o n sh a v eb e e na p p l i c a t e de x t e n s i v e l yi nt h ec o n s t r u c t i o no fc r y p t o s y s e t m sa n dc r y p t o p r o t o c o l s 1 1 1 ec r y p t o g r a p h i cp r o p e r t i e so fb o o l e a nf u n c t i o n sg i v e a d i r e c t l yi n f l u e n c eo nt h es a f eo fc r y p t o s y s t e m sa n dc r y p t o p r o t o c o l s t h e r e f o r e ，i ti s v e r yi m p o r t a n tt or e s e a r c ht h ep r o p e r t i e so fb o o l e a nf u n c t i o n s t h i sp a p e rg i v ead e t a i l s t u d yo nt h ec r y p t o g r a p h i cp r o p e r t i e so fs y m m e t r i cb o o l e a nf u n c t i o n s a tt h es a m e t i m e ，w eh a v ec o n s t r u c t e ds o m eb o o l e a nf u n c t i o n sw h i c ha r eb a s e do nt h es y m m e t r i c f u n c t i o n s s y m m e t r i cf u n c t i o n si sac l a s so fs p e c i a lb o o l e a nf u n c t i o n i t so u t p u ti sd e c i d e d b yt h ew e i g h to fi n p u t ，i ft h ei n p u tv a r i a b l e sh a v es a m ew e i g h t ，t h e nt h e yh a v es a m e o u t p u t s ot h a t ，as y m m e t r i cb o o l e a nf u n c t i o nc o u l db er e p r e s e n t e db yan + 1 d i mv e c t o r , a n da l lt h es y m m e t r i cf u n c t i o n sf o r mav e c t o rs p a c ew i t h 讫+ 1 - d i m i nv i e wo ft h e s p e c i a lf o r mo fs y m m e t r i cf u n c t i o n s ，w ea r ei n t e r e s t e di ns t u d y i n gt h i r ec r y p t o g r a p h i c p r o p e r t i e s b a l a n c e d n e s si sab a s i cp r o p e r t yt h a tac r y p t o g r o p h i cf u n c t i o nm u s th a s af u n c t i o ni sc a l l e db a l a n c e ds y m m e t r i ci fi th a sb a l a n c e da n d s y m m e t r i cp r o p e r t i e ss i m u l t a n e o u s i th a sb e e np r o v e db yl o t so fa u t h o r st h a tt h e r ea l es o m eb a l a n c e ds y m m e t r i c b o o l e a nf u n c t i o n s ，b u th a sn o tr e s e a r c h e do nt h e i rp r o p e r t i e s t h e r e f o r e ，i ti sa p u b l i c p r o b l e m t os e a r c hf o rb a l a n c e ds y m m e t r i cb o o l e a nf u n c t i o n sw i t hb e t t e r c r y p t o g r o p h i c p r o p e r t i e s w ek n o wt h a tt h i sc l a s sf u n c t i o n sh a v ed i f f e r e n tp r o p e r t yu n d e rd i f f e rc o n d i t i o n so fn s ot h a tw e s t u d yt h e mr e s p e c t i v e l yo nn b eo d da n db ee v e ni n t e g e r t h i sp a p e r b e g i nf r o mt h er e p r e s e n t a t i o n so fb o o l e a nf u n c t i o n s ，a n dt a l ka b o u t t h ed e g r e e ，n o n l i n e a r i t y ，r e s i l e n c e ，p r o p a g a t i o np r o p e r t ya n da l g e b r a i ci m m u n i t yo fa b a l a n c e ds y m m e t r i cb o o l e a nf u n c t i o n sr e s p e c t i o n l y w h e nni sa o d di n t e g e r , w eh a v e s t u d i e dt h ec r p t o g r a p h i cp r o p e r t i e so fs y m m e t r i cb o o l e a nf u n c t i o n sw h i c hi st r i v i a lb a l a n c e d ，a n dt h ec r p t o g r a p h i cp r o p e r t i e so fn o n t r i v i a lb a l a n c e db o o l e a nf u n c t i o n sw h e n ni se v e n a tl a s t w eg i v es o m ec o n s t r u c t i o nm e t h o d so fb o o l e a nf u n c t i o n sw i t hb e t t e r p r o p e r t i e s k e yw o r d s ： b o o l e a nf u n c t i o n ；b a l a n c e dp r o p e r t y ；n o n l i n e a r i t y ；r e s i l e n c e ；p r o p a g a t i o np r o t e r t y ；a l g e b r a i ci m m u n i t y 一一 湖北大学学位论文原创性声明和使用授权说明 原创性声明 本人郑重声明：所呈交的论文是本人在导师的指导下独立进行研究所取得 的研究成果。除了文中特别加以标注引用的内容外，本论文不包含任何其他个 人或集体已经发表或撰写的成果作品。对本文的研究做出重要贡献的个人和集 体，均已在文中以明确方式标明。本人完全意识到本声明的法律后果由本人承 担。 论文作者签名：萋毫。屎 签名日期：茹年j 月引e 1 学位论文使用授权说明 本学位论文作者完全了解学校有关保留、使用学位论文的规定，即： 按照学校要求提交学位论文的印刷本和电子版本；学校有权保存并向国家 有关部门或机构送交论文的复印件和电子版，并提供目录检索与阅览服务：学 校可以允许采用影印、缩印、数字化或其它复制手段保存学位论文；在不以赢 利为目的的前提下，学校可以公开学位论文的部分或全部内容。( 保密论文在 解密后遵守此规定) 论文作者签名； 鬃前卷 签名日期：d 8 年5 月弓1 日 名：慰团 签名日期玑叼璋6 影e 1 1 绪论 1 1研究意义 1绪论 在当今信息社会，信息安全越来越受到重视，从而极大的推动了信息安全 的核心一密码学的发展密码学研究的主要内容是密码体制和密码协议我们现 在使用的密码体制主要有两种：公钥密码和私钥密码体制公钥密码体制对于通 信环境的安全性要求相对较弱，但它的最大缺点是结构复杂，速度也比较慢私 钥密码体制正好相反，它的结构及实现都比较简单，并且速度非常快，但它的私钥 必须是保密的，同时还要解决私钥交换问题要实现密钥的保存与交换是一个十 分复杂的问题因此现实中使用的密码方案一般都是两种体制的结合：使用公钥 密码体制来生成和交换密钥，使用私钥密码体制来传输大部分的数据【1 1 流密码【2 】和分组密码f 3 】是实现私钥密码体制的两种基本方式对于流密码， 最常用的密钥流生成器是非线性组合生成器，它们的安全性能与所选用的滤波 函数和组合函数有非常密切的关系而滤波函数和组合函数都是布尔函数【4 】因 此，要提高生成器的安全性能，必须采用具有好的密码学性质的滤波函数和组合 函数从而构造具有良好密码学性质的布尔函数显得尤为重要【5 ，6 1 同时具有优越 性质的布尔函数还可以用于够造序列【7 8 1 对称布尔函数从t o m e s c u 提出后就得到，“泛关注，特别是进入2 1 世纪以来 c a n t e a u t ，v i d e a u ，和b r e a k e n 等人对对称布尔函数的研究做了许多工作，他们分 别研究了对称布尔函数的平衡性，非线性性，非退化性，非相关性和代数免疫性等 等【6 ，5 1 但是，对于对称布尔函数的研究还不是很完全，人们甚至还不清楚是否存 在各种性质都比较好的，可以应用于密码体制中的对称布尔函数对称布尔函数 有很多优点，比如：对称布尔函数的表示简单，需要的存储空间大大减少，并且机 器实现容易如果把它应用于流密码体制中，将会大大提高加密，解密的效率对 称布尔函数的这些优点足以吸引我们去研究它的其它密码学性质，从而找出适合 选作滤波函数的对称布尔函数 1 2 研究背景 为了得到具有较好密码性质的对称布尔函数，在文献【9 】中，作者d a l a i 等人 通过改变对称布尔函数某一点的函数值，构造出了含有奇变元的，具有最大代数 湖北大学硕士学位论文 免疫的布尔函数于是我们考虑是否可以利用l 司样的方法，构造出具有较好其它 密码性质的布尔函数同时我们还可以考虑，对于偶变元的情况，是否也可以构造 同样的函数 在文献【l o 】中，c a n t e a n t 等比较系统的讨论了对称布尔函数的性质文章首 先讨论了对称布尔函数的代数次数与它的简化值向量的关系，同时还讨论了对 称布尔函数的弹性和扩散性质文中对于奇变元的情况，提出了平凡平衡布尔函 数的概念，从而确立了一种特殊的布尔函数但对于这种特殊布尔函数的性质却 没有深入研究并且对于偶变元的情况，是否存在平凡平衡的对称布尔函数。这 些函数具有哪些密码学性质都有待考虑 在文献【l l 】中，b r a e k e n 等研究了对称布尔函数的代数免疫，文章证明了存 在对称布尔函数，其代数免疫可以达到最优文献【1 1 】还证明了对于每个奇数 凡，存在唯一一个平凡平衡对称布尔函数，使其代数免疫达到最优有些文章利 用了对称布尔函数的这个特点，通过改变某些点处的函数值，构造出了具有较好 其它性质的密码函数 对于如何构造具有较好密码学性质的布尔函数这一课题，研究成果较多 y z h e n g 等提出了通过级联两个或多个函数构造新函数的方法【l 芍m a i o r a n a 和 m c f a r l a n d 提出了具有较好密码学性质的m m 类函数【1 3 】通过改变函数某点函 数值也是构造新函数的方法z e n g 等构造了具有较好密码学性质的完备非线性 函数【1 4 ，1 5 , 1 6 1 ，将这些方法综合起来，以对称函数为基础，构造新的具有较好密码学 性质的布尔函数，也是一项很有挑战性的工作 1 3 本文的主要研究工作和内容安排 本文主要研究的是奇变元平凡平衡布尔函数和偶变元非平凡平衡布尔函数 的性质，以及对称布尔函数在构造具有较好密码学性质的新函数中的应用 具体内容安排如下： 第二章介绍了本论文中用到的一些基本概念和基本结论 第三章归纳总结了对称布尔函数的密码学性质对称布尔函数的代数次数具 有特殊的性质，它的大小与函数的简化值向量的周期性有关对称布尔函数的线 性结构比较简单，除平凡的线性结构外，只可能有向量1 作为它的线性结构对 于偶变元对称布尔函数，j 有二次函数可以达到最大的非线性度。也就是对称的 b e n t 函数全都是二次的在分析对称布尔函数的代数免疫时发现存在对称函数， 2 1 绪论 使其代数免疫达到最优 第四章讨论了两种特殊的对称布尔函数的性质对于礼是奇数的情况，多数 平衡布尔函数为平凡平衡的我们给出了这类函数的一些重要密码学性质对于 佗是偶数的情况，我们定义了非平凡平衡布尔函数，并简单讨论了这类函数的密 码学性质 第五章构造了具有较好密码学性质的布尔函数我们以对称布尔函数为基 础，通过级联的方法和改变函数某点处值的方法，构造出性质较优的布尔函数 3 湖北大学硕士学位论文 2 布尔函数的基本概念及基本结论 在这篇论文中，我们研究的主要是对称布尔函数的一些密码学性质，同时研 究了具有较好密码学性质的布尔函数的构造为了以后讨论方便，我们首先介绍 一下后面将要用到的一些基本概念和一些常用的结论 2 1 布尔函数的定义和表示方法 我们用f 2 来表示元素为0 和1 的二元有限域，用曰表示含有2 n 个元素的 有限域，其中的加法运算用来表示一个关于n 个变量z 1 ，勋，z n 的布尔 函数是从毋到最的函数我们以后总是称有n 个变量的布尔函数为毋上的函 数毋上的所有布尔函数作成一个集合，记为鼠 设z 是毋上的一个n 维向量，令z = ( z 1 ，z 2 ，z n ) ，那么向量z 的汉明权 重w t ( z ) 定义为：z 中不为0 的坐标的个数即 伽芒( z ) = 兢 i = 1 一个布尔函数，( z ) 的汉明权重w t ( 1 ) 定义为：曰中使得厂( z ) 不为0 的z 的 个数也就是鲫亡( ，) = i z 曰i f ( x ) 0 l ，其中 f 表示集合中元素的个数 设厂，g 玩，厂和g 的汉明距离d ( f ，g ) 定义为： d ( f ，9 ) = i z f ：；li f ( x ) 夕( z ) ) 1 我们经常用真值表来表示一个布尔函数，也就是用函数的2 扎个函数值作成 的向量( ，( o ) ，( 1 ) ，f ( 2 n 一1 ) ) 来表示鼠中的布尔函数和向量空间k n 中的 向量是对应的，埘此n 元布尔函数的计数为2 2 n 通常我们还把布尔函数f ( x ) 表示成个具有礼个变量的多项式： 4 兄 入 o z 。试 ， 2 ，则，扛) 满足s a c ( k ) 当且仅当每个变量x i 至少在 代数正规型中后+ 1 个二次项巾出现，这里0 ks 佗一2 以上定理说明，在布尔函数不一性质之间存在着复杂的关系有些是等价 的，如p c ( n ) 函数和b e n t 函数，p c ( 1 ) 和s a c 有些是互斥的，如p c ( n ) 和c i ， p c ( n ) 和平衡性有些是相互制约的，如代数次数和相关免疫等 每一条性质在一特定的应用环境中有其优势，甚至是必要条件因此研究不 1 0 2 布尔函数的基本概念及基本结论 同性质之问的关系，特别是当相互制约时，如何量化这种制约程度，如何折中是一 个非常重要而且复杂的问题，难度较大 湖北大学硕士学位论文 3对称布尔函数的密码学性质 这一章我们主要讨论对称布尔函数的性质，包括它的代数次数，非线性度，相 关免疫，扩散性质，线性结构以及它的代数免疫性质等【1 3 1 对称布尔函数的定义和表示方法 定义3 1 一个布尔函数称作是对称的，如果对于输入变量的任意置换，输出 值不变即对于一个诧变量对称布尔函数，有： f ( x l ，x 2 ，z n ) = y ( x 口( 1 ) ，x a ( 2 ，z 盯( 竹) ) 对于的任意置换仃都成立 由定义3 1 可知，对称布尔函数的函数值只与输入变量的权重有关也就是 说 w t ( z 1 ) = w t ( x 2 ) 兮厂( z 1 ) = ，( z 2 ) 凶此我们可以建立一个整函数 叩： o ，1 ，佗) 一f 2 使得v 童曰，( z ) = 即( 叫( z ) ) 考虑序列咋= ( 即( o ) ，叶( 1 ) ，即) ) ，每一个对称布尔函数唯一对应于一 个这样的n4 - 1 维向量，把这个向量叫做厂的简化值向量这就是对称布尔函数 的第一种表示方法 性质3 1 一个住元布尔函数是对称的，当且仅当它的代数正规型可以写成下 面的形式： 这里x m 指含有礼个变量的i 次基本对称多项式 由性质3 1 可知，对称布尔函数的代数正规型可以由一个n + 1 维向量 入( ，) = ( 入，( o ) ，入，( 1 ) ，a ，( n ) ) 来确定我们把这个向量叫做，的简化代数正规 1 2 x ，( n o 渤 j j 毗7 茁 礼芦。悔m 0 一( 。o 础 = 茁z ， 3 对称布尔函数的密码学性质 型向量 因此一个对称布尔函数既可以由它的简化值向量表示，同时也可以由它的简 化代数正规型向量表示 性质3 2 设f ，g 都是铭元对称布尔函数，则，+ g 也是对称的。 性质3 3 设，夕都是n 元对称布尔函数，则，夕也是对称的 性质3 。2 和3 3 说明佗元对称布尔函数的全体在鼠中，对于多项式的加法 作成一个环 3 2 对称布尔函数的代数次数 设s ( x ) 是一个礼变元对称布尔函数，它的简化值向量和简化代数正规型向 量分别为叩= ( 叶( o ) ，v f ( 1 ) ，即( n ) ) 和入( ，) = ( 入，( o ) ，入，( 1 ) ，x a - ) ) 由代 数次数的定义可知，对称布尔函数的代数次数可表示为： d e g ( f ) = m a x i l 入i ( i ) o ) 下面我们建立对称布尔函数的代数次数与它的简化值向量的关系 设a = ( a n k n 是一个无限二元序列，我们说a 是周期为t 的周期序列，如果 a n + t = a 。对于所有n n 都成立我们用( a o ，a l ，a t 一1 ) + ，a i 岛表示周期 为t 的无限周期序列u = ( u n ) n e n ，u n o ，1 ) ，其中 f t 正t2 【u t - t - i 0 i t 一1 vi n 定义3 2 一个佗维向量( 均，一1 ) 叫做一个无限序列的一部分，如果它 是由这个无限序列的前t , 项构成我们说这个礼维向量是周期为t 的周期向量， 如果它是无限周期序列( 峋，v t 1 ) + 的一部分 定理3 1 【1o 】设，3 是一个对称布尔函数，其简化值向量和简 化的代数正规型向量分别为咋= ( 吩( o ) ，即( 1 ) ，吩( 佗) ) 和入( ，) = ( a ，( o ) ，a ，( 1 ) ，入，( 凡) ) 那么( ，) 是周期为2 。( 2 。 n ) 的，当且仅当d e g ( f ) 2 2 1 并且( 峋，耽t _ 1 ) 是一个2 一1 个变量的对称布尔函数的简化值向量， ( a o ，入2 t 一1 ) 是它的简化代数正规型向量 1 3 湖北大学硕士学位论文 定理3 2 【1 0 】设，风是一个对称布尔函数，那么d e g ( f ) = ，当且仅当( ，) 是周期为岔+ 1 的周期序列，并且它是序列( 峋，忱t _ 1 ，的ol ，蚴一1o1 ) 的 一部分 由定理3 4 可知，对于一个n 变元d 次对称布尔函数，完全可以由它的简化 值向量的前2l o o g 。d j + 1 个字节和表示礼的iz 0 9 2 d j + 1 个字节来表示，这样就大大 降低了存储这个函数所用的空间 3 3 对称布尔函数的扩散性质和它的线性结构 这一节我们主要讨论对称布尔函数的扩散性质和它的线性结构，它们都是由 函数导数的性质决定的 性质3 4 【1 0 ) 设i 鼠是一个对称布尔函数，a ，b 毋，满足条件w t ( a ) = w t ( b ) ，那么d 。，和d 6 厂是线性等价的也就是说存在毋上的一个线性置换口， 使得眈，= d b f o 性质3 5 【1o 】设，b n 是一个对称布尔函数，k 是一个整数，l k n 一1 ，v = ( e 1 ，c n - k ) ，七= e n - k + 1 + + e n 那么，眈k 厂在所有仿射子空间 b + vb ( e n - k + l ，e 乱) 所确定的函数： g b ：v 一咒 x h 伍。，( z + b ) 是一个( 几一k ) 元对称布尔函数，并且它们的简化值向量和简化代数正规型向量 分别为： 。( i ) = 即( i + 训t ( 6 ) ) o 吩0 + k w t ( b ) ) a g b ( i ) =oa s ( i + 歹) oo 久巾+ 歹) j ! k w t ( b ) j ，- s ( - ) ) 如果z , ：f - 2 1 1 = 吩f n 2 1 + 1 ，几为偶数；或者 , sr n l 2 1 1 = u s n 2 1 + 1 ，u s f n 2 1 2 = , if - 1 2 ， 咒为奇数那么厂) 不能达到最大的代数免疫 定理3 1 2 i l l 设2 j n 2 升1 1 ，j 1 ，b n 是一个对称布尔函数 它的简化值向量为即= ( 叩( o ) ，( 1 ) ，吖( 几) ) ，对于所有0 t 2 j ，定义 集合k = z ：? 兰im o d 一，0 z + 砩即( 1 ) + + 簖一1 咋( 诧一1 ) + 四叩( 铊) = 2 n ( 4 1 ) 引理4 2 如果入= ( 入o ，入l ，k ) 是方程的一组解，那么 入+ 1 = ( a o + 1 ，入l + i ，入n + 1 ) 也是方程的一组解 证明由砩+ 嚷+ + 谨= 2 n 得： c 嚣( a o + 1 ) + c 尝( a 1 + 1 ) + + 铝( a 稚+ 1 ) = ( 砩+ 砩+ + 锘) + ( 四入o + 砩入l + + 嚷k ) ：2 “一2 礼一i = 2 n 一1 所以a + 1 = ( 入o + 1 ，入1 + 1 ，h + 1 ) 也是方程的一组解 由引理可知，如果吩= ( 卟( o ) ，咋( 1 ) ，吩( 冗) ) 是一个平衡对称布尔函数的 简化值向量，那么叩+ l = ( 即( o ) + l ，叶( 1 ) + 1 ，叶( 礼) + 1 ) 也是某个平衡对 称布尔函数的简化值向量以后我们把这两个对称布尔函数看成是同一个函数， 不加区别 引理4 3 当倪为奇数时，任意形如 8 = ( a o ，a l ，n ( 几+ 1 ) 2 ，o ( n + i ) 2o1 ，a lo1 ，a oo1 ) 的向量都是方程( 4 1 ) 的解 证明由于对于任意的0 i 讫有：锈= c ： 当扎为奇数时，n + 1 为偶数 q 知+ + c 驴一1 7 2 8 m 1 ) 2 + + c ：口0 = 1 2 ( 砩+ 嚷+ + 暖) = 2 “一i 1 8 4 平衡对称布尔函数 所以a = ( a o ，a l ，n ( n + 1 ) 2 ，o ( n + 1 ) 2o 1 ，a lo1 ，a oo1 ) 是方程的解 定义4 1 当n 为奇数时，简化值向量为 a = ( a o ，a l ，o ( 珐+ 1 ) 2 ，o b + 1 ) 2o l ，a lol ，a oo1 ) 的平衡对称布尔函数叫做平凡平衡对称布尔函数 因此平凡平衡对称布尔函数的计数为2 ( n + 1 ) 2 。我们通过计算机搜索发 现，在平衡函数中，平凡平衡对称布尔函数占据了相当大的比例对于奇数 7 t , ，( 7 1 , 1 2 8 ) ，除n 1 3 ，2 9 ，3 1 ，3 3 ，3 5 ，4 1 ，4 7 ，6 1 ，6 3 ，7 3 ，9 7 ，1 0 3 之外，所有的奇 变量平衡函数都是平凡平衡的 引理4 4 当n 为偶数时，方程有一组平凡解为：a = ( 1 ，0 ，1 ，0 ，0 ，1 ) 并且 以向量a 作为简化值向量的平衡布尔函数为一次函数 证明因为对于任意的偶数扎有： 所以 砩+ 暖十+ 四= 磷+ 碟+ + 四。 砩+ 锈+ + 铝 = 铷铝+ a l 砩+ + 铝 = 2 竹一1 并且我们很容易验证，以a = ( 1 ，0 ，1 ，0 ，0 ，1 ) 为简化值向量的函数是y ( x ) = x l + x 2 + + z n + 1 定义4 2 当n 为偶数时，代数次数大于1 的平衡对称布尔函数叫做非平凡平 衡对称布尔函数 4 。2 奇变元平衡对称布尔函数 引理4 5 9 1 设n 是奇数，是一个n 变元对称布尔函数如果，的简化值向量 y ，满足： 啪) - a + 1 i f i fi i 州 m 2 j 这里a f 2 定理4 2 1 9 1 设整数诧，2 。死 2 抖1 ，t 0 函数，是一个忍变元对称布尔函 数如果a i ( s ) = n 1 2 1 ，那么a s ( 2 。) ，入，( 2 。一1 ) 和a ，( 2 。+ 2 卜1 ) 中至少有一个为1 4 3 偶变元平衡对称布尔函数 对于任意偶数7 2 ，是否存在非平凡平衡的对称布尔函数我们还不能确定也 就是说对于任意偶数n ，方程( 4 1 ) 的解的情况不确定但对于某些特定的偶数 我们找到了一些非平凡平衡的对称布尔函数下面我们就来讨论这些平衡对称函 数的某些密码学性质 引理4 7 【1 0 】设厂是一个n 变元的对称布尔函数，它的简化值向量和简 化的代数正规型向量分别为： ( ，) = ( 叶( o ) ，吩( 1 ) ，叶( n ) ) 和入( ，) = ( 入，( o ) ，a s ( 1 ) ，入，( n ) ) 那么矿( ，) 和入( ，) 满足关系： 吁( i ) = o a s ( k ) ， 七兰t 入觯) = o - s ( a ) 。 a s i 对于任意的i 0 ，1 ，死) 都成立 定理4 3 当n = 6 k + 2 ，k z 时，至少存在四个非平凡平衡对称布尔函数设 这四个函数分别为 ，如，3 ， 那么他们的简化值向量( ) ，( ，2 ) ，( 厶) ，( ) 满足关系： 2 0 4甲衡对称布尔函数 ( 1 ) ( 2 k ) = ( 4 七+ 2 ) = 0 ，( 2 k + 1 ) = 1 其余i f l ( 2 i ) = 1 , v f , ( 2 i - 1 ) = 0 ， ( i k ，0 isn 2 ) ( 2 ) v f 2 ( 2 k ) = ( 4 知+ 2 ) = 0 ，( 4 七+ 1 ) = 1 其余v f 2 ( 2 i ) = 1 , v f 2 ( 2 i 一1 ) = 0 ， ( i k ，0 i 7 2 2 ) ( 3 ) ( z ) = ( i ) 4 - 1 ( 4 ) ( i ) = ( ) 4 - 1 证明通过验证可知： 再由 ( 1 ) ( 2 ) ( 3 ) ( 4 ) 3 k 4 - 1 i = o 3 七+ l i = o 3 岛+ 1 i - - - 0 3 奄+ l i = 0 3 七+ 1 = 2 q 2 七k + 2 = q 2 詹k + 2 - 4 - 锱 3 七+ 1 兹+ 2 = 6 。6 6 2 i + 1 = 2 加1 i = 0 瑶+ 。= 诺器一强2 一础蹴= 2 n - 1 ； 罐+ 2 = 诺瞄一锘2 k + 2 一嗽；= 2 n - t ； 。6 6 6 2 七i + + 1 2 = 锘2 忌k + 2 一碟搿一c 一6 6 2 詹k + + 2 l = 2 n - 1 ； 6 6 2 i + ：= 锘2 南k + 2 一c 擞薯一。6 6 6 4 七k + + 2 2 = 2 n - 1 ； 那么，由( 1 ) 式确定一个平衡对称布尔函数 ( z ) ，其简化值向量 满足关系： 其余 ( ) = ( ( o ) ，( 1 ) ，( 扎) ) v f ，( 2 k ) = v i a ( 4 k4 - 2 ) = 0 ，叶。( 2 k + 1 ) = 1 ( 2 i ) = 1 ，( 2 i 一1 ) = 0 ，( i k ，0si 佗2 ) 2 1 铷 湖北大学硕士学位论文 由( 2 ) 式确定个平衡对称布尔函数厶( z ) ，其简化值向量 满足关系： 其余 ( 丘) = ( ( o ) ，( 1 ) ，( n ) ) v r 2 ( 2 k ) = y 2 ( 4 k + 2 ) - = 0 ，v 2 ( 4 k + 1 ) = 1 u f 2 ( 2 i ) = 1 ，( 2 t 一1 ) = 0 ，( i k ，0 i n 2 ) 由( 3 ) 式得：v y a ( i ) = 叩。( i ) + 1 由( 4 ) 式得：( ) = v 1 2 ( i ) + 1 证明完毕 推论4 1 由定理4 3 得到的四个平衡对称布尔函数 ，厶， ，厶满足关系： 矗 ) = p + 1 ) ，3 ( z ) = ( z ) + l ， ( z ) = i ( x + 1 ) + 1 定理4 4 当n = 6 k + 2 = 2 。时，定理4 3 中确定的对称布尔函数五，的代数 次数为： d e g ( f i ) = 2 一1 = 6 k + 1 证明由 ( 妨的平衡性可知d e g ( f 1 ) 6 k + 2 ， 由引理4 7 得： , k i 。( 6 k + 1 ) = 入 ( 2 2 1 ) = o ( ) 三2 i 一1 = o ( i ) i ! ( 1 ，1 ) =1 冈此d e g ( h ) = 2 。一1 = 6 k + 1 ( i = l ，2 ，3 ，4 ) ，同时由推论4 。1 可知如， ， 的代 数次数与 相同 我们通过计算得出了n = 6 k + 2 ，机 1 2 8 ) 时，定理4 3 给出的平衡对称布 尔函数的代数次数如下： 一2 2 4 t - 衡对称布尔函数 n = 6 忍+ 2 8 2 0 3 2 4 4 5 6 6 8 8 0 9 2 1 0 4 1 1 6 d e g ( f ) 7 1 5 3 1 3 1 5 5 6 3 6 3 6 3 1 0 3 1 1 1 诧= 6 + 2 1 4 2 6 3 8 5 0 6 2 7 4 8 6 9 8 1 1 0 1 2 2 由上面的计算得到的结果，我们得出下面的猜想： 猜想4 1 设，( z ) 是一个n 元平衡对称布尔函数，礼= 6 k + 2 ，k 1 ，2 ，) ， 其简化值向量吩= ( 吩( o ) ，即( 1 ) ，即( 死) ) 满足： u l ( 2 k ) = v l ( 4 k + 2 ) = 0 ，v s ( 2 k + 1 ) = 1 其余 v l ( 2 i ) = 1 ，v i ( 2 i 一1 ) = 0 ( i k ，0 i n 2 ) 令n = m a x i i 2 k i 6 k + 2 ) ，另b 么：d e g ( f ) = n 或d e g ( f ) = n 一1 引理4 8 设t 毋，佗为偶数对于任意z 毋有： ( 1 ) 若w t ( t ) 为奇数，那么t x = t ( x + 1 ) + 1 ； ( 2 ) 若w t ( t ) 为偶数，那么t z = t ( z + 1 ) 证明由于 t zo t ( x + 1 ) = t ( xo zo 1 ) = t 1 = w t ( t ) ( r o o d 2 ) 所以( 1 ) w t ( t ) 为奇数，那么t z = t + 1 ) + 1 ； ( 2 ) w t ( t ) 为偶数，那么t x = t + 1 ) 2 3 砒：孔缸铝够螂坳 ( 七2 4 6 8均垅m均堪加 七1 3 5 7 9 u 培坫 均 湖北大学硕士学位论文 引理4 9 设f ( x ) b 。是定理4 3 中得到的平衡布尔函数，那么对于任意的 t 曰，t 1 , f ( z ) 在t 处的w a l s h 变换为： ( 1 ) w t ( o 为奇数 坼( t ) = 2 ( 一1 ) 妇= 2 p 2 k + l ( 叫芒( t ) ，n ) ( 2 ) w t ( t ) 为偶数 w t ( x ) = 2 k + 1 ( t ) = 4 ( 一1 ) 细一2( - - 1 ) 沁= 4 恳七( 加舌( 亡) ，礼) 一2 p 2 k + 1 ( 叫t ( t x 仃) w t ( z ) = 2 kw t ( x ) = 2 k + l 证明设向量( 1 ，0 ，1 ，0 ，0 ，1 ) 对应的对称布尔函数为，7 ( z ) ，那么它的代数 次数d e g ( f 7 ) = 1 而f ( x ) 与，7 ( z ) 满足关系： ，c z ，= = 0 ， 其余u y 2 ( i ) = 叶( i ) ，( 0 i 礼) ( 3 ) ( 佗一m ) = ( m 一2 ) = 0 ， 其余( i ) = v f ( i ) ，( 0 i 礼) u , ( m 1 ) = u l a ( n m + 1 ) = 1 ， ( m 一1 ) = ( 咒一m + 1 ) = 1 ， ( m 一1 ) = ( 佗一m + 1 ) = 1 ， ( 4 ) ( n m ) = ( n m + 2 ) = 0 ，( m 1 ) = ( 佗一m + 1 ) = 1 ， 其余( 力= 叶( z ) ，( 0 i 礼) ( 5 ) ( t ) = ( i ) + 1 ；( 0 i 竹) ( 6 ) 0 ) = ( i ) + 】；( 0 i 铊) ( 7 ) ( i ) = ( i ) + 1 ；( 0 i 佗) ( 8 ) ( i ) = u s , ( ) + 1 ；( 0 i 佗) 证明通过验证- q f 知： 四+ 四。2 = 2 四。1 2 角2 12 南2 1 再由c 2 n i = 碟件1 = 2 加1 得： i = o i = 0 2 k 2 - 1 碟+ 四。+ 谨一+ 1 一四一四= 2 ”1 i - - - - 0 上式确定了一个平衡对称布尔函数 ( z ) ，其简化值向量满足： 其余 ( m ) = 巧。( r n 一2 ) = 0 ，( m 一1 ) = ( 死一m + 1 ) = 1 ( i ) = 吩( i ) ，( 0 isn ) 。 2 6 4 平衡对称布尔函数 这就证明了结论( 1 ) ，i 司样的方法可以证明结论( 2 ) 一一( 8 ) 定理4 6 中的t r t = 2 k 2 2 也可以取奇数，证明方法与定理4 3 类似 我们可以通过采用定理4 3 中的方法，来讨论定理4 6 得到的平衡对称布尔 函数的性质，这里就省略了 2 7 湖北大学硕士学位论文 5对称布尔函数的应用 这一章我们主要是利用对称布尔函数，通过已知的构造函数的方法，来梅造 一些具有较好密码学性质的新函数 我们用符号( 0 0 1 1 ) + 表示无限序列：0 0 1 1 0 0 1 1 0 0 1 1 ，它是南0 0 1 1 无限循环 形成的如果一个礼维有限序列是某一无限循环序列的前佗项，我们就说这个序 列是循环的 下面我们分别就n 为偶数和扎为奇数两种情况，讨论对称布尔函数的最大非 线性度 引理5 1 【3 9 】设f ( x ) 是扎元对称布尔函数，礼为偶数，其简化值向量为 叶= ( 咋( o ) ，v s ( 1 ) ， ( n ) ) ，那么下面的结论是等价的： ( 1 ) f 是b e n t 函数； ( 2 ) 对于所有k = 0 ，1 ，扎一2 ，叶( 后十2 ) = 吩( 七) 4 - - l ； ( 3 ) 存在常数c ，d o ，1 ) ，使得对于任意x 有： m ) = o x i x jo ( o c x i ) o d t j i 引理5 1 说明了，存在对称的b e n t 布尔函数，并且这类函数都是二次的它们 的简化值向量必是( 0 0 1 1 ) + ，( 0 1 1 0 ) + ，( 1 1 0 0 ) + 或( 1 0 0 1 ) + 中的一种情况因此，对于 任意偶数n ，只存在四个对称b e n t 函数 引理5 2 4 q 设f ( x ) 是佗元对称布尔函数，祀为奇数，j j l j z , ： n f 2 n 一一2 ( n 一1 ) 2 引理5 3 【4 i 】设r l 3 ，7 2 是奇数，是一个钆变量对称布尔函数，其简化值向 量为叩= ( 即( o ) ，u f ( 1 ) ，咋) ) ，下面的结论是等价的： ( 1 ) f 的非线性度等于2 妒1 2 ( n - 1 ) t 2 ： ( 2 ) ( ，) 是( 0 0 1 1 ) + 的一个长度为咒+ 1 的子序列； ( 3 ) ，的w a l s h 谱为三值的，并且取值0 ，- t - 2 ( 1 ) 2 ； ( 4 ) ，是一个二次函数 2 r 5对称布尔函数的应用 引理5 2 和5 3 说明，奇变元对称布尔函数可达到的最大非线性度为2 仆1 2 住- 1 ) 2 ，这类函数都是二次的，并且是三值谱函数 定义5 1 设，1 ，厶是两个n 元布尔函数，那么它们的n + 1 元级联函数 歹( + 1 ，z 嚣，z 1 ) 定义为： ，