优良布尔函数的混合禁忌搜索算法

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

Abstract

Abstract:

Boolean function in symmetric cryptographic algorithm must satisfy excellent cryptographic criteria to ensure the security of the algorithm.By combining the advantages of tabu search algorithm and hill climbing algorithm, a new heuristic generation algorithm called hybrid tabu search algorithm for excellent Boolean function was proposed.A large number of Boolean function with high nonlinearity, low autocorrelation, one-resilient, optimal algebraic degree, optimal algebraic immunity, optimal (suboptimal) resistance to fast algebraic attacks could be obtained quickly by applying the proposed algorithm.Simulation results demonstrate that the cryptographic properties of the Boolean function obtained by the proposed algorithm with strong search ability and fast running speed are better than the results of known optimization algorithm.Moreover, the algorithm also provides good Boolean function that cannot be obtained by using construction method.

Key words: Boolean function, tabu search algorithm, resiliency, nonlinearity

CLC Number:

TP301.6

Weiqiong WANG, Haojie XU, Meng CUI, Qiong XIE. Hybrid tabu search algorithm for excellent Boolean function[J]. Journal on Communications, 2022, 43(5): 133-143.

Figures/Tables 6

n	${HTS}_{{cost}_{1}}$	${HTS}_{{cost}_{2}}$
8	(116,24,6,4,7)	(116,24,6,4,7)
9	(236,48,7,5,8)	(236,48,7,5,8)
10	(484,80,8,5,10)	(488,72,8,5,9)
11	(984,112,9,6,10)	(988,104,9,6,10)
12	(1 988,144,10,6,11)	(1 996,152,10,6,11)
13	(4 012,216,11,7,12)	(4 020,232,11,7,12)
14	(8 072,320,12,7,13)	(8 080,320,12,7,13)

n	文献[8]	文献[9]	文献[12]	文献[13]	${HTS}_{{cost}_{2}}$
8	(112,-,6,4,-)	(116,32,6,4,7)	(116,48,6,4,7)	(112,48,6,4,7)	(116,24,6,4,7)
9	—	—	(236,48,7,4,8)	(232,80,7,4,8)	(236,48,7,5,8)
10	(484,-,8,5,-)	(488,-,8,5,8)	(484,96,8,5,9)	—	(488,72,8,5,9)
11	—	—	(984,136,9,5,10)	—	(988,104,9,6,10)
12	(1996,-,10,6,-)	(2 008,96,9,6,9)	(1988,184,10,6,11)	—	(1996,152,10,6,11)
13	—	—	(4 012,288,11,6,12)	—	(4 020,232,11,7,12)
14	(8100,-,12,7,-)	(8112,-,11,-,-)	(8 072,368,12,7,13)	—	(8 080,320,12,7,13)

References 32

[1]	张卫国, 肖国镇 . 具有偶数个变元的高非线性度平衡布尔函数的构造[J]. 电子学报, 2011,39(3): 727-728.
	ZHANG W G , XIAO G Z . Construction of balanced Boolean functions with high nonlinearity on even number variables[J]. Acta Electronica Sinica, 2011,39(3): 727-728.
[2]	欧智慧, 赵亚群, 李旭 . 一类密码函数的构造与分析[J]. 通信学报, 2013,34(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.
[3]	孙天锋, 胡斌, 杨阳 . Plateaued 函数的构造方法研究[J]. 电子与信息学报, 2018,40(10): 2352-2357.
	SUN T F , HU B , YANG Y . Research on the construction of Plateaued functions[J]. Journal of Electronics ＆ Information Technology, 2018,40(10): 2352-2357.
[4]	杜蛟, 刘春红, 庞善起 . 4t-1 元旋转对称 2-弹性函数的构造[J]. 通信学报, 2020,41(11): 169-175.
	DU J , LIU C H , PANG S Q . Constructions of rotation symmetric 2-resilient functions with 4t-1 number of variables[J]. Journal on Communications, 2020,41(11): 169-175.
[5]	ZHANG F R , PASALIC E , WEI Y Z . Constructions of balanced Boolean functions on even number of variables with maximum absolute value in autocorrelation spectra<2^n/2[J]. Information Sciences, 2021,575: 437-453.
[6]	CARLET C , FENG K Q . An infinite class of balanced functions with optimal algebraic immunity,good immunity to fast algebraic attacks and good nonlinearity[C]// 2008 International Conference on the Theory and Application of Cryptology and Information Security. Berlin:Springer, 2008: 425-440.
[7]	TU Z R , DENG Y P . A conjecture about binary strings and its applications on constructing Boolean functions with optimal algebraic immunity[J]. Designs,Codes and Cryptography, 2011,60(1): 1-14.
[8]	TU Z R , DENG Y P . Boolean functions optimizing most of the cryptographic criteria[J]. Discrete Applied Mathematics, 2012,160(4/5): 427-435.
[9]	ZHANG W G , PASALIC E . Improving the lower bound on the maximum nonlinearity of 1-resilient Boolean functions and designing functions satisfying all cryptographic criteria[J]. Information Sciences, 2017,376: 21-30.
[10]	SABER Z , UDDIN M F , YOUSSEF A . On the existence of (9,3,5,240) resilient functions[J]. IEEE Transactions on Information Theory, 2006,52(5): 2269-2270.
[11]	LIU W M , YOUSSEF A . On the existence of (10,2,7,488) resilient functions[J]. IEEE Transactions on Information Theory, 2009,55(1): 411-412.
[12]	YANG J P , ZHANG W G . Generating highly nonlinear resilient Boolean functions resistance against algebraic and fast algebraic attacks[J]. Security and Communication Networks, 2015,8(7): 1256-1264.
[13]	贾少帅, 张凤荣 . 基于引力搜索的布尔函数生成算法[J]. 计算机应用研究, 2021,38(2): 430-434.
	JIA S S , ZHANG F R . Boolean function generation algorithm based on gravitational search algorithm[J]. Application Research of Computers, 2021,38(2): 430-434.
[14]	CLARK J A , JACOB J L . Two-stage optimisation in the design of Boolean functions[C]// 2000 Australasian Conference on Information Security and Privacy. Berlin:Springer, 2000: 242-254.
[15]	李超, 胡朋松, 海昕 . 布尔函数设计中的爬山算法及其改进[J]. 通信学报, 2007,28(3): 130-133.
	LI C , HU P S , HAI X . Improved hill-climbing methods in the design of Boolean function[J]. Journal on Communications, 2007,28(3): 130-133.
[16]	BEHERA P K , GANGOPADHYAY S . An improved hybrid genetic algorithm to construct balanced Boolean function with optimal cryptographic properties[J]. Evolutionary Intelligence, 2022,15(1): 639-653.
[17]	JAKOBOVIC D , PICEK S , MARTINS M S R ,et al. Toward more efficient heuristic construction of Boolean functions[J]. Applied Soft Computing, 2021,107:107327.
[18]	CARLET C , JAKOBOVIC D , PICEK S . Evolutionary algorithms-assisted construction of cryptographic Boolean functions[C]// Proceedings of the Genetic and Evolutionary Computation Conference.[S.l.:s.n.], 2021: 565-573.
[19]	MACWILLIAMS F J , SLOANE N J A . The theory of error correcting codes[M]. Amsterdam: Elsevier, 1977.
[20]	XIAO G Z , MASSEY J L . A spectral characterization of correlation-immune combining functions[J]. IEEE Transactions on Information Theory, 1988,34(3): 569-571.
[21]	SIEGENTHALER T . Correlation-immunity of nonlinear combining functions for cryptographic applications[J]. IEEE Transactions on Information Theory, 1984,30(5): 776-780.
[22]	ZHANG X M , ZHENG Y L . GAC-the criterion for global avalanche characteristics of cryptographic functions[J]. Journal of Universal Computer Science, 1995,1(5): 316-333.
[23]	CARLET C . Partially-bent functions[J]. Designs,Codes and Cryptography, 1993,3(2): 135-145.
[24]	COURTOIS N T , . Algebraic attacks on combiners with memory and several outputs[C]// 2004 International Conference on Information Security and Cryptology. Berlin:Springer, 2004: 3-20.
[25]	MEIER W , PASALIC E , CARLET C . Algebraic attacks and decomposition of Boolean functions[C]// 2004 International Conference on the Theory and Applications of Cryptographic Techniques. Berlin:Springer, 2004: 474-491.
[26]	COURTOIS N T , . Fast algebraic attacks on stream ciphers with linear feedback[C]// 2003 Annual International Cryptology Conference. Berlin:Springer, 2003: 176-194.
[27]	GLOVER F . Future paths for integer programming and links to artificial intelligence[J]. Computers ＆ Operations Research, 1986,13(5): 533-549.
[28]	GLOVER F . Tabu search—part I[J]. ORSA Journal on Computing, 1989,1(3): 190-206.
[29]	GLOVER F . Tabu search—part II[J]. ORSA Journal on Computing, 1990,2(1): 4-32.
[30]	GLOVER F . Tabu search:a tutorial[J]. Interfaces, 1990,20(4): 74-94.
[31]	MAITRA S , PASALIC E . Further constructions of resilient Boolean functions with very high nonlinearity[C]// Proceedings of Sequences and Their Applications. Berlin:Springer, 2002: 265-280.
[32]	CARLET C . On a weakness of the Tu-Deng function and its repair[R]. Cryptology ePrint Archive, 2009.

Metrics

Recommended 0

No Suggested Reading articles found!

n	K
8	8.6
9	9.8
10	10.7
11	11.7
12	12.6
13	13.7
14	14.6

n		运行时间/s
n	改进前		改进后
8	2.41		1.66
9	3.51		2.52
10	10.28		6.14
11	28.39		12.58
12	176.42		40.36
13	556.82		126.62
14	1 864.96		415.16

Hybrid tabu search algorithm for excellent Boolean function

RichHTML

PDF

Knowledge

Abstract

Cite this article

share this article

Figures/Tables 6

References 32

Related Articles 15

Metrics

Recommended 0

n	num_cs	len_tabu
8	500	8
9	1 000	15
10	2 000	30
11	3 100	47
12	4 300	65
13	5 600	84
14	7 000	105

[1]	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.
[2]	GHao HUAN,Hua QIAN,Sai-jie YAO,Xiu-mei YANG. Coordinate transformation based coefficients estimation algorithm for digital predistortion of RF power amplifiers [J]. Journal on Communications, 2015, 36(1): 75-83.
[3]	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.
[4]	Hong-bo YUAN,Xiao-yuan YANG,Li-xian WEI,Long-fei LIU. Description of global avalanche characteristics and constructions of Boolean functions [J]. Journal on Communications, 2014, 35(Z2): 251-255.
[5]	. Description of global avalanche characteristics and constructions of Boolean functions [J]. Journal on Communications, 2014, 35(Z2): 35-255.
[6]	. Extended algebraic immunity of symmetric Boolean function [J]. Journal on Communications, 2014, 35(Z2): 24-183.
[7]	Wei-wei LI. Correlation-immunity study of balanced H-Boolean functions [J]. Journal on Communications, 2013, 34(8): 82-87.
[8]	. Correlation-immunity study of balanced H-Boolean functions [J]. Journal on Communications, 2013, 34(8): 11-87.
[9]	Jiao DU,Qiao-yan WEN,Jie ZHANG,Shan-qi PANG. Construction and count of resilient rotation symmetric Boolean functions with prime number variables [J]. Journal on Communications, 2013, 34(3): 6-13.
[10]	Ya-qun ZHAO,Xu LI. Two open problems about the liner structure of rotation symmetric Boolean functions [J]. Journal on Communications, 2013, 34(3): 171-174.
[11]	Zhi-hui OU,Ya-qun ZHAO. On one class of symmetric Boolean functions [J]. Journal on Communications, 2013, 34(1): 90-95.
[12]	Jing-lian HUANG,Zhuo WANG. Relationship between correlation immune and weight of H Boolean functions [J]. Journal on Communications, 2012, 33(2): 110-118.
[13]	Hai-xin SONG,Xiu-bin FAN,Chuan-kun WU,Deng-guo FENG. Analysis of the success probability of cube attack [J]. Journal on Communications, 2012, 33(10): 143-148.
[14]	Quan LI,Guang-pu GAO,Wen-fen LIU. Analysis of properties and counting of orbits for k-rotation symmetric Boolean functions [J]. Journal on Communications, 2012, 33(1): 114-119.
[15]	Chuan-lun REN,Feng-mei LIU,Zhong-xian LI,Xin-xin NIU,Yi-xian YANG. Some results about negabent functions [J]. Journal on Communications, 2011, 32(8): 179-182.