资源描述：
《浅谈辅助函数的构造方法》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。
1、浅谈辅助函数的构造方法1、相关定义1.1、弹性函数的定义和性质日本学者Siegenthaler在1985年对非线性组合流密码系统提出了一种称为”分别征服”(Divide-and-conquer)的攻击方法[53],即后来所称的相关攻击。相关攻击的基本思想是考察密钥流序列和原驱动序列之间的相关性,两者相关性越强,就越容易实施攻击[53]。为了抵抗相关攻击,非线性组合流密码系统中的非线性函数应当具有一定的相关免疫性。为此,Siegenthaler给出了相关免疫函数的定义:定义2.3[33]设f(x1,x2,?,xn)是一个n元布尔函数,其中x1,x2
2、,?,xn是?2上均匀分布的独立随机变量,如果f与x1,x2,?,xnm1,,中任意的个变元xi?xim统计独立,即对于任意的(a1,a2,?,am)??2m及a??2,均有12(
3、i1,i2,,m)pf?ax?ax?a?xim?a?p(f?a),称f是m阶相关免疫函数。下面的定理2.9给出了判别相关免疫函数的等价条件:定理2.9[33]设f(x)?f(x1,x2,?,xn)为n元布尔函数,其中x1,x2,?,xn是?2上均匀分布的独立随机变量,则下列三个条件等价:(1)f(x)是m阶相关免疫函数;(2)对任意的w??2n,1?wt(w)?m,f
4、(x)与w?x统计独立;(3)对任意的w??2n,1?wt(w)?m,f(x)?w?x是平衡函数。定理2.10[33]设f(x)?f(x1,x2,?,xn)为n元布尔函数,其中x1,x2,?,xn是?2上国防科学技术大学研究生院硕士学位论文均匀分布的独立随机变量,则f(x)0是阶相关免疫函数当且仅当对任意的,均有ma??2n,1?wt(a)?mWf(a)?。定理2.10通常称为Xiao-Massey定理,该定理刻画了阶相关免疫函数的谱特征。由于密码系统中所使用的布尔函数通常需要满足平衡条件,后来给出了如下弹性函数的定义:m定义2.4[33]设f(
5、x)?f(x1,x2,?,xn)是一个n元布尔函数,如果f(x)既是阶相关免疫函数又是平衡函数,则称m第11页f(x)是m阶弹性函数。注意到布尔函数f(x)是平衡函数当且仅当Wf(x)?0,于是定理2.11[33]布尔函数f(x)0n是阶弹性函数当且仅当对于任意,,有。2ma??n0?wt(a)?mWf(a)?弹性函数既具有相关免疫性,又具有平衡性,给定一个布尔函数,我们希望弹性阶越大越好,但弹性阶与代数次数,非线性度等其它密码学指标存在一定的制约关系。下面的定理说明了布尔函数的相关免疫阶或者弹性阶与代数次数的相互关系:定理2.12[33]给定一
6、个元布尔函数f(x)?f(x1,x2,?,xn),若f(x)是m(1?m?n?1)阶弹性函数,则degf?n?m?1;若f是m(1?m?n?1)阶相关免疫函数,则degf?n?m。定理2.12给出了弹性函数的代数次数的上界,这个上界最早由Siegenthaler给出,所以被称为Siegenthaler界。利用McEliece定理,Carlet给出了次数为的阶相关免疫函数或者弹性函数的Walsh变换性质。dm定理2.13[33]设f(x)是n元布尔函数,并且degf?d?1,若f(x)是阶相关免疫函数,,则mm?n?111Wf(a)?0mod2m?
7、????n?dm????,?a??2n;若f(x)是m阶弹性函数,m?n?2,则222m2od,2.nm???????d?????a??n1Wf(a)0mNL(f)注意到对于任意的布尔函数都有?n?1?2n/2?,再利用定理2.3,可以得到代数次数为d的m阶弹性函数非线性度的上界。定理2.14[33]设f(x)是代数次数为d的n元m阶弹性布尔函数,,是使得m?n?2kk2m?1???(n?m?2)/d???2n?1?2n/2?1国防科学技术大学研究生院硕士学位论文成立的最大整数,则11(2)/1(2)/22(2)/222(2)/2.,2,nmnm
8、dfmnmdmnmdnNkmnmdn????????????????????????????????????????????时时当当;若不考虑代数次数,则由定理2.14可以直接得到如下定理:定理2.15[33]设f(x)是n元m阶弹性函数,k是使得k2m?1?2n?1?2n/2?1成立的最大整数,则111222222.,,2nmmfmnNkmn????????????????当时当时;定理2.15的上界最早由Sarkar等人在文[49]中给出,所以这个界称为Sarkar界,显然若一个弹性函数达到Sarkar界,则它的代数次数也达到Siegenth
9、aler界。关于相关免疫度与代数免疫度之间的联系,目前还没有一个好的结果,但利用代数次数,可以给出二者之间一个简单的联系。由于AI(f)
