布尔函数代数免疫性研究.pdf

《布尔函数代数免疫性研究.pdf》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。

1、第34卷第4期淮北师范大学学报(自然科学版)VO1．34N0．42013年l2月JournalofHuaibeiNormalUniversity(NaturalScience)Dec．2013布尔函数代数免疫性研究曹浩，魏仕民(1．安徽科技学院理学院，安徽滁州233100；2．淮北师范大学计算机科学与技术学院，安徽淮北235000)摘要：针对当前密码学中对具有多种好的密码学性质布尔函数的构造需求，通过分析函数在重量≤d的向量处的取值与代数免疫阶之间的内在关系，在给出高阶代数免疫函数判断方法的基础上，给出适当改变函数在部分点的取值而不降低代数免疫阶的方法，利用该方法，

2、给出了在代数免疫性、非线性性、平衡性和相关免疫性等方面均达到最优的布尔函数的一个构造实例．关键词：布尔函数；代数免疫阶；支撑点集；相关免疫阶；非线性度中图分类号：TN918．1文献标识码：A文章编号：2095—0691(2013)04—0006—04布尔函数作为密码学设计和分析的重要工具，一直是密码学研究热点．为抵抗各种密码分析方法，学者们提出许多布尔函数的密码学指标，如相关免疫性、平衡性、非线性性等．2003年，Courtois和Meier⋯在欧洲密码学年会上提出了一种特别有效的密码分析方法——代数攻击，并成功地攻破了许多种著名的密码体制．为有效衡量布尔函数抵抗代

3、数攻击的能力，密码学者提出了代数免疫阶，它被定义为布尔函数厂和．①1的最低次数的非零零化多项式的次数．为抵抗代数攻击，函数的代数免疫阶不能太低，构造具有较高代数免疫阶的布尔函数显得非常有意义．国内外密码学者纷纷对代数攻击进行研究。，从不同角度给出多种具有高代数免疫阶布尔函数的构造．然而，在满足代数免疫阶较高的同时，满足多种其他密码学性质的良好布尔函数的构造却仍然是一个难题．本文在深入研究布尔函数代数免疫性与其零点集和支撑点集的基础上，给出了代数免疫阶不低于d的判断方法和具有较高代数免疫阶布尔函数的构造，本文首次研究了改变布尔函数在部分点的值却不降低代数免疫阶的充分条

4、件，并利用该方法，在已具有高代数免疫性布尔函数类中，通过适当改变部分点的函数值，可以构造在平衡性、代数免疫性、非线性性和相关免疫性等方面均达到最优的布尔函数，并给出一个4元布尔函数的构造实例，为构造多元具有良好密码学性质的布尔函数提供一条途径。1基本概念{0，1}到{0，1}的映射称为元布尔函数，通常用f，g，h等表示，几元布尔函数的全体记为B记o，：{xelO，1}if()=0}和lp={∈{0，1}l厂()：1}，分别称为布尔函数_厂的零点集和支撑点集．如果Q，和l，中的元素个数相同，则称)是平衡布尔函数．n元布尔函数厂()可以用上的多项式唯一地表示为：l厂(2

5、，⋯，)=n010iXinijXiXj0⋯OaI_2-一(1),，，I这里ao,a，n，⋯a⋯EF2，称为)的代数标准f~J．(ANF))的ANF中非零最高次项的次数称为／的次，，数，记为deg∽．如)的次数等于1，则厂()为仿射函数．在ANF中)的系数与函数值有下列关系：z，／∽(2)，}收稿日期：20l3一O6—13基金项目：国家自然科学基金资助项目(60573026)；安徽省自然科学研究资助项目(KJ2010B059，KJ2013B083)作者简介：曹浩(1981一)，男，安徽宿州人，硕士，讲师，主要研究方向为密码学；通讯作者：魏仕民(1962一)男，安徽巢湖

6、人．博士，教授，主要研究方向为密码学与信息安全．第4期曹浩等：布尔函数代数免疫性研究7其中，sup(x)表示n元向量=(⋯，％)中元素1的位置集合，即sup(x)={ilx=1}．循环普是研究布尔函数密码学性质的重要工具，定义为5，㈤=2’(一1)(WE{0，1})(3)xe{0，1l布尔函数的非线性度是衡量密码函数抵抗代数攻击的能力，它被定义为该函数与所有仿射函数的最小距离，非线性度和循环谱之间有如下重要关系：Ⅳ，=2’(1-max{IS：(w)l，WE{0，1)(4)如果()=O对所有=(。，W：，⋯⋯W)∈{0，1}且1≤￡()≤m都成立，则称厂是m阶相关免疫

7、函数，如是平衡的，则穆厂为m阶弹性函数．这里wt(w)是指W，W。，⋯，W中1出现的个数，即W的重量．文献[12]指出，布尔函数的变元个数、代数次数d和相关免疫阶m由如下关系：，n+≤d(5)当布尔函数为平衡时，式(5)将是严格不等式．谢，geB，g称为的零化多项式，如果对任意的∈{0，1}都)·g()=0成立．．厂的零化多项式的集合记为Ann∽的代数免疫阶定义为：AI∽=rain{geBIgeAnn∽UAnn(1Of)J~g#O}．文献[13]指出，含有n个变元的布尔函数厂，代数免疫阶最大为f．／2]，我们把满足AI(厂)=fn／2]的布尔函数称为代数免疫最优