布尔函数线性结构分析及构造杨晓元1,2，车小亮1，肖海燕1（1.武警工程大学电子技术系网络与信息安全武警部队重点实验室，西安710086；2.西安电子科技大学计算机网络信息安全教育部重点实验室，西安710071）摘要：布尔函数的密码学性质决定了密钥流的密码强度。对于布尔函数的研究主要集中在如何更精确的刻画密码学性质之间的关系，以及如何构造布尔函数使得这几种密码学性质得到较优的组合。文章通过研究部分Bent函数中线性空间对其性质的影响，得出部分Bent函数的相关免疫阶、扩散次数与其线性维数的关系，并得到其扩散次数的范围；最后利用M-M构造法，构造出一类满足多种密码学性质且不含非零线性结构的函数。关键字：布尔函数，部分Bent函数，密码学性质，线性维数，M-M构造中图法分类号:TP309ConstructionandLinearStructureAnalysisofBooleanFunctionsYANGXiao-Yuan1,2，CHEXiao-Liang1，XIAOHai-Yan1（1.KeyLaboratoryofNetwork&InformationSecurityofAPF,EngineeringUniversityofAPF,Xi’an710086;2.KeyLaboratoryofComputerNetwork&InformationSecurityoftheMinistryofEducation,XidianUniversity,Xi’an710071）Abstract:ThecryptographicpropertiesofBooleanfunctiondeterminethesecurityofkeystream.ResearchesonBooleanfunctionarefocusonhowtodescribetherelationshipsaccuratelyamongitspropertiesandhowtoconstructaBooleanfunctioncombiningthepropertiesskillfully.Thisarticlestudiestheinfluenceofthelinearspaceinpartiallybentfunction.Therelationshipbetweentheorderofcorrelationimmuneofpartially-bentfunctionanditslineardimensionisgiven.Andtherelationshipbetweentheorderofpervasionandlineardimensionisalsoachieved，whatismore,theareaoftheorderisnumerated.Atlast,amuchbetterfunctionisconstructedbasedonaknownconstructionofM-M,whichsatisfiesmultiplecriteriaandhasnotnon-zerolinearstructureatthesametime.Keywords:Booleanfunction,Partially-Bentfunctions,Cryptographicproperties,Lineardimensions,ConstructionofM-M1引言基金项目:国家自然科学基金项目(61103230)；武警工程大学基金课题(wjy201119)。杨晓元，男，1959年生，教授，主要研究领域为密码学，信息安全等。E-mail:xawjchexl@163.com.车小亮，男1987年生，硕士研究生，主要研究方向为密码学。肖海燕，女，1985年生，讲师，主要研究方向为密码学。Bent函数的非线性度达到最大，且具有差分分布均匀的特性，然而其不具有平衡性、相关免疫性且代数次数不超过，故在具体应用上受到限制。部分Bent函数具有良好的非线性，同时又可兼有平衡性及相关免疫性。然而部分Bent函数中除了Bent函数的那部分外，具有非零线性结构，而我们所希望的密码函数是具有高的非线性度、高的扩散性和一定的相关免疫性等，最重要的是不含非零线性结构。怎样构造性质较好的布尔函数是目前研究的一个重点，且函数性质之间存在的关系也是值得继续深入研究的问题。文献[2]在这方面就得到很有价值的结果。本文首先研究了部分Bent函数的线性维数与其密码学性质之间的关系；并说明了线性维数对部分Bent函数的影响。最后利用M-M方法构造了一类综合性质较好的密码函数。2预备知识定义1设函数为上的元布尔函数，称，为的Walsh循环谱；，为的自相关函数。定义