一类布尔函数的代数免疫度的下界

doi:10.11959/j.issn.1000-436x.2016200

通信学报 ›› 2016, Vol. 37 ›› Issue (10): 92-98.doi: 10.11959/j.issn.1000-436x.2016200

一类布尔函数的代数免疫度的下界

田叶¹,张玉清^1,²,胡予濮¹,伍高飞¹

¹ 西安电子科技大学综合业务网理论及关键技术国家重点实验室，陕西西安 710071
² 中国科学院大学国家计算机网络入侵防范中心，北京 101408

出版日期:2016-10-25 发布日期:2016-10-25
基金资助:
国家自然科学基金资助项目;国家自然科学基金资助项目;国家重点研究计划基金资助项目;国家发展改革委员会信息安全专项基金资助项目;国家111计划基金资助项目

New bound of algebraic immunity of a class of Boolean function

Ye TIAN¹,Yu-qing ZHANG^1,²,Yu-pu HU¹,Gao-fei WU¹

¹ State Key Laboratory of Integrated Services Networks,Xidian University,Xi’an 710071,China
² National Computer Network Intrusion Protection Center,University of Chinese Academy of Sciences,Beijing 101408,China

Online:2016-10-25 Published:2016-10-25
Supported by:
The National Natural Science Foundation of China;The National Natural Science Foundation of China;The National Key Research and Development Project;The National Information Security Special Projects of National Development,The Reform Commission of China;China 111 Project

摘要/Abstract

摘要：

代数免疫度是衡量布尔函数抵抗代数攻击的重要指标。最近，Mesnager等研究了布尔函数的零化子与函数所对应循环码最小距离之间的联系，代数免疫度的下界可以由对应的循环码的最小距离得到。解决了Mesnager提出的一个公开问题，给出了一类特定函数的零化子次数的下界，并得到一类布尔函数的代数免疫度的下界。

关键词: 密码学, 布尔函数, 零化子, 代数免疫度, 循环码, 最小距离

Abstract:

Algebraic immunity quantified the resistance of a Boolean function to the algebraic attack.Recently,Mesnager,et al showed that there were direct linked between the annihilators used in algebraic attacks and the coding theory.They showed that the lower bound of the algebraic immunity of Boolean functions could been derived from the minimum distance of the associated cyclic codes.An open problem proposed by Mesnager is settled with a detailed proof.Also,a lower bound of algebraic immunity of a class of Boolean functions will be introduced.

Key words: cryptography, Boolean functions, annihilators, algebraic immunity, cyclic code, minimum distance

田叶,张玉清,胡予濮,伍高飞. 一类布尔函数的代数免疫度的下界[J]. 通信学报, 2016, 37(10): 92-98.

Ye TIAN,Yu-qing ZHANG,Yu-pu HU,Gao-fei WU. New bound of algebraic immunity of a class of Boolean function[J]. Journal on Communications, 2016, 37(10): 92-98.

参考文献 22

[1]	COURTOIS N , MEIER W . Algebraic attacks on stream ciphers with linear feedback[C]// Cryptology-Eurocrypt 2003,LNCS 2656. Berlin:Springer-Verlag, 2003: 345-359.
[2]	ARMKNECHT F , KRAUSE M . Algebraic attacks on combiners with memory[C]// Cryptology-Crypto. 2003: 162-175.
[3]	MEIER W , PASALIC E , CARLET C . Algebraic attacks and decomposition of Boolean functions[C]// Cryptology -Eurocrypt 2004,LNCS 3027. 2004: 474-491.
[4]	DALAI D , MAITRA S , SARKAR S . Cryptographically significant Boolean functions:construction and analysis in terms of algebraic immunity[J]. Fast Software Encryption , 2005,3557: 98-111.
[5]	CARLET C , DALAI D , GUPTA C . Algebraic immunity for cryptographically significant Boolean function:analysis and construction[J]. IEEE Transactions on Information Theory, 2006,52(7): 3105-3121.
[6]	CARLET C , FENG K . An infinite class of balanced functions with optimal algebraic immunity,good immunity to fast algebraic attacks and good nonlinearity[C]// Cryptology-Asiacrypt 2008,LNCS 5350. 2008, 5350: 425-440.
[7]	RIZOMILIOTIS P . On the resistance of Boolean functions against algebraic attacks using univariate polynomial representation[J]. IEEE Trans Information Theory, 2010,56(8): 4014-4024.
[8]	TU Z , DENG Y . A conjecture on binary string and its applications on constructing Boolean functions of optimal algebraic immunity[J]. Designs Codes and Cryptography, 2011,60(1): 1-14.
[9]	HELLESTH T , RONJOM S . Simplifying algebraic attacks with univariate analysis[C]// Information Theory and Applications Workshop (ITA). 2011: 1-7.
[10]	TANG D , CARLET C , TANG X . Highly nonlinear Boolean functions with optimal algebraic immunity and good behavior against fast algebraic attacks[J]. IEEE Trans Inf Theory, 2013,59(59): 653-664.
[11]	LIN J , WANG M , LI Y . On annihilators in fewer variables:basic theory and applications[J]. Chinese Journal of Electronics, 2013,22(3): 489-494.
[12]	欧智慧, 赵亚群, 李旭 . 一类密码函数的构造与分析[J]. 通信学报, 2013,4(4): 106-113. OU Z H , ZHAO Y Q , LI X . Construction and analysis of one class of cryptographic functions[J]. Journal on Communications, 2013,34(4): 106-113.
[13]	MESNAGER S , . A note on linear codes and algebraic immunity of Boolean Functions[C]// 21st International Symposium on Mathematical Theory of Networks and Systems. 2014.
[14]	MACWILLIAMS F , SLOANE N . The theory of error-correcting Codes[M]. North-Holland Mathematical Library. Amsterdam,The Netherlands: North-HollandPress, 1977.
[15]	HUFFMAN W , PLESS V . Fundamentals of error-correcting codes[M]. Cambridge,UK: Cambridge Univ.PressPress, 2003.
[16]	BETTI E , SALA M . A new bound for the minimum distance of a cyclic code from its defining set[J]. IEEE Trans Information Theory, 2006,52(8): 3700-3706.
[17]	BETTEN A , BRAUN M , FRIPERTINGER H . Error- correcting linear codes[M]. Berlin,Germany: Springer- VerlagPress, 2006.
[18]	GAO J , HU Y , LI X . Linear span of the optimal frequency hopping sequences from irreducible cyclic Codes[J]. Chinese Journal of Electronics, 2015,24(4): 818-823.
[19]	DING C , DU X , ZHOU A . The bose and minimum distance of a class of BCH codes[J]. IEEE Trans Information Theory, 2015,61(5): 2351-2356.
[20]	FENG X , GONG G . On algebraic immunity of trace inverse functions on finite fields of characteristic two[J]. Journal of Systems Science and Complexity, 2016,29(1): 272-288.
[21]	WU D , QI W . On the spectral immunity of periodic sequences restricted to binary annihilators[J]. Designs Codes and Cryptography, 2016,78(2): 533-545.
[22]	DING C . A construction of binary linear codes from Boolean functions[J]. Discrete Mathematics, 2016,339(9): 2288-2303.

一类布尔函数的代数免疫度的下界

New bound of algebraic immunity of a class of Boolean function

在线阅读

PDF下载

可视化

摘要/Abstract

引用本文

使用本文

参考文献 22

相关文章 15

Metrics

推荐阅读 0

[1]	王维琼, 许豪杰, 崔萌, 谢琼. 优良布尔函数的混合禁忌搜索算法[J]. 通信学报, 2022, 43(5): 133-143.
[2]	田有亮, 蒋小霞. 通用可组合框架下的公平理性委托计算[J]. 通信学报, 2021, 42(9): 106-119.
[3]	田苗苗, 陈静, 仲红. 格上基于身份的增量签名方案[J]. 通信学报, 2021, 42(1): 108-117.
[4]	马鸿洋,张鑫,徐鹏翱,刘芬,范兴奎. 基于循环码和信息压缩融合的量子保密通信算法[J]. 通信学报, 2020, 41(3): 190-196.
[5]	于斌, 黄海, 刘志伟, 赵石磊, 那宁. 面向多椭圆曲线的高速标量乘法器设计与实现[J]. 通信学报, 2020, 41(12): 100-109.
[6]	杜蛟,刘春红,庞善起. 4t-1元旋转对称2-弹性函数的构造[J]. 通信学报, 2020, 41(11): 169-175.
[7]	田苗苗,高闯,陈洁. 格上基于身份的云存储完整性检测方案[J]. 通信学报, 2019, 40(4): 128-139.
[8]	严新成,陈越,贾洪勇,陈彦如,张馨月. 支持高效密文密钥同步演化的安全数据共享方案[J]. 通信学报, 2018, 39(5): 123-133.
[9]	王真,马兆丰,罗守山. 基于身份的移动互联网高效认证密钥协商协议[J]. 通信学报, 2017, 38(8): 19-27.
[10]	杜蛟,尚玉婧,赵金玲,董乐,张恩. 8元多输出旋转对称弹性函数的构造与计数[J]. 通信学报, 2017, 38(7): 47-55.
[11]	汤永利,胡明星,刘琨,叶青,闫玺玺. 新的格上基于身份的全同态加密方案[J]. 通信学报, 2017, 38(5): 39-47.
[12]	田叶,张玉清,胡予濮. 最小距离为4的最优五元循环码[J]. 通信学报, 2017, 38(2): 74-80.
[13]	袁峰,江继军,杨旸,许盛伟. 与3类向量值密码函数仿射等价的函数数量研究[J]. 通信学报, 2017, 38(11): 84-92.
[14]	杜红珍,温巧燕. 无证书强指定验证者多重签名[J]. 通信学报, 2016, 37(6): 20-28.
[15]	袁宏博，杨晓元，魏立线，刘龙飞. 全局雪崩准则的刻画及函数构造[J]. 通信学报, 2014, 35(Z2): 35-255.