（概率论与数理统计专业论文）多输出布尔函数的密码学性质.pdf

摘要 布尔函数可以应用于一些密码体制和密码协议的构造它们的安全性能与所选用的 布尔函数有着密切的关系从目前的文献来看，对布尔函数的研究多局限于单输出布尔 函数，已取得了许多重要成果，但对多输出布尔函数的讨论似乎并不多 本文主要讨论多输出布尔函数的密码学性质，取得了一些研究成果，主要包括以下 几个方面 相关免疫函数在密码学中起着重要的作用本文定义了一类新的多输出相关免疫函 数，称之为第1 1 类多输出相关免疫函数，它是单输出相关免疫函数的一种新的推广形式， 可以抵抗对其分量函数的任意非零线性组合进行的相关分析攻击夺文还给出了一种从 已有的第1 i 类多输出相关免疫函数构造新的第1 i 类多输出相关免疫函数的方法，并且给 出了所构造的第1 i 类多输出相关免疫函数的非线性度的一个下界利用这种方法可以从 简单的多输出相关免疫函数构造出复杂的具有较高非线性度的多输出桓关免疫函数 对于平衡的相关免疫函数的构造和计数问题，本文也进行了研究漕先给出了一种 简单并且直观的平衡的相关免疫函数的构造方法，然后在此基础上给出了乎衡的相关免 疫函数的一个计数下界，改进了目前已有的结果，并且进一步绘出了平衡的相关免疫函 数的一个计数上界、 r e s i l i e n t 函数首先在文献【2 】2 和【9 】中引入：，本文讨论了r e s i l i e n t 函数与多输出相关免 疫函数之间的关系，证明了r e s i l i e n t 函数就是完偏的多输出相关免疫函数菠次，本文推 广了文献【7 6 】中构造r e s i l i e n t 函数的两种方法，得到了两个一般性的结论，在此基础上给 出了一种构造平衡的相关免疫函数的简单力法另外，4 义还讨论了r e s i l i e n t 函数的一 系列性质，给出了一个多输出布尔函数f ( z ) 是( n ，m ，t ) - r e s i l i e n t 函数的两个充分必要条 件，在此基础上得到了r e s i l i e n t 函数的一种理论上的枚举构造方法? ， 本文研究了多输出布尔函数的线性结构，指出了文献( 7 5 中的错误，给出了线性结 构和线性结构函数的若干重要性质，讨论了线性结构与非线性度以及函数的无偏性之间 的关系溺外，本文还引进了一种广义自相关函数，它和线性结构之间的关系也进行了 讨论， 复合多输出布尔函数是一种特殊的多输出布尔函数，而退化的多输出布尔函数又是 复合多输出布尔函数的一种特殊情况j 本文给出了复合多输出布尔函数和退化的多输出 布尔函数的一些密码学性质，指出了它们的密码学价值 f 文献f 3 7 】中引入的多输出布尔函数的非线性度是衡量密码体制安全性的一个重要指 标本文定义了一种与之不同的多输出布尔函数的第二类非线性度，讨论了两者之间的 关系，指出了它们的密码学意义，并且进一步讨论了两类多输出布尔函数的第二类非线 性度 z i g z a g 函数首先在文献【5 】中引入，它可以应用于健忘传输的构造本文给出了两种 从已有的z i g z a g 函数构造新的z i g z a g 函数的方法利用这两种方法，可以将线性的z i g z a g 函数变换为非线性的z i g z a g 函数，从简单的z i g z a g 函数构造出复杂的z i g z a g 函数 最后，本文以两种不同的方式对文献【2 0 中的二元序列的导数进行了推凡，定义了 两类不同的二元序列的广义导数，讨论了周期为2 ”和2 ”一1 的二元序列的广受导数的 性质，推广了文献 2 0 1 中给出的结果。： a b s t r a c t b o o l e a nf u n c t i o n sc a nb eu s e dt oc o n s t r u c ts o m ec r y p t o s y s t e m sa n dc r y p t o g r a p h i ep r o t o c o l s t h e i rs e c u r i t i e sh a v ec l o s er e l a t i o nt ot h ec h o s e nb o o l e a nf u a c t i o n s f r o mt h ec u r r e n tr e f e r e n c e s ， i ti sf o u n dt h a tr e s e a r c h e s0 1 3 b o o l e a nf u n c t i o n sa r em a i n l yc o n f i n e di ns i n g l e - o u t p u to d e sa n d h a v ea c h i e v e dm a n yi m p o r t a n tr e s u l t s h o w e v e r ，t h e r es e e r d 一9t ob en o tm u c hd i s c u s s i o n0 n m u l t i o u t p u tb o o l e a nf u n c t i o n s t h i sd i s s e r t a t i o nm a i n l yd i s c u s s e st h ec r y p t o g r a p h i cp r o p e r t i e so fm u l t i - o u t p u tb o o l e a n f u n c t i o n st h em a i nr e s u l t sa r ea sf o u o w s c o r r e l a t i o ni m m u n ef l m c t i o n sp 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 y t h i sd i s s e r t a t i o n d e f i n e san e wc l a s so fm u l t i - o u t p u tc o r r e l a t i o ni m m u n ef u n c t i o n s c a l l e dt h ec l a s si im u l t i - o u t p u t c o r r e l a t i o ni m m u n ef u n c t i o n s ，w h i c hc a nr e s i s tt h ec o r r e l a t i o na t t a c ko ne v e r yn o n z e r ol i n e a r c o m b i n a t i o no ft h e i rc o m p o n e n tf u n c t i o n s f u r t h e r m o r e am e t h o df u rc o n s t r u c t i n gn e wc l a s s i im u l t i - o u t p u tc o r r e l a t i o ni m m u n ef u n c t i o n sf r o mo l do n e si s p r e s e n t e d t h en o n l i n e a r i t yo f t h en e wc o n s t r u c t e dc l a s si im u l t i o u t p u tc o r r e l a t i o ni m m u n ef u n c t i o n si sa l s od i s c u s s e d t h i s m e t h o dc a ns y n t h e s i z el a r g em u l t i - o u t p u tc o r r e l a t i o nh - n n l u n ef u n c t i o n sw i t hh i g hn o n l i n e a r i t y f r o ms i n a i lo n e s t h i sd i s s e r t a t i o na l s or e s e a r c h e st h ec o n s t r u c t i o na n de n u m e r a t i o np r o b l e mo fb a l a n c e d c o r r e l a t i o ni m m u n ef u n c t i o n s w ef i r s t g i v eas i m p l ea n di n t u i t i v em e t h o df o rc o n s t r u c t i n g b a l a n c e dc o r r e l a t i o ni m m u n ef u n e t i o n sa n dt h e ns h o wal o w e rb o u n df o rt h en u m b e ro fb a l a n c e d c o r r e l a t i o ni m m u n ef u n c t i o n s ，w h i c hi m p r o v e st h ep r e v i o u s l yk n o w nb o u n d s a l s o ，w es h o wa n u p p e rb o u n df u rt h en u m b e ro fb a l a n c e dc o r r e l a t i o ni m m u n ef u n c t i o n s t h ec o n c e p to far e s i l i e n tf u n c t i o nw & 8f i r s ti n t r o d u c e di n 【2 a n d 【9 】w ed i s c u s st h e r e l a t i o n s h i pb e t w e e nr e s i l i e n tf u n c t i o n sa n dm u l t i o u t p u tc o r r e l a t i o ni l l n u n ef u n c t i o n s w es h o w t h a tar e s i l i e n tf u a c t i o ni sc o i n c i d e n tw i t ha nu n b i a s e dm u l t i - o u t p u tc o r r e l a t i o ni m m u n ef u n c t i o n w ea l s og e n e r a l i z et w om e t h o d sf u rc o n s t r u c t i n gr e s i l i e n tf u n c t i o n si n 7 6 】a n do b t a i nt w ol n o r e g e n e r a lr e s u l t s ，b yw h i c has i m p l em e t h o df o rc o n s t r u c t i n gb a l a n c e dc o r r e l a t i o ni m m u n ef u n c t i o n s i so b t m n e d i na d d i t i o n ，w es h o ws o m ep r o p e r t i e so fr e s i l i e n tf u n c t i o n sa n dg i v et w on e c e s s a r y a n ds u f f i c i e n tc o n d i t i o n so fw h a ta l lm u l t i - o u t p u tb o o l e a nf u n c t i o nf ( ) i sa n ( n ，m ，t ) 一r e s i l i e n t f u n c t i o na sar e s u l t ，at h e o r e t i c a l l ye n u m e r a t i v ea l g o r i t h mo fr e s i l i e n tf u n c t i o n si s p r o p o s e d i nt h i sd i s s e r t a t i o n ，t h eu n e a rs t r u c t u r e so fm u l t i - o u t p u tb o o l e & nf u n c t i o n sa r es t u d i e d w ep o i n to u tt h em i s t a k e si n 【7 5 】a n dg i v es o m ei m p o r t a n tp r o p e r t i e so fl i n e a rs t r u c t u r e sa n d l i n e a rs t r u c t u r e df u n c t i o n s f u r t h e r m o r e ，w ed i s c u s st h er e l a t i o n s h i pb e t w e e nl i n e a rs t r u c t u r ea n d n o n h n e a r i t y t h er e l a t i o n s h i pb e t w e e n 】i n e a rs t r u c t u r e sa n du n b i a s e df u n c t i o n sj sa i s od i s c u s s e d ag e n e r a l i z e da u t o c o r r e l a t i o nf u n c t i o ni sd e f i n e d w ea l s os h o war e s u l to nt h e r e l a t i o n s h i p b e t w e e nl i n e a rs t r u c t u r ea n dt h eg e n e r a l i z e da u t o c o r r e l a t i o nf u n e t i o n c o m p o s i t em u l t i - o u t p u tb o o l e a nf u n c t i o n sa r es p e c i a lm u l t i - o u t p u tb o o l e a nf u n c t i o n s ，w h i l e a l g e b r a i cd e g e n e r a t em u l t i - o u t p u tb o o l e a nf u n c t i o n sa r eas p e c i a le a s eo fc o m p o s i t eo n e s t h i s d i s s e r t a t i o ns h o w e ss o m ec r y p t o g r a p h i cp r o p e r t i e so f c o m p o s i t ea n da l g e b r a i cd e g e n e r a t em u l t i o u t p u tb o o l e a nf u n c t i o n sa n de x p l a i n st h e i rc r y p t o g r a p h i cv a l u e s a b t r a c 0 t h en o n l i n e a r i t yo fam u l t i o u t p u tb o o l e a nf u n c t i o n ，w h i c hw a sf i r s t i n t r o d u c e di n 【3 7 】 i sa ni m p o r t a n ti n d e xf o rm e a s u r i n gt h es e c u r i t yo fc r y p t o s y s t e m s t h i sd i s s e r t a t i o nd e f i n e sa n e wk i n do fn o n l i n e a r i t yf o rm u l t i o u t p u tb o o l e a nf u n c t i o n sw h i c hi sd i f i e r e n tf r o mt h a ti nj 3 7 t h er e l a t i o n s h i pb e t w e e nt h et w od i f f e r e n tk h l d so fn o n l i n e a r i t i e shs t u d i e d t h e hc r y m o g r a p i f i c s i g n i f i c a n c ei sp o i n t e do u t f u r t h e r m o r e ，t h en e wn o n l i n e a r i t i e so ft w oc l a s s e so fm u l t i o u t p u t b o o l e a nf h n c t i o n sa r ea l s od i s c u s s e d z i g z a gf u n c t i o n sw e r ed e f i n e di n 【5 1i nc o n n e c t i o nw i t ha l la p p l i c a t i o nt ot h ec o n s t r u c t i o no f o b l i v i o u st r a n s f e r s t h i sd i s s e r t a t i o np r e s e n t st w om e t h o d sf o rc o n s t r u c t i n gn e wz i g z a gf u n c t i o n s f r o mo l do n e s b yu s i n gt h e s em e t h o d s ，w ec a d t u r nl i n e a rz i g z a gf u n c t i o n si n t on o n l i n e a ro n e s a n dc o n s t r u c tl a r g ez i g z a gf u n c t i o n sf r o ms m a l lo n e s f i n a f iy ，t h i sd i s s e r t a t i o ne x t e n d st h ed e r i v a t i v e so fb i n a r ys e q u e n c e sd e f i n e di n 【2 0 】i nt w o d i f f e r e n tw a y sa n dd e f i n e st w od i f f e r e n tg e n e r a l i z e dd e r i v a t i v e so f b i n a r ys e q u e n c e s f u r t h e r m o r e ， t h ep r o p e r t i e so fg e n e r a h z e dd e r i v a t i v e so fb i n a r ys e q u e n c e sw i t h p e r i o d s2 ”a n d2 “1a r c d i s c u s s e d t h er e s u l t si n 2 0 】a r ee x t e n d e d 致谢 首先，我要感谢我的导师沈世镒教授是他为我提供了一个继续深造的机会，带领 我进入了密码学的研究领域在他的关心和指导下，我得以顺利完成博士学位论文 其次，我要感谢符方伟教授在这几年来的研究工作中，他始终给予我具体的帮助 和指导他的严谨细致的治学作风，使我受益匪浅 另外，我还要对李明瑶同学在程序的编制和调试方面所提供的帮助表示感谢 最后，我还要感谢各位给予我关心、帮助和支持的老师和同学 第一章引言 随着计算机科学的蓬勃发展，我们这个社会已开始进入信息时代电子计算机和通 讯网络的广泛应用，一方面为人们的生活和工作提供了很大的方便，另一方面也提出了， 许多亟待解决的问题，其中信息的安全性就是一个突出的问题因此，密码学理论和技 术已成为信息科学和技术中的一个重要研究领域随着计算机网络的迅速发展，近代密 码学的应用已不仅仅局限于政治和军事以及外交等领域，其商用价值和社会价值也已得 到了充分的肯定 密码学是一门既古老又年轻的学科，其历史可以追溯到几千年以前，但在1 9 4 9 年之 前，密码技术基本上可以说是一门技巧性很强的艺术，而不是- - f 7 科学在这一时期， 密码专家常常是凭借真觉和信念来进行密码设计和分析，而不是推理证明在1 9 4 9 年， c e s h a n n o n 发表了“c o m m u n i c a t i o nt h e o r yo fs e c r e c ys y s t e m 1 4 s l 一文，为密码学奠定 了坚实的理论基础，使密码学成为一门真正的科学但从1 9 4 9 年至1 9 7 5 年，密码学的 理论研究工作进展不大1 9 7 6 年，w d i f f i e 和m e h e l l m a n 发表7 “n e wd i r e c t i o n si n c r y p t o g r a p h y ” ”】一文，提出了一种崭新的密码体制，导致了密码学上的一场革命他们 首次证明了从发送端到接收端无密钥传输的保密通信是可能的，从而开创了公钥密码学 的新纪元1 9 7 7 年，美国国家标准局( n a t i o n a lb u r e a uo fs t a n d a r d s ) 正式公布实施数据 加密标准d e s ( d a t ae n c r y p t i o ns t a n d a r d ) ，将d e s 算法公开，从而揭开了密码学的神秘面 纱从此，密码学的研究进入了一个崭新的时代 流密码和分组密码是密码学中数据加密的两种重要方式 对于流密码，最常用的密钥流生成器是非线性滤波生成器和非线性组合生成器它 们的安全性能与所选用的滤波函数和组合函数有着非常密切的关系实际上，滤波函数 和组合函数都是布尔函数因此，要讨论非线性滤波生成器和非线性组合生成器的安全 性能，必须首先深入研究作为滤波函数和组合函数的布尔函数的密码学性质近年来，对 布尔函数的密码学性质的研究多局限于单输出布尔函数，已取得了许多重要研究成果 但对多输出布尔函数的讨论似乎并不多如果在非线性滤波生成器和非线性组合生成器 中选用多输出布尔函数作为滤波函数和组合函数，则可以加快密钥流的生成速度因此， 对多输出布尔函数的密码学性质进行深入的研究具有重要的理论和应用价值 分组密码的一个典型例子是d e s 体制，其安全性能主要取决于s 盒的密码学性质的 好坏d e s 体制中的s 盒实际上就是一个多输出布尔函数另外，在分组密码中用到的 各种置换实际上也是一种特殊的多输出布尔函数因此，要想设计一个具有较高安全性 能的分组密码体制，必须首先选取一些具有良好密码学性质的多输出布尔函数 本文主要讨论多输出布尔函数的密码学性质，取得了一些研究成果全文共分九章， 主要内容安排如下 第二章定义了一类新的多输出相关免疫函数，称之为第1 i 类多输出相关免疫函数， 它是单输出相关免疫函数的一种新的推广形式，可以抵抗对其分量函数的任意非零线性 组合进行的相关分析攻击第二章还给出了一种从已有的第1 i 类多输出相关免疫函数构 造新的第1 i 类多输出相关免疫函数的方法，并且给出了所构造的第1 i 类多输出相关免疫 函数的非线性度的一个下界利用这种方法可以从简单的多输出相关免疫函数构造出复 杂的具有较高非线性度的多输出相关免疫函数 第一章引言 第三章对平衡的相关免疫函数的构造和计数问题进行了研究首先给出了一种简单 并且直观的平衡的相关免疫函数的构造方法，然后在此基础上给出了平衡的相关免疫函 数的一个计数下界，改进了目前已有的结果，并且进一步给出了平衡的相关免疫函数的 一个计数上界 第四章讨论了r e s i l i e n t 函数与多输出相关免疫函数之间的关系，证明了r e s i l i e n t 函数 就是无偏的多输出相关免疫函数其次，第四章推广了文献【7 6 】中构造r e s i l i e n t 函数的两 种方法，得到了两个一般性的结论，在此基础上给出了一种构造平衡的相关免疫函数的 简单方法另外，第四章还讨论了r e s i l i e n t 函数的一系列性质，给出了一个多输出布尔函 数f ( z ) 是，n ，t ) r e s i l i e n t 函数的两个充分必要条件，在此基础上得到了r e s i l i e n t 函数的 一种理论上的枚举构造方法 第五章研究了多输出布尔函数的线性结构，指出了文献【7 5 】中的错误，给出了线性 结构和线性结构函数的若干重要性质，讨论了线性结构与非线性度以及函数的无偏性之 间的关系另外，第五章还引进了一种广义自相关函数，它和线性结构之间的关系也进 行了讨论 复合多输出布尔函数是一种特殊的多输出布尔函数，而退化的多输出布尔函数又是 复合多输出布尔函数的一种特殊情况第六章给出了复合多输出布尔函数和退化的多输 出布尔函数的一些密码学性质，指出了它们的密码学价值 文献( 3 7 】中引入的多输出布尔函数的非线性度是衡量密码体制安全性的个重要指 标第七章定义了一种与之不同的多输出布尔函数的第= 类非线性度，讨论了两者之间 的关系，指出了它们的密码学意义，并且进一步讨论了两类多输出布尔函数的第二类非 线性度 z i g z a g 函数首先在文献 5 中引入，它可以应用于健忘传输的构造第八章给出了 两种从已有的z i g z a g 函数构造新的z i g z a g 函数的方法利用这两种方法，可以将线性的 z i g z a g 函数变换为非线性的z i g z a g 函数，从简单的z i g z a g 函数构造出复杂的z i g z a g 函数 最后，本文在第九章中以两种不同的方式对文献 2 0 1 中的二元序列的导数进行了推 广，定义了两类不同的二元序列的广义导数，讨论了周期为2 ”和2 ”一i 的二元序列的 广义导数的性质，推广了文献【2 0 中给出的结果 下面介绍几个在本文中经常用到的基本概念和记号 设碥= g f ( 2 ) “是二元域g f ( 2 ) 上的n 维向量空间显然，k 中的向量( z l ，) 与整数i = ：，k 2 n 4 是一一对应的，os is2 ”一1 因此，以后我们常将k 中对应 于整数 的向量记为郎 多输出布尔函数就是从k 到的函数对任意的从k 到的函数f ，f 可以表 示为f = l ，2 ，厶) ，其中每个分量函数 都是碥上的函数，即 是从k 到g f ( 2 ) 的函数，1 兰is m 我们用hk 表示码长为n 的维线性码，它是k 的一个t 维子空间，! n 一个 【n ，q 线性码c 的生成矩阵m 是g f ( 2 ) 上的一个k t t 阶矩阵，并且r a n k ( m ) = ，其行 向量是c 的一组基h i ，司表示极小距离为d 的，叫线性码 第二章多输出布尔函数的相关免疫性 布尔函数的相关免疫性首先在文献 5 3 】中被引进，它是衡量序列密码体制安全性的 一个重要指标如果所选用的布尔函数不具有一定的相关免疫性，则相应的密码体制易 受到相关分析法的攻击近年来，对单输出布尔函数的相关免疫性已进行了比较深入的 研究，取得了许多重要成果但对多输出布尔函数的相关免疫性，目前比较深入的研究 结果尚不多见对于具有一定相关免疫性的布尔函数我们称之为相关免疫函数文献【2 3 和【1 4 引入了多输出相关免疫函数的概念( 本文称之为第1 类多输出相关免疫函数) ，并 且简略地分析研究了其密码学性质文献 2 5 l 对多输出布尔函数提出了一种相关分析方 法 本章讨论多输出布尔函数的相关免疫性，给出了多输出相关免疫函数的一种新的定 义，称之为第1 i 类多输出相关免疫函数，它同样是单输出相关免疫函数的一种推广形式， 它可以抵抗对其分量函数的线性组合进行的相关分析攻击本章首先证明了第1 类多输 出相关免疫函数是第1 i 类多输出相关免疫函数的子类进一步，本章给出了一种从已有 的第1 i 类多输出相关免疫函数构造新的第1 i 类多输出相关免疫函数的方法 2 1 多输出相关免疫函数 定义2 1 设，是k 上的函数x 1 ，x 2 ，蜀是二元域g f ( 2 ) 上的n 个独立同分 布的随机变量，它们都服从均匀分布如果对任意满足l t l = t 的t = j - ，j 2 ，矗) 互 1 ，2 ，。) ，随机变量z = ，( 噩，x 2 ，) 与( 而。，而，玛。) 相互独立，即对任意 ( a l ，0 2 ，毗) k 和任意c g f ( 2 ) ， p r ( z = c l x j 。= 1 i t ) = p r ( g = c ) ， 则称，是( n ，1 ，t ) 相关免疫函数，或称，是k 上的t 阶相关免疫函数 由定义2 1 ，容易证明下述结论成立 引理2 1 如果，是( n ，1 ，t ) 相关免疫函数，则对任意1ss t ，也是( n 1 ，s ) 相关 免疫函数 下面是文献 2 3 和 1 4 ( p p 1 6 9 1 7 3 ) 中引入的第1 类多输出相关免疫函数的概念 定义2 2 设f 是从k 到的函数x l ，x 2 ，盖。是二元域g f ( 2 ) 上的n 个服 从均匀分布并且相互独立的随机变量如果对任意满足l t l = t 的t = j 1 j 2 ， ) 1 ，2 ，；) ，随机变量z = f ( x i ，x 2 ，。k ) 与( 乃，而，乃。) 相互独立，即对任意 ( “1 ，“2 ，a t ) k 和任意c6 ( g f ( 2 旷t 7 h 77h l p r ( z = c l x j = m ，1 i t ) = p r ( z = c ) ， 则称f 是( n ，m ，t ) 第1 类多输出相关免疫函数 现在我们引入第1 i 类多输出相关免疫函数的定义 定义2 3 设f = ( ，2 ，m ) 是从k 到的函数如果f 的分量函数的每一个 非零线性组合，( z ) = o 銎。c 。 ( z ) 都是( m1 ，t ) 相关免疫函数，则称f 是( n ，m ，t ) 第1 i 类 多输出相关免疫函数，其中z k ，c l ，c 2 ，c 。g f ( 2 ) 并且不全为o 第二章多输出布尔函数的相关免疫性 4 显然，多输出布尔函数的第1 i 类相关免疫性也是单输出布尔函数的相关免疫性的一 种推广第1 i 类多输出相关免疫函数可以抵抗对其分量函数的线性组合进行的相关分析 攻击 由定义2 3 知，下述结论是显然的 引理2 2 如果f = ( ，1 ，2 ，m ) 是( n ，m ，t ) 第n 类多输出相关免疫函数，则对任 意 i 1 ，i 2 ，靠) g 1 ，2 ，m ) ，g = ( ，t ， ：，允) 是( n ，i ，) 第1 i 类多输出相关免疫函 数 根据定义2 3 和引理21 ，可以立即得到以下结论 引理2 3 如果f 是( n ，m ，t ) 第1 i 类多输出相关免疫函数，则对任意l 8 t ，f 也 是( n ，m ，s ) 第1 i 类多输出相关免疫函数 2 2 两类多输出相关免疫函数之间的关系 定理2 1 如果f = ( ，f 2 ，m ) 是( n ，m ，t ) 第1 类多输出相关免疫函数，则f 也 一定是( n ，m ，t ) 第1 i 类多输出相关免疫函数 证明；设x - ，x 2 ，矗是二元域g f ( 2 ) 上的n 个服从均匀分布并且相互独立的随机 变量，z i = ，l ( x l ，x 2 ，x 。) ，注1 ，2 ，m 设z = f ( x 1 ，x 2 ，x 。) = ( z l ，易，z 。) 对任意c 1 ，c 2 ，c 。g f ( 2 ) 并且不全为0 ，c g f ( 2 ) ，设 m & ( c - ，c 2 ，c m ) = pj 卢= ( 6 - ，b 。，h ) ，日c 。以= c ) = l 因为f 是( n ，m ，t ) 第1 类多输出相关免疫函数，所以对任意 九，j 。，引 1 ，2 ，n ) 牙= ( z - ，z 2 ，) 与( 玛，蜀，置。) 相互独立于是，对任意( d - ，n z 棚t ) w ， p r ( oc 磊= c i 乃= 。，1 i t ) t = l = p r ( z = 卢f 乃= a ，1 s i t ) 芦s c ( o ，0 2 ，c m ) = p r ( z = 卢) 芦e j c ( n ，c ，c 。j = p r ( 0 c i z i = c ) 因此，根据定义2l ，f 的分量函数的每一个非零线性组合都是( n ，1 ，t ) 相关免疫函数再 由定义2 3 知f 是( n ，m ，) 第1 i 类多输出相关免疫函数 口 下述引理是文献【2 3 】中的线性组合引理的一种特殊情形 引理2 4 【23 设z 1 ，玩，名k 是二元域g f ( 2 ) 上的相互独立的离散随机变量，x 是 “上的离散随机变量则舅与( z l ，邑，z 。) 相互独立甘x 与z 1 ，易，z 。的每 一个非零线性组合。墨1c i 磊相互独立，其中c 1 ，c 2 ，c 。g f ( 2 ) 并且不全为0 定理2 2 设f = ( ，l ，f 2 ，m ) 是从k 到的函数设x 1 ，x 2 x 。是二元 域g f ( 2 ) 上的n 个服从均匀分布并且相互独立的随机变量，z i = ( x l ，x 2 ，x 。) ， 第二章多输出布尔函数的相关免疫性 5 i ：1 ，2 ，m 如果z 1 ，z 2 ，相互独立，则f 是( n ，m ，t ) 第1 i 类多输出相关免疫函 数骨f 是( n ，m ，t ) 第1 类多输出相关免疫函数 证明；因为z 。，z 2 ，z 。相互独立，所以根据引理2 4 和定义2 1 2 3 知，f 是( n ，m ，t ) 第1 类多输出相关免疫函数骨对任意 j 。，：， ) 1 ，2 ，n ) ，随机变量 z = f ( x x ，x 2 ，x 。) = ( z 1 ，z 2 ，) 与( 玛。，玛：，玛。) 相互独立错对任意协，j 2 ，九) 1 ，2 ，n ) ，z z ，z z ，的 每一个非零线性组合 mm o c 。蜀= o c j d x - ，x 2 ，x 。) i = 1i = 1 与( 而，玛，乃。) 相互独立# 争f 的分量函数的每一个非零线性组合0 墨。c 。，i ( z ) 都 是( n ，1 ，t ) 相关免疫函数( 其中z 碥) 车辛f = ( ，2 ，m ) 是( n ，m ，t ) 第1 i 类多输出 相关免疫函数 口 文献【1 4 ( p p 1 6 9 1 7 3 ) 指出定理2 1 的逆命题不成立，并且给出了一个反例经过仔 细验证，我们发现文献【14 中的反例实际上支持定理2 1 的逆命题我们猜测定理2 1 的 逆命题是成立的，也就是说，第1 i 类多输出相关免疫函数和第1 类多输出相关免疫函数 是等价的 质 2 3 无偏函数 为了讨论第1 i 类多输出相关免疫函数的构造，下面给出无偏函数的定义及其个性 定义2 4 设n m 1 ，f 是从k 到的函数如果对任意卢 l z 碥lf b ) = 卢) i = 2 ”一”， 则称f 是无偏函数对于k 上的无偏函数，称之为平衡函数 下面的引理可以在文献 7 6 中找到 引理2 5 7 6 】设f = ( ，2 ，m ) 是从k 到的函数，n m ，则f 是无偏函数 # 亭f 的分量函数 ，2 ，m 的每一个非零线性组合，( z ) = 三。c ( 。) 都是k 上的 平衡函数，其中z k ，c l ，c 2 ，c 。g f ( 2 ) 并且不全为0 2 4第1 i 类多输出相关免疫函数的构造 下面的引理是文献 7 4 】( p p ，6 0 0 6 0 4 ) 中的一个结果， 引理2 8c 7 q 设f l ( y 1 ) 是( n l ，1 ，t 1 ) 相关免疫函数，2 ( y 2 ) 是( n 2 ，l ，t 2 ) 相关免疫函数 其中t l t 2 ，y 1 k 。，y 2 k ，设 f ( y l ，y 2 ) = ( y 1 ) of 2 ( 2 ) ( 1 ) 如果 ( 1 ) 和，2 ( 9 2 ) 都不是平衡函数，则，( g l ，蚰) 是( n l + n 2 ，1 ，t 1 ) 相关免疫函数 第二章多输出布尔函数的相关免疫性 6 ( 2 ) 如果 ( y 1 ) 不是平衡函数，f 2 ( y 2 ) 是平衡函数，则f ( y x ，2 ) 是( n l + n 2 ，l ，t 2 ) 相关免 疫函数 ( 3 ) 如果 ( y 1 ) 是平衡函数，2 ( 9 2 ) 不是平衡函数，则f ( m ，y 2 ) 是( n 1 + * t t 2 ，1 ，t 1 ) 相关免 疫函数 ( 4 1 如果，l ( 玑) 和h ( u 2 ) 都是平衡函数，则( y l ，y 2 ) 是( n l + n ? ，1 ，t x + t 2 + 1 ) 相关免疫函 数 为了将上述引理推广到多个相关免疫函数的加和的情形，我们先引进一个相关免疫 函数的阶函数妒 设z = 0 ，l ，2 ，3 是所有非负整数的集合妒是一个从u 墨。( ( o ，l “z ”) 到z 的函数妒由以下递推关系定义 ( 1 ) 对任意n 2 ，( b l ，b 2 ，b 。) 0 ，1 ) ”和( tx ，t 2 ，t 。) z “， 币( ( 6 1 ，b 2 ，b ) ，( tx ，t 2 ，z 。) ) = 妒( ( b 。，b j 。) ，( t 1 。，t j ，t j 。) ) 其中 j - ，j 2 ，j 。) 是满足t j 。t ，5 s t j 。的 1 ，2 ，n ) 的一个排列 ( 2 ) 对任意n 2 ，( 6 l ，b 2 ，6 。) o ，1 ) ”和( t 1 ，t 2 ，“) z “，如果t 1 t 2 t 。，则 当( b z ，6 【号) 和( 6 l 扑“，6 。) 都是零向量时， 当( b 1 当( b l 当( b 。 妒( ( 6 l ，b 2 ，6 n ) ，( t l ，t 2 ，t n ) ) = 妒( ( 6 1 ，b t j ) ，( t x ，o 【 j ) ) ，6 ) 是零向量，( h j + - ，6 n ) 不是零向量时， 妒( ( b 1 ，b 2 ，b n ) ，( t 1 ，t 2 ，t n ) ) = 妒( ( b l 引+ ”，b ”) ，( 【制十，t n ) ) ，6 吲) 不是零向量，( 6 汹+ l ，6 n ) 是零向量时， 妒( ( 6 1 ，b 2 ，b n ) ，( t l ，t 2 - ，z n ) ) = 妒( ( 6 ，b i l l ) ，( t 1 ，【jj ) ) ，b t j ) 和( b t g + 1 ，b 。) 都不是零向量时， 妒( ( 6 l ，b z ，b 。) ，( 1 ，t 2 ，。t ) ) = 咖( ( 6 l ，6 【号j ) ，( t 1 ，o 【制) ) + 妒( ( 6 【号j + 1 - - ，6 n ) ，( o l 号j + 1 ，t n ) ) + 1 这里【j 表示不大于的最大整数 ( 3 ) 对任意( 6 1 ，b 2 ) 0 ，1 ) 2 和( t 1 ，t 2 ) z 2 ，如果t ls t 2 ，则 州k m “圳哉针