一类偶数元最优代数免疫布尔函数分析.pdfVIP

第3l卷第2期 淮北煤炭师范学院学报(自然科学版) V01．3lNo．2 2010年6月 ofHuaibeiCoal Teachers Jun．2010 Journal Science) Industry College(Natural 一类偶数元最优代数免疫布尔函数分析 江明明，周 艳，魏仕民 (淮北师范大学数学科学学院，安徽淮北235000) 摘要：文章对用级联构造法构造的一类特殊的布尔函数，讨论了其汉明重量和非线性度，发现此类函数的汉明重量 是一个定值，并用另一种方法得到的非线性度的下界接近了最紧的下界．最后利用这类布尔函数构造了一类新的最 优代数免疫布尔函数． 关键词：布尔函数；级联；代数免疫；汉明重量；零化子 309 文献标识码：A 文章编号：1672—7177(2010)02—0005—03 中图分类号：TP 1 引言 代数攻击是近年来兴起的一种有效的攻击方法，此方法破译了很多著名的密码系统．为了抵御代数攻 击的能力越强，反之就越弱．目前已经发现了几种构造最优代数免疫布尔函数的方法，级联构造法就是一种 重要的构造方法．此方法构造了一类特殊的布尔函数，本文就这类函数的一些性质进行了研究，得出了一些 结果． 2基本概念及性质 定义1 一个It元布尔函数．厂是指从咒_R的一个映射，记B。【x】为所有lrt元布尔函数组成的集合． 对任意的／t元布尔函数厂(札X2，…，石。)都有唯一的多项式表示 二 三 a0．x／xj+…+O,12…，函l耽…戈n…，m，口驴，…口12…n∈F2 以茗l，戈2，…，菇。)=口o+乞￡t／．xi+：L 称为以戈)的代数正规型，简记为A胛．记／的代数次数为deg(刃，定义为，的代数正规型中具有非零系数 的乘积项的最大次数．任意一个凡元布尔函数．厂(舫，X2，…，龙。)也可以用真值表表示，即用一个长为2“的二 1小 1，={菇I菇∈咫，f(石)=1)，f的零点集0／={菇I戈∈R，以茹)=o)，那么有wt(刃=I An(一={glg∈B。，磨；0，g#O}． 定义4设，∈B。，f的代数免疫度定义为，的零化子和厂+1的零化子中代数次数最低的零化子的代 数次数，即A／(力=rain(deg(g)Ig∈Art(力UAn(f+1)}． 定义5 凡元布尔函数厂(菇)的Walsh谱表示为：耵(∞)=艺(一1)舢n“． ‘EB 1 定义6布尔函数的非线性度为：以(．，)=2—1一知a)【l助(∞)1． -mEB r一1 性质1【11对任意的，∈B。，都有郇(力smin{deg(一，岩}}． 三 “=1 性质2担1设／∈风，且a／(．／3d，则∑c：s耽(力s艺co 上去一1上出 性质3t。1设／∈B。，当a／(f)=之}L，则∑c：≤wt(f)≤∑c：． ‘ —————————————————一 ‘t0 ‘=0 收稿日期：2009—12—16 作者简介：江明明(1984一)，男，安徽宿州人，硕士生，研究方向：信息安全． 万方数据 6 淮北煤炭师范学院学报(自然科学版)