具有最高代数免疫阶的布尔函数的构造

《具有最高代数免疫阶的布尔函数的构造》由会员上传分享，免费在线阅读，更多相关内容在工程资料-天天文库。

1、２００９年８月北京邮电大学学报Aug．２００９第３２卷第４期JournalofBeijingUniversityofPostsandTelecommunicationsVol．３２No．４文章编号：１００７-５３２１（２００９）０４-００７３-０４具有最高代数免疫阶的布尔函数的构造１２莫骄，温巧燕（１．北京邮电大学理学院，北京１００８７６；２．北京邮电大学网络与交换技术国家重点实验室，北京１００８７６）摘要：利用布尔函数的代数标准型，总结了f与f＋１具有高次数非零零化子的条件，得到布尔函数具有最高代数免疫阶的充分条件．构造了具有

2、最高代数免疫阶的布尔函数，并对所构造函数的平衡性与对称性进行了讨论．关键词：布尔函数；非零零化子；代数标准型；代数免疫阶中图分类号：TN９１１．２２文献标识码：AConstructionsofBooleanFunctionswithOptimalAlgebraicImmunity１２MOJiao，WENQiao-yan（１．SchoolofScience，BeijingUniversityofPostsandTelecommunications，Beijing１００８７６，China；２．StateKeyLaboratoryof

3、NetworkingandSwitchingTechnology，BeijingUniversityofPostsandTelecommunications，Beijing１００８７６，China）Abstract：BasedonthealgebraicstandardformofBooleanfunctions，theconditionssatisfiedbyBooleanfunctionforf＋１withhighdegreenonzeroannihilatorsaresummarized，thesufficientcon-

4、ditionssatisfiedbytheBooleanfunctionswithoptimalalgebraicimmunityarethereforeobtained．TheBooleanfunctionswithoptimalalgebraicimmunityareconstructed．Thebalanceandthesymmetryoftheconstructedfunctionsarediscussed．Keywords：Booleanfunctions；nonzeroannihilators；algebraicst

5、andardform；algebraicimmunity近年来代数攻击在密码学研究领域引起了重型入手进行构造的方法．用代数标准型表示布尔函视．代数攻击是通过求解１个超定的多变元高次方数，可以使其代数次数一目了然．本文直接对布尔程组，用其破坏一些具有线性反馈结构的流密码的函数的代数标准型进行讨论，分析并总结了布尔函安全性．为了保证密码系统的安全，抵御代数攻击数具有最高代数免疫阶的充分条件，从代数标准型对密码系统的威胁，要求用于生成流密码的布尔函的角度构造出了具有最高代数免疫阶的n元布尔数具有较高的代数免疫阶．文献［１］明确指出，任

6、意函数．nn一个n元布尔函数的代数免疫阶都不超过（1基本概念与性质２２n代表不小于的最小整数）．国内外学者对具有最下面介绍有关布尔函数代数免疫阶的概念与２性质．n高代数免疫阶（即代数免疫阶等于）布尔函数的２定义1设f，g∈Bn，其中Bn表示全体n元布构造及所构造函数的其他密码学性质进行了深入研尔函数．如果fg＝０，则称f是g的１个零化子，同［２８］-究．至今还没有人提出从布尔函数的代数标准时也称g是f的１个零化子．收稿日期：２００８-０９-１３基金项目：国家自然科学基金项目（６０８７３１９１；６０８２１００１）；北京市自然科学基

7、金项目（４０７２０２０）作者简介：莫骄（１９６８—），女，副教授，E-mail：pridenope＠gmail．com；温巧燕（１９５９—），女，教授，博士生导师．７４北京邮电大学学报第３２卷定义2设f∈Bn，f的代数免疫阶AIn（f）指证明任取f的零化子g，假设deg（g）≤m－的是f或f＋１的非零零化子的最低代数次数．即１，即g的代数标准型中只包含次数小于或等于m－AIn（f）＝deg（g），其中g∈Bn是满足fg＝０或１的项．由fg＝０，于是f（x＋１）g（x＋１）＝（f＋１）g＝０的非零布尔函数中代数次数最低的［f（x）

8、＋１］g（x＋１）＝０，f（x）g（x＋１）＋g（x＋函数．１）＝０．［１］nn因为f只含有次数大于或等于m的项，所以引理1橙f∈Bn，AIn（f）≤（表示２２f（x）g（x＋１）也只包含次数大于或等于m的项，而n５不小于的最小整数，例如＝３）．g只包含次数小于