IGA: An Improved Genetic Algorithm to Construct Weightwise (Almost) Perfectly Balanced Boolean Functions with High Weightwise Nonlinearity

Lili Yan, Jingyi Cui, Jian Liu, Guangquan Xu, Lidong Han, Alireza Jolfaei, Xi Zheng

Research output: Chapter in Book/Report/Conference proceedingConference contributionpeer-review

3 Citations (Scopus)

Abstract

The Boolean functions satisfying secure properties on the restricted sets of inputs are studied recently due to their importance in the framework of the FLIP stream cipher. However, finding Boolean functions with optimal cryptographic properties is an open research problem in the cryptographic community. This paper presents an Improved Genetic Algorithm (IGA) with the directed changes that keep the weightwise balancedness of Boolean functions. A cross-protection strategy is proposed to ensure that the offspring has the same weightwise balancedness characteristics of the parents while implementing crossover. Then, a large number of weightwise (almost) perfectly balanced (W(A)PB) functions with a good nonlinearity profile are obtained based on IGA. Finally, we make comparisons between our constructions and relevant works. The comparisons show that IGA has a significant advantage for reaching the W(A)PB functions with high weightwise nonlinearity. Moreover, it is the first time to obtain the 8-variable WPB functions with the weightwise nonlinearity of 28 in the restricted sets of inputs with Hamming weight of 4, and list the statistical indicators of the weightwise nonlinearity for W(A)PB functions for input size n = 9, 10.

Original languageEnglish
Title of host publicationASIA CCS 2023 - Proceedings of the 2023 ACM Asia Conference on Computer and Communications Security
PublisherAssociation for Computing Machinery
Pages638-648
Number of pages11
ISBN (Electronic)9798400700989
DOIs
Publication statusPublished - Jul 2023
Event18th ACM ASIA Conference on Computer and Communications Security, ASIA CCS 2023 - Melbourne, Australia
Duration: 10 Jul 202314 Jul 2023

Publication series

NameProceedings of the ACM Conference on Computer and Communications Security
ISSN (Print)1543-7221

Conference

Conference18th ACM ASIA Conference on Computer and Communications Security, ASIA CCS 2023
Country/TerritoryAustralia
CityMelbourne
Period10/07/2314/07/23

Keywords

  • Boolean function
  • Genetic algorithm
  • Nonlinearity
  • Weightwise (almost) perfectly balancedness

Fingerprint

Dive into the research topics of 'IGA: An Improved Genetic Algorithm to Construct Weightwise (Almost) Perfectly Balanced Boolean Functions with High Weightwise Nonlinearity'. Together they form a unique fingerprint.

Cite this