Journal of Shandong University(Engineering 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-06-21

PDF (PC)

313

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] Jun QIN,Weidong LI,Jinli YI,Jing LIU,Maode MA. Ant colony optimization for solving maximization problem based ondouble heuristic information [J]. Journal of Shandong University(Engineering Science), 2020, 50(3): 45-50.
[2] Chuan MA,Yancheng LIU,Siyuan LIU,Qinjin ZHANG. Robust adaptive self-organizing neuro-fuzzy tracking control of UUV with unknown dead-zone nonlinearity [J]. Journal of Shandong University(Engineering Science), 2019, 49(3): 47-56.
[3] ZENG Hua1, CUI Wen2, FU Lian-ning1, WU Yao-hua1*. Heuristic construction method for the initial tour of the Lin-Kernighan algorithm [J]. JOURNAL OF SHANDONG UNIVERSITY (ENGINEERING SCIENCE), 2012, 42(2): 30-35.
[4] WU Ke-shou, CHEN Yu-ming, ZENG Zhi-qiang. Decision table reduction based on neighborhood relation [J]. JOURNAL OF SHANDONG UNIVERSITY (ENGINEERING SCIENCE), 2012, 42(2): 7-10.
[5] LI Yu-jian, MENG Dong-xia*, GUI Zhi-ming. Fast computation of characteristic boundary points for improving geometric ensembles [J]. JOURNAL OF SHANDONG UNIVERSITY (ENGINEERING SCIENCE), 2011, 41(4): 56-60.
Viewed
Full text


Abstract

Cited
  Shared   
  Discussed   
No Suggested Reading articles found!
Copyright 2018 © Editorial office of Journal of Shandong University (Engineering Science)
Supported by Beijing Magtech Co.Ltd