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

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

Abstract

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

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.

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

Metrics

Recommended 0

No Suggested Reading articles found!

New bound of algebraic immunity of a class of Boolean function

RichHTML

PDF

Knowledge

Abstract

Cite this article

share this article

References 22

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]	Hongyang MA,Xin ZHANG,Peng’ao XU,Fen LIU,Xingkui FAN. Quantum secure communication algorithm based on cyclic code and information compression [J]. Journal on Communications, 2020, 41(3): 190-196.
[15]	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.