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

doi:10.6040/j.issn.1671-9352.2.2021.007

摘要/Abstract

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

吴万青,周国龙,王巧,赵永新. 基于GSA搜索高非线性度的平衡布尔函数[J]. 《山东大学学报(理学版)》, 2022, 57(5): 74-84.

WU Wan-qing, ZHOU Guo-long, WANG Qiao, ZHAO Yong-xin. Research of balanced Boolean functions with high nonlinearity based on GSA[J]. JOURNAL OF SHANDONG UNIVERSITY(NATURAL SCIENCE), 2022, 57(5): 74-84.

参考文献

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

相关文章 15

[1]	欧阳柏平,肖胜中. 一类具有空变系数的非线性项的半线性双波动方程解的全局非存在性[J]. 《山东大学学报(理学版)》, 2021, 56(9): 59-65.
[2]	杜亚利,汪璇. 带非线性阻尼的非自治Berger方程的时间依赖拉回吸引子[J]. 《山东大学学报(理学版)》, 2021, 56(6): 30-41.
[3]	李远飞,李丹丹,陈雪姣,石金诚. 一类拟线性瞬态抛物方程组的空间二择性[J]. 《山东大学学报(理学版)》, 2021, 56(6): 1-9.
[4]	刘梦雪, 李杰梅, 姚燕燕. 带有非线性边界条件的四阶边值问题的多解性[J]. 《山东大学学报(理学版)》, 2021, 56(2): 84-91.
[5]	马维凤,陈鹏玉. 状态依赖型时滞微分方程的解流形及其C¹-光滑性[J]. 《山东大学学报(理学版)》, 2021, 56(2): 92-96.
[6]	苏肖肖, 张亚莉. 带阻尼项的二阶差分方程周期边值问题正解的存在性[J]. 《山东大学学报(理学版)》, 2021, 56(2): 56-63.
[7]	唐益明,张征,芦启明. 分段二次方转换函数驱动的高斯核模糊C均值聚类[J]. 《山东大学学报(理学版)》, 2020, 55(3): 107-112.
[8]	张如,韩旭,刘小刚. 非线性延迟微分方程边值方法的收敛性和收缩性[J]. 《山东大学学报(理学版)》, 2019, 54(8): 97-101.
[9]	李娟. 晶体相场方程的线性化Crank-Nicolson格式的误差分析[J]. 《山东大学学报(理学版)》, 2019, 54(6): 118-126.
[10]	王凌霜,黄志刚. 非线性微分方程解的唯一性[J]. 《山东大学学报(理学版)》, 2019, 54(12): 106-114.
[11]	苏肖肖. 一类奇异二阶阻尼差分方程周期边值问题正解的存在性[J]. 《山东大学学报(理学版)》, 2019, 54(12): 38-45.
[12]	王非,杨亚莉,金英姬,曹书苗. 具有两个感染阶段和治疗及非线性发生率的HIV/AIDS模型的研究[J]. 《山东大学学报(理学版)》, 2019, 54(10): 67-73.
[13]	刘园园,曹德欣,秦军. 非线性二层混合整数规划问题的区间算法[J]. 山东大学学报（理学版）, 2018, 53(2): 9-17.
[14]	李会会,刘希强,辛祥鹏. 变系数Benjamin-Bona-Mahony-Burgers方程的微分不变量和精确解[J]. 山东大学学报（理学版）, 2018, 53(10): 51-60.
[15]	崔建斌,姬安召,鲁洪江,王玉风,何姜毅,许泰. Schwarz Christoffel变换数值解法[J]. 山东大学学报（理学版）, 2016, 51(4): 104-111.

多维度评价

Viewed

Full text

Abstract

Cited

Shared

Discussed