Computer Science

Computer Science ›› 2025, Vol. 52 ›› Issue (12): 351-357.doi: 10.11896/jsjkx.241200039

• Information Security • Previous Articles     Next Articles

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 Online:2025-12-15 Published: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)

7

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

CLC Number: 

  • 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.
[1] WU Wan-qing, ZHOU Guo-long and MA Xiao-xue. Construction of Boolean Permutation Based on Derivative of Boolean Function [J]. Computer Science, 2020, 47(6A): 349-351.
[2] LI Hao-jun, DU Zhao-hong and QIU Fei-yue. Optimized Research for Task-driven Grouping Based on Hybrid Genetic Algorithm [J]. Computer Science, 2017, 44(Z6): 105-108.
[3] HUANG Jing-lian, WANG Zhuo and LI Juan. H Boolean Functions with Divided into Two Parts and High Nonlinearity Boolean Functions [J]. Computer Science, 2016, 43(7): 166-170.
[4] RONG Li-xia. Sub-period Considering Vehicle Scheduling Problem with Uncertain Demands [J]. Computer Science, 2014, 41(8): 274-277.
[5] ZHANG Zhe-lin and ZHOU Meng. Construction of MAI Function Based on T-D Conjecture [J]. Computer Science, 2013, 40(11): 94-97.
[6] ZHOU Yu XIAO Guo-zhen （ Institute of Information Security, National Key Laboratory of ISN, Xidian University, Xi ＇ an 710071, China）. [J]. Computer Science, 2009, 36(6): 82-84.
[7] . [J]. Computer Science, 2007, 34(1): 103-105.
[8] . [J]. Computer Science, 2005, 32(10): 68-70.
Viewed
Full text


Abstract

Cited
  Shared   
  Discussed   
No Suggested Reading articles found!
渝ICP备16013121号-4
Add:18# Honghu West Rd., Yubei ,Chongqing,China    Post Code: 401121
Tel: 023-63500828/023-67039612/023-67039623
E-mail: jsjkx12@163.com
Powered by Beijing Magtech Co., Ltd.