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

^*Corresponding author for this work

School of Computing

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

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

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
Weightwise (almost) perfectly balancedness
Nonlinearity
Genetic algorithm

Access to Document

10.1145/3579856.3590337

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 '23: proceedings of the 2023 ACM Asia Conference on Computer and Communications Security (pp. 638-648). Association for Computing Machinery, Inc. https://doi.org/10.1145/3579856.3590337

@inproceedings{7357ff5be3234be7bd2e9270de0c9ba2,

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, Weightwise (almost) perfectly balancedness, Nonlinearity, Genetic algorithm",

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,

day = "10",

doi = "10.1145/3579856.3590337",

language = "English",

pages = "638--648",

booktitle = "ASIA CCS '23",

publisher = "Association for Computing Machinery, Inc",

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 '23: proceedings of the 2023 ACM Asia Conference on Computer and Communications Security. Association for Computing Machinery, Inc, New York, 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 '23: proceedings of the 2023 ACM Asia Conference on Computer and Communications Security. New York: Association for Computing Machinery, Inc, 2023. p. 638-648.

Research output: Chapter in Book/Report/Conference proceeding › Conference proceeding 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/10

Y1 - 2023/7/10

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 - Weightwise (almost) perfectly balancedness

KW - Nonlinearity

KW - Genetic algorithm

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

U2 - 10.1145/3579856.3590337

DO - 10.1145/3579856.3590337

M3 - Conference proceeding contribution

AN - SCOPUS:85168099723

SP - 638

EP - 648

BT - ASIA CCS '23

PB - Association for Computing Machinery, Inc

CY - New York

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 '23: proceedings of the 2023 ACM Asia Conference on Computer and Communications Security. New York: Association for Computing Machinery, Inc. 2023. p. 638-648 doi: 10.1145/3579856.3590337

IGA: an improved genetic algorithm to construct weightwise (almost) perfectly balanced boolean functions with high weightwise nonlinearity

Abstract

Conference

Keywords

Access to Document

Other files and links

Fingerprint

Cite this