您的位置：山东大学 -> 科技期刊社 -> 《山东大学学报（工学版）》

山东大学学报 (工学版) ›› 2022, Vol. 57 ›› Issue (5): 74-84.doi: 10.6040/j.issn.1671-9352.2.2021.007

• • 上一篇    

基于GSA搜索高非线性度的平衡布尔函数

吴万青,周国龙*,王巧,赵永新   

  1. 河北大学网络空间安全与计算机学院, 河北 保定 071000
  • 发布日期:2022-06-21
  • 作者简介:吴万青(1981— ), 男, 博士, 副教授, 硕士生导师, 研究方向为信息安全. E-mail:wuwanqing8888@126.com*通信作者简介:周国龙(1996— ), 男, 硕士研究生, 研究方向为信息安全. E-mail:glong_zhou@126.com
  • 基金资助:
    河北省高等学校科学技术研究项目(ZD202101);河北大学研究生创新资助项目(HBU2021ss058)

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)

21

摘要： 提出了一种包含两个阶段的布尔函数搜索算法,第一阶段是基于引力搜索算法,采用一种浮点编码方式,定义了真值表与浮点向量之间的转换,设置了适当目标函数、粒子之间的受力规则和运动规则。第二阶段是局部遍历,以提高布尔函数的非线性度。计算机仿真实验表明,该算法可以得到许多具有高非线性度和低自相关的6~9元平衡布尔函数,其中部分布尔函数的自相关度可达最优或次优。

关键词: 布尔函数, 非线性, 启发式算法, 引力搜索算法

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

中图分类号: 

  • 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] 程春蕊,毛北行. 一类非线性混沌系统的自适应滑模同步[J]. 山东大学学报 (工学版), 2020, 50(5): 1-6.
[2] 覃俊,李蔚栋,易金莉,刘晶,马懋德. 基于双重启发式信息求解影响最大化问题的蚁群算法[J]. 山东大学学报 (工学版), 2020, 50(3): 45-50.
[3] 刘杰,王者超,张宇鹏,孙华阳. 岩石粗糙裂隙大范围雷诺数条件下渗流特性[J]. 山东大学学报 (工学版), 2019, 49(4): 70-77, 85.
[4] 马川,刘彦呈,刘厶源,张勤进. 考虑未知死区非线性的自适应模糊神经UUV航迹跟踪控制[J]. 山东大学学报 (工学版), 2019, 49(3): 47-56.
[5] 朱晓强,钟麦英. 基于强跟踪H-/H∞优化的无人机系统故障检测[J]. 山东大学学报 (工学版), 2019, 49(1): 66-74.
[6] 周福娜,高育林,王佳瑜,文成林. 基于深度学习的缓变故障早期诊断及寿命预测[J]. 山东大学学报(工学版), 2017, 47(5): 30-37.
[7] 赵煊,钟麦英,郭丁飞. 基于等价空间的无人机飞行控制系统故障检测[J]. 山东大学学报(工学版), 2017, 47(5): 150-156.
[8] 陈杰,钟麦英,张利刚. 基于L2范数最小估计的无人机飞控系统故障检测[J]. 山东大学学报(工学版), 2017, 47(5): 89-95.
[9] 李洪阳,何潇. 基于SCKF方法的非线性随机动态系统故障诊断方法[J]. 山东大学学报(工学版), 2017, 47(5): 130-135.
[10] 李炜,王可宏,曹慧超. 基于新型ESF的一类非线性系统故障滤波方法[J]. 山东大学学报(工学版), 2017, 47(5): 7-14.
[11] 王常顺,肖海荣. 基于自抗扰控制的水面无人艇路径跟踪控制器[J]. 山东大学学报(工学版), 2016, 46(4): 54-59.
[12] 李晗,魏爱荣. 输入饱和非线性切换Hamilton系统镇定与H∞控制[J]. 山东大学学报(工学版), 2016, 46(3): 79-86.
[13] 刘金慧. 基于多目标非线性函数某深基坑参数反演分析[J]. 山东大学学报(工学版), 2015, 45(4): 75-83.
[14] 洪晓芳1,2,王玉振1*, 魏爱荣1. 一类执行器饱和非线性Hamilton网络控制系统H∞控制器设计[J]. 山东大学学报(工学版), 2014, 44(1): 49-56.
[15] 周新波1,徐向锋2*,张峰3,孙家龙3,齐广志3. 箱梁竖向预应力张拉力无损检测研究[J]. 山东大学学报(工学版), 2013, 43(6): 77-82.
Viewed
Full text


Abstract

Cited
  Shared   
  Discussed   
No Suggested Reading articles found!
版权所有 © 2018 《山东大学学报(工学版)》编辑部　
地址: 济南市山大南路27号（250100）　 电话: 0531-88366735　 E-mail: xbgxb@sdu.edu.cn
本系统由北京玛格泰克科技发展有限公司设计开发