JOURNAL OF SHANDONG UNIVERSITY(NATURAL SCIENCE) ›› 2022, Vol. 57 ›› Issue (5): 74-84.doi: 10.6040/j.issn.1671-9352.2.2021.007

Previous Articles    

Research of balanced Boolean functions with high nonlinearity based on GSA

WU Wan-qing, ZHOU Guo-long*, WANG Qiao, ZHAO Yong-xin   

  1. School of Cyber Security and Computer, Hebei University, Baoding 071000, Hebei, China
  • Published:2022-05-27

PDF (PC)

191

Abstract: A two-stage Boolean function search algorithm is proposed, the first stage is based on the Gravitational Search Algorithm, using a floating-point coding rule, which specifies the conversion between the truth table and the floating-point vector, and set the appropriate cost function, the rules of the force between the particles and the movement rules. The second stage is called local traversal, which improves the nonlinearity of Boolean functions. Simulating experiments show that our algorithm can gain a large number of balanced 6-9 variables Boolean functions with high nonlinearity and low autocorrelation, among them with optimal or sub-optimal autocorrelation.

Key words: Boolean function, nonlinearity, heuristic algorithm, gravitational search algorithm

CLC Number: 

  • TP399
[1] MILLAN W, CLARK A. Smart hill climbing finds better Boolean functions[J]. Proceedings of the Workshop on Selected Areas on Cryptography SAC 97, 1997: 50-63.
[2] MILLAN W, CLARK A, DAWSON E. Boolean function design using hill climbing methods[C] //Information Security and Privacy, 4th Australasian Conference, ACISP'99. Wollongong:[s.n.] , 1999, 1587: 1-11.
[3] MILLAN W, FULLER J, DAWSON E. New concepts in evolutionary search for Boolean functions in cryptology[J]. Computational Intelligence, 2004, 20(3):463-474.
[4] MILLAN W, CLARK A, DAWSON E. An effective genetic algorithm for finding highly nonlinear Boolean functions[C] // Proceedings of the First International Conference on Information and Communication Security(ICICS '97). Beijing: [s.n.] 1997: 149-158.
[5] MILLAN W, CLARK A, DAWSON E. Heuristic design of cryptographically strong balanced Boolean functions[C] //EUROCRYPT 98, LNCS 1403. Berlin: Springer, 1998: 489-499.
[6] CLARK A, JACOB L. Two-stage optimisation in the design of Boolean functions[C] //Information Security and Privacy(ACISP 2000). Berlin: Springer, 2000: 242-254.
[7] CLARK A, JACOB L, STEPNEY S, et al. Evolving Boolean functions satisfying multiple criteria[C] //Progress in Cryptology-INDOCRYPT 2002. Berlin: Springer, 2002, 2551:246-259.
[8] MCLAUGHLIN J, CLARK A. Using evolutionary computation to create vectorial Boolean functions with low differential uniformity and high nonlinearity[J]. Computer Science, 2013, 29:1-19;
[9] PICEK S, JAKOBOVIC D, GOLUB M. Evolving cryptographically sound Boolean functions[C] //Proceedings of the 2013 Genetic and Evolutionary Computation Conference Companion. Berlin: Springer, 2013: 191-192.
[10] PICEK S, MARCHIORI E, BATINA L, et al. Combining evolutionary computation and algebraic constructions to find cryptography-relevant Boolean functions[M] //Parallel Problem Solving from Nature. Cham: Springer, 2014, 8672:822-831.
[11] PICEK S, JAKOBOVIC D, MILLER F, et al. Evolutionary methods for the construction of cryptographic Boolean functions[C] //Genetic Programming, EuroGP 2015. Cham: Springer, 2015, 9025.
[12] YANG Junpo, ZHANG Weiguo. Generating highly nonlinear resilient Boolean functions resistance against algebraic and fast algebraic attacks[J]. Security & Communication Networks, 2015, 8(7):1256-1264.
[13] MARIOT L, LEPORATI A. Heuristic search by particle swarm optimization of Boolean functions for cryptographic applications[C] //Proceedings of the companion publication of the 2015 annual conference on genetic and evolutionary computation. Berlin: Springer, 2015: 1425-1426.
[14] 贾少帅, 张凤荣. 基于引力搜索的布尔函数生成算法[J]. 计算机应用研究, 2020, 38(2):430-434. JIA Shaoshuai, ZHANG Fengrong. Boolean function generation algorithm based on gravitational search algorithm[J]. Application Research of Computers, 2020, 38(2):430-434.
[15] 张思瑶.基于改进模拟退火的布尔函数生成算法[J]. 网络安全技术与应用, 2021(7):47-49. ZHANG Siyao. Boolean functions generation algorithm based on improved simulated annealing[J]. Network Security Technology & Application, 2021(7):47-49.
[16] BEHERAP, GANGOPADHYAY S. Analysis of cost function using genetic algorithm to construct balanced Boolean function[C] //TENCON 2018—2018 IEEE Region 10 Conference. [S.l.] : IEEE, 2018: 1445-1450.
[17] BEHERA P, GANGOPADHYAY S. An improved hybrid genetic algorithm to construct balanced Boolean function with optimal cryptographic properties[J]. Evolutionary Intelligence, 2021(1):1-15.
[18] MANZONI L, MARIOT L, TUBA E. Does constraining the search space of GA always help?: the case of balanced crossover operators[C] //Proceedings of the Genetic and Evolutionary Computation Conference Companion-GECCO'19, Berlin: Springer, 2019: 151-152.
[19] MANZONI L, MARIOT L, TUBA E. Balanced crossover operators in genetic algorithms[J]. Neural and Evolutionary Computing, 2019: 1-26.
[20] RASHEDI E, NEZAMABADI-POUR H, SARYAZDI S. GSA: a gravitational search algorithm[J]. Information Sciences, 2009, 179(13):2232-2248.
[21] PICEK S, ŠIŠEJKOVIC D, JAKOBOVIC D. Immunological algorithms paradigm for construction of Boolean functions with good cryptographic properties[J]. Engineering Applications of Artificial Intelligence, 2017, 62:320-330.
[22] ZHANG Xianmo, ZHENG Yuliang. GAC-the criterion for global avalanche characteristics of cryptographic functions[J]. Journal of Universal Computer Science, 1997, 1(5):316-333.
[23] BURNETT L, CLARK A, DAWSON E, et al. Simpler methods for generating better Boolean functions with good cryptographic properties[J]. Australasian Journal of Combinatorics, 2004, 29:231-247.
[24] CLARK A, JACOB L, STEPNEY S. Searching for cost functions[C] //Proceedings of the 2004 Congress on Evolutionary Computation. Berlin: Springer, 2004, 2:1517-1524.
[25] HERNÁN A, HIROYUKI O, YASUSHI F. An evolutionary multiobjective approach to design highly non-linear Boolean functions[C] // Proceedings of the 9th Annual Conference on Genetic and Evolutionary Computation. Berlin: Springer, 2007: 749-756.
[1] OUYANG Bai-ping, XIAO Sheng-zhong. Global nonexistence of solutions to a class of semilinear double-wave equations with space-dependent coefficients on the nonlinearity [J]. JOURNAL OF SHANDONG UNIVERSITY(NATURAL SCIENCE), 2021, 56(9): 59-65.
[2] ZHUO Ze-peng, CHONG Jin-feng, WEI Shi-min. Constructions of bent-negabent Boolean functions [J]. JOURNAL OF SHANDONG UNIVERSITY(NATURAL SCIENCE), 2015, 50(10): 47-51.
[3] YUAN Hong-bo, YANG Xiao-yuan, WEI Yue-chuan, LIU Long-fei, FAN Cun-yang. Matrix description and properties of global avalanche characteristics [J]. JOURNAL OF SHANDONG UNIVERSITY(NATURAL SCIENCE), 2014, 49(11): 89-94.
[4] ZHUO Ze-peng, CHONG Jin-feng, WEI Shi-min. On Nega-Hadamard transform and negabent functions [J]. J4, 2013, 48(7): 29-32.
[5] ZHANG Shen-gui. Multiplicity of periodic solution of a class of non-automous second order system [J]. J4, 2011, 46(11): 64-69.
[6] LI Ya-nan1, LIU Lei-po2, WANG Yu-guang3. Passive sliding mode control for uncertain time-delay systems subjected to input nonlinearity [J]. J4, 2010, 45(6): 99-104.
[7] FU Li. Basic properties of uniform logic formulas and  distribution of their truth degrees [J]. J4, 2010, 45(11): 59-62.
[8] ZHANG Jia-Cheng, TUN Bao-Wei. Mixed type guaranteed cost controller design for neutral systems with nonlinearity [J]. J4, 2009, 44(10): 67-74.
[9] ZHANG Wei and JU Pei-jun . Design of observers for nonlinear Lipschitz descriptor systems with unknown inputs [J]. J4, 2006, 41(2): 85-88 .
[10] ZHAO Pei-xin,MA Jian-hua and WANG Hong, . Lagrange relaxation heuristic algorithm for stochastic loader problem [J]. J4, 2006, 41(1): 106-110 .
Viewed
Full text


Abstract

Cited
  Shared   
  Discussed   
No Suggested Reading articles found!
Copyright 2018 © Editorial office of JOURNAL OF SHANDONG UNIVERSITY(NATURAL SCIENCE)
Supported by Beijing Magtech Co.Ltd