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

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

Abstract

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

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.

References 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.

Metrics

Recommended 0

No Suggested Reading articles found!

Extended algebraic immunity of symmetric Boolean function

RichHTML

PDF

Knowledge

Abstract

Cite this article

share this article

References 16

Related Articles 15

Metrics

Recommended 0

[1]	Huawei HUANG. Security analysis of public-key cryptosystems based on matrix action problem against quantum attack [J]. Journal on Communications, 2023, 44(3): 220-226.
[2]	Ziyuan WANG, Ruizhong DU. Certificateless public key cryptography based provable data possession scheme in edge environment [J]. Journal on Communications, 2022, 43(7): 62-72.
[3]	Zhu WANG, Siqi YANG, Fenghua LI, Kui GENG, Tingting PENG, Mengyao SHI. Efficient and provably-secure certificateless sequential aggregate signature scheme [J]. Journal on Communications, 2022, 43(5): 58-67.
[4]	Bin LI, Xiaojie CHEN, Feng FENG, Qinglei ZHOU. FPGA multi-unit parallel optimization and implementation of post-quantum cryptography CRYSTALS-Kyber [J]. Journal on Communications, 2022, 43(2): 196-207.
[5]	Youliang TIAN, Xiaoxia JIANG. Fair and rational delegation of computation in the universally composable framework [J]. Journal on Communications, 2021, 42(9): 106-119.
[6]	Hui LIU, Xinyan LIU, Yan XU, Hong ZHONG, Meng WANG. Privacy protection of warning message publishing protocol in VANET [J]. Journal on Communications, 2021, 42(8): 120-129.
[7]	Jiangtao DONG, Peiwen YAN, Ruizhong DU. Verifiable access control scheme based on unpaired CP-ABE in fog computing [J]. Journal on Communications, 2021, 42(8): 139-150.
[8]	Huaqun WANG, Zhe LIU, Debiao HE, Jiguo LI. Identity-based provable data possession scheme for multi-source IoT terminal data in public cloud [J]. Journal on Communications, 2021, 42(7): 52-60.
[9]	Wenbo ZHANG, Wenhua HUANG, Jingyu FENG. Secure communication mechanism for VSN based on certificateless signcryption [J]. Journal on Communications, 2021, 42(7): 128-136.
[10]	Fei TANG, Jiali BAO, Yonghong HUANG, Dong HUANG, Huili WANG. Multi-authority attribute-based identification scheme [J]. Journal on Communications, 2021, 42(3): 220-228.
[11]	Bin WANG, Si CHEN, Jiadong CHEN, Xing WANG. DWB-AES: an implementation of dynamic white-box based on AES [J]. Journal on Communications, 2021, 42(2): 177-186.
[12]	Houzhen WANG, Xinwei CAI, Yan GUO, Huanguo ZHANG. 5-pass zero-knowledge identity authentication scheme based on matrix completion problem [J]. Journal on Communications, 2021, 42(11): 79-86.
[13]	Miaomiao TIAN, Jing CHEN, Hong ZHONG. Identity-based incremental signature scheme from lattices [J]. Journal on Communications, 2021, 42(1): 108-117.
[14]	Jiao DU,Chunhong LIU,Shanqi PANG. Constructions of rotation symmetric 2-resilient functions with 4t_-1 number of variables [J]. Journal on Communications, 2020, 41(11): 169-175.
[15]	Liguo FANG,Zhengxin FU,Hao HU,Gang SHEN,Bin YU. Research on algorithm for raster map multi-level sharing based on region incrementing color visual cryptography [J]. Journal on Communications, 2019, 40(9): 24-32.