对称布尔函数的扩展代数免疫度

doi:10.3969/j.issn.1000-436x.2014.z2.024

通信学报 ›› 2014, Vol. 35 ›› Issue (Z2): 179-183.doi: 10.3969/j.issn.1000-436x.2014.z2.024

对称布尔函数的扩展代数免疫度

伍高飞¹,刘雪峰¹,田叶¹,张玉清^1,²

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

出版日期:2014-11-25 发布日期:2017-06-19
基金资助:
国家自然科学基金资助项目;国家自然科学基金资助项目

Extended algebraic immunity of symmetric Boolean function

Gao-fei WU¹,Xue-feng LIU¹,Ye TIAN¹,Yu-qing ZHANG^1,²

¹ 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:2014-11-25 Published:2017-06-19
Supported by:
The National Natural Science Foundation of China;The National Natural Science Foundation of China

摘要/Abstract

摘要：

构造具有最优代数免疫度的布尔函数在流密码中有重要作用，基于布尔函数的单变量多项式表示，构造了一类达到最大扩展代数免疫度的布尔函数。以前的一些函数是这类函数的特例。利用对称布尔函数的基本性质，分析了具有最大代数免疫度的对称布尔函数的扩展代数免疫度。得出结论：共有 $2^{＆#x230A; lb (n / 2) ＆#x230B; + 2}$ 个达到最大扩展代数免疫度的n（n是偶数）元对称布尔函数。

关键词: 密码学, 布尔函数, 对称布尔函数, 代数免疫度, 零化子, 扩展代数免疫度

Abstract:

Boolean functions with optimal algebraic immunity play an important role in stream ciphers.Based on the univariate polynomial representation of Boolean functions,a construction of Boolean functions with maximum extended algebraic immunity (EAI) is proposed,some previous results are special cases of our construction.The EAI of symmetric Boolean functions which have maximum algebraic immunity (AI) are analyzed by using the properties of symmetric Boolean functions.The result shows that there are only $2^{＆#x230A; lb (n / 2) ＆#x230B; + 2}$ n-variable (n even) symmetric Boolean functions achieve maximum EAI.

Key words: cryptography, Boolean functions, symmetric Boolean functions, algebraic immunity; annihilators, extended algebraic immunity

伍高飞,刘雪峰,田叶,张玉清. 对称布尔函数的扩展代数免疫度[J]. 通信学报, 2014, 35(Z2): 179-183.

Gao-fei WU,Xue-feng LIU,Ye TIAN,Yu-qing ZHANG. Extended algebraic immunity of symmetric Boolean function[J]. Journal on Communications, 2014, 35(Z2): 179-183.

参考文献 16

[1]	COURTOIS N , MEIER W . Algebraic attacks on stream ciphers with linear feedback[A]. Advances in Cryptology-Eurocrypt 2003,LNCS 2656[C]. Berlin, 2003. 345-359.
[2]	MEIER W , PASALIC E , CARLET C . Algebraic attacks and decomposition of Boolean functions[A]. Advances in Cryptology-Eurocrypt 2004,LNCS 3027[C]. Berlin,Springer-Verlag, 2004. 474-491.
[3]	CARLET C . Constructing balanced functions with optimal algebraic immunity[A]. IEEE ISIT 2007[C]. Nice,France, 2007. 451-455.
[4]	CARLET C , FENG K . An infinite class of balanced functions with optimal algebraic immunity,good immunity to fast algebraic attacks and good nonlinearity[A]. Advances in Cryptology-Asiacrypt 2008,LNCS 5350[C]. Berlin: Springer-Verlag, 2008. 425-440.
[5]	DALAI D , MAITRA S , SARKAR S . Basic theory in construction of Boolean functions with maximum possible annihilator immunity[J]. Des.Codes Cryptogr, 2006,40(1): 41-58.
[6]	WANG Q , PENG J , KAN H ,et al. Constructions of cryptographically significant Boolean functions using primitive polynomials[J]. IEEE Trans Inf Theory, 2010,56(6): 3048-3053.
[7]	TU Z , DENG Y . A conjecture on binary string and its applications on constructing Boolean functions of optimal algebraic immunity[J]. Des.Codes Cryptogr, 2011,60(1): 1-14.
[8]	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(1): 653-664.
[9]	李雪莲, 胡予濮 . 对具有高代数免疫度布尔函数的新型代数攻击[J]. 西安电子科技大学学报, 2009,36(4): 702-707. LI X L , HU Y P . Algebraic attack on symmetric Boolean functions with a high algebraic immunity[J]. Journal of Xidian University, 2009,36(4): 702-707.
[10]	ZHANG X , PIEPRZYK J , ZHENG Y . On algebraic immunity and annihilators[A]. ICISC 2006,LNCS 4296[C]. Berlin,Springer-Verlag, 2004. 65-80.
[11]	WANG C , CHEN X . On extended algebraic immunity[J]. Des Codes Cryptogr, 2010,57(3): 271-281.
[12]	熊晓雯, 屈龙江, 李超 . 布尔函数的扩展代数免疫度[J]. 电子与信息学报, 2011,33(2): 284-288. XIONG X W , QU L J , LI C . On extended algebraic immunity of Boolean functions[J]. Journal of Electronics ＆ Information Technology, 2011,33(2): 284-288.
[13]	CARLET C . Comment on constructions of cryptographically significant Boolean functions using primitive polynomials[J]. IEEE Trans Inf Theory, 2011,57(7): 4852-4853.
[14]	LI N , QI W . Symmetric Boolean functions depending on an odd number of variables with maximum algebraic immunity[J]. IEEE Trans Inf Theory, 2006,52(5): 2271-2273.
[15]	QU L , LI C , FENG K . A note on symmetric Boolean functions with maximum algebraic immunity in odd number of variables[J]. IEEE Trans Inf Theory, 2007,53(8): 2908-2910.
[16]	PENG J , WU Q , KAN H . On symmetric Boolean functions with high algebraic immunity on even number of variables[J]. IEEE Trans Inform Theory, 2011,57(10): 7205-7220.

对称布尔函数的扩展代数免疫度

Extended algebraic immunity of symmetric Boolean function

在线阅读

PDF下载

可视化

摘要/Abstract

引用本文

使用本文

参考文献 16

相关文章 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(12): 100-109.
[5]	杜蛟,刘春红,庞善起. 4t-1元旋转对称2-弹性函数的构造[J]. 通信学报, 2020, 41(11): 169-175.
[6]	田苗苗,高闯,陈洁. 格上基于身份的云存储完整性检测方案[J]. 通信学报, 2019, 40(4): 128-139.
[7]	严新成,陈越,贾洪勇,陈彦如,张馨月. 支持高效密文密钥同步演化的安全数据共享方案[J]. 通信学报, 2018, 39(5): 123-133.
[8]	王真,马兆丰,罗守山. 基于身份的移动互联网高效认证密钥协商协议[J]. 通信学报, 2017, 38(8): 19-27.
[9]	杜蛟,尚玉婧,赵金玲,董乐,张恩. 8元多输出旋转对称弹性函数的构造与计数[J]. 通信学报, 2017, 38(7): 47-55.
[10]	汤永利,胡明星,刘琨,叶青,闫玺玺. 新的格上基于身份的全同态加密方案[J]. 通信学报, 2017, 38(5): 39-47.
[11]	袁峰,江继军,杨旸,许盛伟. 与3类向量值密码函数仿射等价的函数数量研究[J]. 通信学报, 2017, 38(11): 84-92.
[12]	杜红珍,温巧燕. 无证书强指定验证者多重签名[J]. 通信学报, 2016, 37(6): 20-28.
[13]	田叶,张玉清,胡予濮,伍高飞. 一类布尔函数的代数免疫度的下界[J]. 通信学报, 2016, 37(10): 92-98.
[14]	袁宏博,杨晓元,魏立线,刘龙飞. 全局雪崩准则的刻画及函数构造[J]. 通信学报, 2014, 35(Z2): 251-255.
[15]	伍高飞，刘雪峰，田叶，张玉清. 对称布尔函数的扩展代数免疫度[J]. 通信学报, 2014, 35(Z2): 24-183.