最优代数免疫布尔函数的完全构造

《最优代数免疫布尔函数的完全构造》由会员上传分享，免费在线阅读，更多相关内容在学术论文-天天文库。

1、最优代数免疫布尔函数的完全构造最优代数免疫布尔函数的完全构造　0引言　　基于线性反馈移位寄存器的代数攻击方法一经提出，就对现有流密码体制形成了巨大的威胁。运用代数攻击的方法人们成功破解了用具有良好性质.L.的布尔函数所设计的，能够抵抗所有已知攻击的Toycrypt和LILI128［1-4］。布尔函数代数免疫的概念是由MEier等［5］于2004年美密会上提出的，代数免疫是衡量其抵抗代数攻击的能力。如何确定布尔函数的代数免疫及具有最优代数免疫(MaximumAlgebraicImmunity,MAI)布尔函数的构造与计数成为密码学者关注的热点问题之一。　AI(f)

2、={mindeg(g)

3、g∈An(f)org∈An(f+1)}　　布尔函数f的代数免疫度越大，函数抵抗代数攻击的能力越强；反之越弱。定理1是代数免疫度的一些性质。.L.　　定理1［5-6］设f∈Bn，则：　　1)AI(f)≤「n/2；　　2)设d<「n/2为整数，若AI(f)>d，则有∑di=0Cin≤AI布尔函数构造方法　　Carlet等［8］利用布尔函数的单变元表达式以及代数编码的相关结论，构造出一类具有最优代数免疫的布尔函数。　　定理2［8］n为正整数，&al

4、pha;为F2n的一个本原元。设f是F2n上的一个单变元多项式函数，其支撑集为{0,1,α,α2,,α2n－1－2}，则f具有最优代数免疫「n/2。　　显然定理1中构造的函数是平衡函数，并且　矩阵H的列向量记为Hi=(αi1,,αi2n－1)T,i=0,1,,2n－2，则H=(H0H1H2n－2)。这样式(2)可以写为：　　H0g0+H1g1++H2n－2g2n－2=0(4)　　本章要讨论的内容是函数f

5、是否能够达到最优代数免疫，即是否存在零化子g满足deg(g)是否缺少相关的字母，是否应该是deg(g)?请明确，或补充。<「n/2，即是否存在解向量(g0,g1,,g2n－2)满足;0≤i≤2n－2,e;=(Hi)e;非退化。此时f没有代数次数<「n/2的零化子。　　　　　　定理3设n为正整数，设f是F2n上的一个平衡布尔函数，其支撑集为{α1,,α2n－1}，其中αi∈F2n，i=1,,2n-1。矩阵H如式(3)所示，规

6、模为2n－1(2n－1)。其列向量分别记为H0,H1,,H2n－2。令A={0≤i≤2n－2

7、e;=(Hi)i∈A。若矩阵H′非退化，则f没有代数次数<「n/2的零化子。　　证明用反证法证明，若f存在代数次数<「n/2的非零零化子g此句是否应该为非零化子g？请对比上下文，作出调整。，其单.L.变元多项式表示为g(x)=∑2n－1i=0gixi，当iA时，gi=0。g的单变元多项式表示可以写为：　　g(x)=∑i∈Agixi　　　

8、　则方程组(2)演化为：　　∑e;(gi)Ti∈A=0(6)　　注意此时矩阵H中起作用的列向量为(Hi)i∈A。又知g是一个非零的函数，故e;非退化矛盾。故deg(g)<「n/2当且仅当g=0，此时f没有代数次数<「n/2的零化子，即证。这个#符号有何作用，是否可以删除，请明确。回复：#表示证明结束。也可以用实心方块表示。最好不要删除。　当n为奇数时，具有最优代数免疫的布尔函数一定是平衡的［5］，若一个平衡布尔函数的单变元多项式表示满足定理2的条件，就具有最优代数免疫。实际上，矩阵H&pr

9、ime;非退化是奇数元布尔函数代数免疫达到最优的充要条件。　　定理4设n为奇数，f∈Bn是平衡函数，α是F2n上的一个本原元，f的支撑集为{αi1,,αi2n－1}。符号H，H′和A的定义同上，则f具有最优代数免疫「n/2的充要条件是矩阵H′非退化。　　证明充分性已证，下面证明必要性。　　设g是f的一个零化子，g的单变元表示为g=∑2n－2i=0gixi，若矩阵H′=(Hi)i∈A退化，不妨