计算机科学

计算机科学 ›› 2025, Vol. 52 ›› Issue (12): 351-357.doi: 10.11896/jsjkx.241200039

• 信息安全 • 上一篇    下一篇

优良平衡布尔函数的Rank排序混合遗传搜索算法

赵海霞1,3, 李鑫1, 韦永壮2   

  1. 1 桂林电子科技大学数学与计算科学学院 广西 桂林 541004
    2 桂林电子科技大学计算机与信息安全学院 广西 桂林 541004
    3 广西应用数学中心(GUET) 广西 桂林 541004
  • 收稿日期:2025-05-21 修回日期:2025-09-03 出版日期:2025-12-15 发布日期:2025-12-09
  • 通讯作者: 韦永壮(walker_wyz@guet.edu.cn)
  • 作者简介:(guetzhx@163.com)
  • 基金资助:
    国家自然科学基金(62402132)

Rank-sorting Hybrid Genetic Algorithm for Search High Quality Balanced Boolean Functions

ZHAO Haixia1,3, LI Xin1, WEI Yongzhuang2   

  1. 1 School of Mathematics and Computing Science, Guilin University of Electronic Technology, Guilin, Guangxi 541004, China
    2 School of Computer and Information Security, Guilin University of Electronic Technology, Guilin, Guangxi 541004, China
    3 Center for Applied Mathematics of Guangxi(GUET), Guilin, Guangxi 541004, China
  • Received:2025-05-21 Revised:2025-09-03 Published:2025-12-15 Online:2025-12-09
  • About author:ZHAO Haixia,born in 1981,Ph.D,associate professor.Her main research interests include Boolean function and design and analysis of symmetric ciphers.
    WEI Yongzhuang,born in 1976,Ph.D,professor.His main research interest is cryptographic algorithm design and analysis.
  • Supported by:
    This work was supported by the National Natural Science Foundation of China(62402132).

PDF (PC)

6

摘要： 对称密码算法通常采用安全指标良好的平衡布尔函数作为核心部件,以保障整个算法的安全性。使用启发式算法进行搜索是获得优良平衡布尔函数的一个重要途径。对此,设计了Rank排序混合遗传算法,用于搜索高非线性度、低自相关绝对值指标的平衡布尔函数。与传统的遗传算法相比,Rank排序混合遗传算法在交叉阶段设计了交叉保护策略,以保障子代的平衡性;在选择步骤,采用基于适应度函数值的精英选择策略,以防止优秀个体流失;在进入下一轮迭代之前,设计了Rank排序环节,以增大下一轮进行交叉的个体间的差异,提高生成优秀子代的可能性,降低算法陷入局部最优解的风险。实验结果表明,以6至14元的偶变元数的布尔函数为搜索对象,使用Rank排序混合遗传算法均可搜索得到非线性度严格几乎最优、自相关绝对值指标低的平衡布尔函数。

关键词: 平衡布尔函数, 混合遗传算法, 非线性度, 自相关绝对值指标

Abstract: The balanced Boolean functions with favorable security indicators are always used as core component in symmetric cipher,which can guarantee the overall security of cipher.One of important approaches to get high quality Boolean functions is searching by using heuristic algorithm.This paper designs Rank-sorting hybrid genetic algorithm to search balanced Boolean functions with high nonlinearity and low absolute autocorrelation values.Compared to traditional genetic algorithms,the following strategies and methods are designed and used in Rank-sorting hybrid genetic algorithm.Firstly,the crossover protection strategy is designed and used in the crossover phase,which can assure the balance of offspring.Secondly,elite selection strategy based on the value of fitness function is utilized in the selection step,in order to prevent the loss of excellent individuals.In particular,a sorting method named Rank-sorting algorithm is proposed and implemented on the selected offspring before they entering the next iteration,the result of using Rank-sorting algorithm is that the differences between individuals for the next crossover are increased,the possibility of generating excellent offspring is enhanced and the risk of the whole algorithm getting stuck in local optimal solutions is reduced.Experimental results show that for the Boolean functions with even number(6 to 14) of variables,ba-lanced Boolean functions with almost optimal nonlinearity and low autocorrelation can be searched by using Rank-sorting hybrid genetic algorithm.

Key words: Balanced Boolean function, Hybrid genetic algorithm, Nonlinearity, Absolute autocorrelation values

中图分类号: 

  • TP306
[1]MCFARLAND R L.A Family of Difference Sets in Non-Cyclic Groups[J].Journal of Combinatorial Theory,Series A,1973,15(1):1-10.
[2]ZHAO H,WEI Y,ZHANG F,et al.Two Secondary Constructions of Bent Functions without Initial Conditions[J].Designs,Codes and Cryptography,2022,90(3):653-679.
[3]CARLET C,FENG K.An Infinite Class of Balanced Functions with Optimal Algebraic Immunity,Good Immunity to Fast Algebraic Attacks and Good Nonlinearity[C]//Proceedings of International Conference on the Theory and Application of Cryptology and Information Security.Berlin:Springer,2008:425-440.
[4]TU Z R,DENG Y P.Boolean Functions Optimizing Most of the Cryptographic Criteria[J].Discrete Applied Mathematics,2012,160(4/5):427-435.
[5]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.
[6]MILLAN W,CLARK A,DAWSON E.Smart Hill ClimbingFinds Better Boolean Functions[EB/OL].https://api.semanticscholar.org/CorpusID:17217144.
[7]MILLAN W,CLARK A,DAWSON E.Boolean Function Design Using Hill Climbing Methods[C]//Proceedings of Information Security and Privacy:4th Australasian Conference.Berlin:Springer,1999:1-11.
[8]KUZNETSOV A,POLUYANENKO N,PELIUKH K O.ANew Cost Function for Heuristic Search of Nonlinear Substitutions[J].Expert Systems with Application,2024,237:1-14.
[9]CLARK J A,JACOB J L.Two-Stage Optimisation in the Designof Boolean Functions[C]//Proceedings of Australasian Confe-rence on Information Security and Privacy.Berlin:Springer,2000:242-254.
[10]CLARK J A,JACOB J L,STEPNEY S,et al.Evolving Boolean Functions Satisfying Multiple Criteria[C]//Proceedings of Cryptology－INDOCRYPT 2002.Berlin:Springer,2002:246-259.
[11]YANG J P,ZHANG W G.Generating Highly Nonlinear Resi-lient Boolean Functions Resistance Against Algebraic and Fast Algebraic Attacks[J].Security and Communication Networks,2015,8(7):1256-1264.
[12]MAITRA S,PASALIC E.Further Constructions of ResilientBoolean Functions with Very High Nonlinearity[M].London:Springer,2002:17-35.
[13]ASTHANA R,VERMA N,RATAN R.Generation of Boolean Functions Using Genetic Algorithm for Cryptographic Applications[C]//Proceedings of IEEE International Advance Computing Conference(IACC).New York:Piscataway,2014:1361-1366.
[14]MARIOT L,LEPORATI A,MANZONI L.A Discrete Particle Swarm Optimizer for the Design of Cryptographic Boolean Functions[J].arXiv:2401.04567,2024.
[15]MANDUJANO S,LARA A,CAUICH J K.Using Evolutionary Algorithms for the Search of 16-Variable Weight-Wise Perfectly Balanced Boolean Functions with High Non-linearity[C]//Proceedings of International Conference on Parallel Problem Solving from Nature.Berlin:Springer,2024:416-428.
[16]PICEK S,JAKOBOVIC D,GOLUB M.Evolving Cryptographically Sound Boolean Functions[C]//Proceedings of the 15th Annual Conference Companion on Genetic and Evolutionary Computation.New York:ACM,2013:191-192.
[17]PICEK S,MARCHIORI E,BATINA L,et al.Combining Evolutionary Computation and Algebraic Constructions to Find Cryptography-Relevant Boolean Functions[C]//Proceedings of Pa-rallel Problem Solving from Nature-PPSN XIII:13th Internatio-nal Conference.Berlin:Springer,2014:822-831.
[18]MANZONI L,MARIOT L,TUBA E.Does Constraining theSearch Space of Ga Always Help? The Case of Balanced Crossover Operators[C]//Proceedings of the Genetic and Evolutio-nary Computation Conference Companion.New York:ACM,2019:151-152.
[19]ZEKI E,KAVUT S,KUTUCU H.Genetic Approach to Im-prove Cryptographic Properties of Balanced Boolean Functions Using Bent Functions[J].Computers,2023,12(8):1-14.
[20]CARLET C,URASEVIC M,JAKOBOVIC D,et al.A Systematic Evaluation of Evolving Highly Nonlinear Boolean Functions in Odd Sizes[C]//Proceedings of Genetic Programming:28th European Conference.Berlin:Springer,2025:18-34.
[21]JIA S S,ZHANG F R.Boolean Function Generation Algorithm Based on Gravitational Search[J].Application Research of Computers,2021,38(2):430-434.
[22]WANG W Q,XU H J,CUI M,et al.Mixed Tabu Search Algorithm for Excellent Boolean Functions[J].Journal on Communications,2022,43(5):133-143.
[23]CARLET C.Boolean Functions for Cryptography and ErrorCorrecting Codes[C]//Boolean Models and Methods in Mathematics,Computer Science,and Engineering.Cambridge University Press,2006:257-397.
[24]ZHOU Y,HU Y P,DONG X F.Design and Analysis of Boolean Function[M]//Beijing:National Defense Industry Press,2015:20-87.
[25]CARLET C.Partially-bent Functions[J].Designs,Codes andCryptography,1993,3:135-145.
[26]HOLLAND J H.Genetic Algorithms[J].Scientific American,1992,267(1):66-73.
Viewed
Full text


Abstract

Cited
  Shared   
  Discussed   
No Suggested Reading articles found!
渝ICP备16013121号-4
地址：重庆市渝北区洪湖西路18号    邮编：401121  
电话：023-63500828（编辑部） 023-67039612（会议/专题） 023-67039623（财务/发票）
E-mail：jsjkx12@163.com
本系统由北京玛格泰克科技发展有限公司设计开发