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

doi:10.1145/3579856.3590337

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

College of Science and Engineering

Research output: Chapter in Book/Report/Conference proceeding › Conference contribution › peer-review

4 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 language	English
Title of host publication	ASIA CCS 2023 - Proceedings of the 2023 ACM Asia Conference on Computer and Communications Security
Publisher	Association for Computing Machinery
Pages	638-648
Number of pages	11
ISBN (Electronic)	9798400700989
DOIs	https://doi.org/10.1145/3579856.3590337
Publication status	Published - Jul 2023
Event	18th ACM ASIA Conference on Computer and Communications Security, ASIA CCS 2023 - Melbourne, Australia Duration: 10 Jul 2023 → 14 Jul 2023

Publication series

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

Conference

Conference	18th ACM ASIA Conference on Computer and Communications Security, ASIA CCS 2023
Country/Territory	Australia
City	Melbourne
Period	10/07/23 → 14/07/23

Keywords

Boolean function
Genetic algorithm
Nonlinearity
Weightwise (almost) perfectly balancedness

Access to Document

10.1145/3579856.3590337Licence: In Copyright

Cite this

Yan, L., Cui, J., Liu, J., Xu, G., Han, L., Jolfaei, A., & Zheng, X. (2023). IGA: An Improved Genetic Algorithm to Construct Weightwise (Almost) Perfectly Balanced Boolean Functions with High Weightwise Nonlinearity. In ASIA CCS 2023 - Proceedings of the 2023 ACM Asia Conference on Computer and Communications Security (pp. 638-648). (Proceedings of the ACM Conference on Computer and Communications Security). Association for Computing Machinery. https://doi.org/10.1145/3579856.3590337

Yan, Lili ; Cui, Jingyi ; Liu, Jian et al. / IGA : An Improved Genetic Algorithm to Construct Weightwise (Almost) Perfectly Balanced Boolean Functions with High Weightwise Nonlinearity. ASIA CCS 2023 - Proceedings of the 2023 ACM Asia Conference on Computer and Communications Security. Association for Computing Machinery, 2023. pp. 638-648 (Proceedings of the ACM Conference on Computer and Communications Security).

@inproceedings{9a7a9cb754c84695b1a8c56946977306,

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

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.",

keywords = "Boolean function, Genetic algorithm, Nonlinearity, Weightwise (almost) perfectly balancedness",

author = "Lili Yan and Jingyi Cui and Jian Liu and Guangquan Xu and Lidong Han and Alireza Jolfaei and Xi Zheng",

year = "2023",

month = jul,

doi = "10.1145/3579856.3590337",

language = "English",

series = "Proceedings of the ACM Conference on Computer and Communications Security",

publisher = "Association for Computing Machinery",

pages = "638--648",

booktitle = "ASIA CCS 2023 - Proceedings of the 2023 ACM Asia Conference on Computer and Communications Security",

note = "18th ACM ASIA Conference on Computer and Communications Security, ASIA CCS 2023 ; Conference date: 10-07-2023 Through 14-07-2023",

}

Yan, L, Cui, J, Liu, J, Xu, G, Han, L, Jolfaei, A & Zheng, X 2023, IGA: An Improved Genetic Algorithm to Construct Weightwise (Almost) Perfectly Balanced Boolean Functions with High Weightwise Nonlinearity. in ASIA CCS 2023 - Proceedings of the 2023 ACM Asia Conference on Computer and Communications Security. Proceedings of the ACM Conference on Computer and Communications Security, Association for Computing Machinery, pp. 638-648, 18th ACM ASIA Conference on Computer and Communications Security, ASIA CCS 2023, Melbourne, Australia, 10/07/23. https://doi.org/10.1145/3579856.3590337

IGA: An Improved Genetic Algorithm to Construct Weightwise (Almost) Perfectly Balanced Boolean Functions with High Weightwise Nonlinearity. / Yan, Lili; Cui, Jingyi; Liu, Jian et al.
ASIA CCS 2023 - Proceedings of the 2023 ACM Asia Conference on Computer and Communications Security. Association for Computing Machinery, 2023. p. 638-648 (Proceedings of the ACM Conference on Computer and Communications Security).

Research output: Chapter in Book/Report/Conference proceeding › Conference contribution › peer-review

TY - GEN

T1 - IGA

T2 - 18th ACM ASIA Conference on Computer and Communications Security, ASIA CCS 2023

AU - Yan, Lili

AU - Cui, Jingyi

AU - Liu, Jian

AU - Xu, Guangquan

AU - Han, Lidong

AU - Jolfaei, Alireza

AU - Zheng, Xi

PY - 2023/7

Y1 - 2023/7

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

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

KW - Boolean function

KW - Genetic algorithm

KW - Nonlinearity

KW - Weightwise (almost) perfectly balancedness

UR - http://www.scopus.com/inward/record.url?scp=85168099723&partnerID=8YFLogxK

U2 - 10.1145/3579856.3590337

DO - 10.1145/3579856.3590337

M3 - Conference contribution

AN - SCOPUS:85168099723

T3 - Proceedings of the ACM Conference on Computer and Communications Security

SP - 638

EP - 648

BT - ASIA CCS 2023 - Proceedings of the 2023 ACM Asia Conference on Computer and Communications Security

PB - Association for Computing Machinery

Y2 - 10 July 2023 through 14 July 2023

ER -

Yan L, Cui J, Liu J, Xu G, Han L, Jolfaei A et al. IGA: An Improved Genetic Algorithm to Construct Weightwise (Almost) Perfectly Balanced Boolean Functions with High Weightwise Nonlinearity. In ASIA CCS 2023 - Proceedings of the 2023 ACM Asia Conference on Computer and Communications Security. Association for Computing Machinery. 2023. p. 638-648. (Proceedings of the ACM Conference on Computer and Communications Security). doi: 10.1145/3579856.3590337

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

Abstract

Publication series

Conference

Keywords

Access to Document

Other files and links

Fingerprint

Cite this