A class of weightwise almost perfectly balanced Boolean functions

Deepak Kumar Dalai; Krishna Mallick

doi:10.3934/amc.2023048

Article Contents

2024, Volume 18, Issue 2: 480-504. Doi: 10.3934/amc.2023048

This issue Previous Article On recursive constructions of $ \mathbb{Z}_2 \mathbb{Z}_4 \mathbb{Z}_8 $-linear Hadamard codes Next Article Lengths of divisible codes with restricted column multiplicities

A class of weightwise almost perfectly balanced Boolean functions

Deepak Kumar Dalai^1, , and
Krishna Mallick^1,

1.
National Institute of Science Education and Research, An OCC of Homi Bhabha National Institute, Bhubaneswar, Odisha 752050, India

^*Corresponding author: Deepak Kumar Dalai
^*Corresponding author: Deepak Kumar Dalai

Received: April 2023

Revised: November 2023

Early access: November 2023

Published: April 2024

Abstract / Introduction Full Text(HTML) Figure(0) / Table(6) Related Papers Cited by

Abstract

Constructing Boolean functions with good cryptographic properties over a subset of vectors with fixed Hamming weight $ E_{n,k} \subset {{\rm{I\!F}}}_2^n $ is significant in lightweight stream ciphers like FLIP [14]. In this article, we have given a construction for a class of $ n $-variable weightwise almost perfectly balanced (WAPB) Boolean functions from known support of an $ n_0 $-variable WAPB Boolean function where $ n_0 < n $. This is a generalization of constructing a weightwise perfectly balanced (WPB) Boolean function by Mesnager and Su [16]. We have studied some cryptographic properties like ANF, nonlinearity, weightwise nonlinearities, and algebraic immunity of the functions. The ANF of this function is obtained recursively, which would be a low-cost implementation in a lightweight stream cipher. Further, we have presented another class of WAPB Boolean functions by modifying the earlier function, and we studied some of its cryptographic properties. The nonlinearity and weightwise nonlinearities of the modified functions improve substantially.

Keywords:

Boolean function,
FLIP cipher,
weightwise perfectly balanced (WPB),
weightwise almost perfectly balanced (WAPB).

Mathematics Subject Classification: Primary: 94A60, 94D10, 06E30; Secondary: 68P25.

Citation:

Full Text(HTML)

Table 1. Listing of $\mathtt{nl}(f_n),\mathtt{nl}_k(f_n), \mathtt{GWNL}(f_n)$ for $9 \leq n \leq 15$

n	$ \mathtt{nl}$	$ \mathtt{nl}_2 $	$ \mathtt{nl}_3 $	$ \mathtt{nl}_4 $	$ \mathtt{nl}_5 $	$ \mathtt{nl}_6 $	$ \mathtt{nl}_7 $	$ \mathtt{nl}_8 $	$ \mathtt{nl}_9 $	$ \mathtt{nl}_{10} $	$ \mathtt{nl}_{11} $	$ \mathtt{nl}_{12} $	$ \mathtt{nl}_{13} $	$ \mathtt{nl}_{14} $	$ \mathtt{GWNL} $
8	8	2	0	3	0	2	0	0	0	-	-	-	-	-	7
9	16	2	2	3	3	2	2	0	0	-	-	-	-	-	16
10	16	3	0	5	0	5	0	3	0	0	-	-	-	-	16
11	32	3	3	5	5	5	5	3	3	0	0	-	-	-	32
12	32	3	0	7	0	10	0	8	0	3	0	0	-	-	31
13	64	3	3	7	7	10	10	8	8	3	3	0	0	-	62
14	64	4	0	10	0	18	0	18	0	10	0	4	0	-	64
15	128	4	4	10	10	18	18	18	18	10	10	4	4	0	128
16	128	4	0	14	0	28	0	35	0	14	0	4	0	28	127

| Show Table

DownLoad: CSV

Table 2. Listing of $ \mathtt{nl}(F_n), \mathtt{nl}_k(F_n), \mathtt{GWNL}(F_n) $ for $ 9 \leq n \leq 16 $

n	$ \mathtt{nl} $	$ \mathtt{nl}_2 $	$ \mathtt{nl}_3 $	$ \mathtt{nl}_4 $	$ \mathtt{nl}_5 $	$ \mathtt{nl}_6 $	$ \mathtt{nl}_7 $	$ \mathtt{nl}_8 $	$ \mathtt{nl}_9 $	$ \mathtt{nl}_{10} $	$ \mathtt{nl}_{11} $	$ \mathtt{nl}_{12} $	$ \mathtt{nl}_{13} $	$ \mathtt{nl}_{14} $	$ \mathtt{GWNL} $
8	82	7	13	14	14	7	0	0	0	-	-	-	-	-	55
9	164	8	26	27	33	26	8	0	0	-	-	-	-	-	128
10	356	10	28	47	66	49	32	10	0	0	-	-	-	-	242
11	712	11	44	79	113	171	93	43	11	0	0	-	-	-	565
12	1504	12	45	127	234	210	244	127	50	12	0	0	-	-	1061
13	3008	13	63	177	361	582	594	371	178	79	13	0	0	-	2431
14	6112	15	66	230	635	708	1016	709	575	230	72	15	0	-	4271
15	12224	16	89	302	925	1510	2424	1725	1295	960	302	88	16	0	9652
16	24338	17	91	378	1321	2001	3485	3002	3499	1995	1363	378	126	18	17464

| Show Table

DownLoad: CSV

Table 3. Comparison of $ \mathtt{nl}_k(F_n) $ with the upper bound(UB) presented in [1]

$ n $	function	$ \mathtt{nl} $	$ \mathtt{nl}_2 $	$ \mathtt{nl}_3 $	$ \mathtt{nl}_4 $	$ \mathtt{nl}_5 $	$ \mathtt{nl}_6 $	$ \mathtt{nl}_7 $	$ \mathtt{nl}_8 $	$ \mathtt{nl}_9 $	$ \mathtt{nl}_{10} $	$ \mathtt{nl}_{11} $	$ \mathtt{GWNL} $
9	UB	244	15	37	57	57	37	15	-	-	-	-	218
9	$ F_9 $	164	8	26	27	33	26	8	-	-	-	-	128
10	UB	496	19	54	97	118	97	54	19	-	-	-	498
10	$ F_{10} $	356	10	28	47	66	49	32	10	-	-	-	128
11	UB	1000	23	76	155	220	220	155	76	23	-	-	948
11	$ F_{11} $	712	11	44	79	113	171	93	43	11	-	-	565
12	UB	2016	28	102	236	381	446	381	236	102	28	-	1940
12	$ F_{12} $	1056	12	45	127	234	210	244	127	50	12	-	1061
13	UB	4050	34	134	344	625	837	837	625	344	134	34	3948
13	$ F_{13} $	3008	13	63	177	361	582	594	371	178	79	13	2431

| Show Table

DownLoad: CSV

Table 4. Comparison of $ \mathtt{nl}_k $ of 6-variable WAPB constructions

WPB/ WAPB Boolean functions	$ \mathtt{nl}_2 $	$ \mathtt{nl}_3 $	$ \mathtt{nl}_4 $
Upper Bound [1]	5	7	5
[1]	2	4	2
[20]	2	2	2
[22,$ f_n $ Equation(8)]	1	4	1
[9]	1	4	1
$ F_n $	3	4	3

| Show Table

DownLoad: CSV

Table 5. Comparison of $ \mathtt{nl}_k $ of 7-variable WAPB constructions

WPB/WAPB Boolean functions	$ \mathtt{nl}_2 $	$ \mathtt{nl}_3 $	$ \mathtt{nl}_4 $	$ \mathtt{nl}_5 $
Upper Bound [1]	8	14	14	8
[22,$ f_n $ Equation(8)]	1	5	5	1
[9]	1	5	5	1
$ F_n $	5	11	7	5

| Show Table

DownLoad: CSV

Table 6. Comparison of $ \mathtt{nl}_k $ of 8-variable WPB constructions

WPB/ WAPB functions	$ \mathtt{nl}_2 $	$ \mathtt{nl}_3 $	$ \mathtt{nl}_4 $	$ \mathtt{nl}_5 $	$ \mathtt{nl}_6 $
Upper Bound [1]	11	24	30	24	11
[1]	2	12	19	12	6
[12]	6, 9	0, 8, 14, 16,	19, 22, 23, 24,	19, 20, 21, 22	6, 9
		18, 20, 21, 22	25, 26, 27
[11,$ g_{2^{q+2}} $ Equation(9)]	2	12	19	12	2
[16,$ f_m $ Equation(13)]	2	0	3	0	2
[16,$ g_m $ Equation(22)]	2	14	19	14	2
[17,$ f_m $ Equation(2)]	2	8	8	8	2
[17,$ f_m $ Equation(3)]	6	8	26	8	6
[5,Table 1]	5, 3, 2, 2	10, 7, 12, 12	16, 15, 18, 19	12, 11, 12, 12	5, 3, 2, 6
[5,Table 3]	5	16	20	17	5
[21,$ g_m $ Equation(11)]	2	12	19	12	6
[6]	6, 6, 7	19, 14, 15	21, 20, 18	11, 11, 14	3, 6, 6
$ F_n $	7	13	14	14	7

| Show Table

DownLoad: CSV

Related Papers

Cited by

References

[1]	C. Carlet, P. Méaux and Y. Rotella, Boolean functions with restricted input and their robustness; application to the FLIP cipher, IACR Trans. Symmetric Cryptol., 2017 (2017), 192-227. doi: 10.13154/TOSC.V2017.I3.192-227.
[2]	D. K. Dalai, K. C. Gupta and S. Maitra, Results on algebraic immunity for cryptographically significant Boolean functions, In Progress in Cryptology - INDOCRYPT 2004, 3348 (2004), 92-106. doi: 10.1007/978-3-540-30556-9_9.
[3]	S. Duval, V. Lallemand and Y. Rotella, Cryptanalysis of the FLIP family of stream ciphers, In Advances in Cryptology - CRYPTO 2016, 9814 (2016), 457-475. doi: 10.1007/978-3-662-53018-4_17.
[4]	A. Gini and P. Méaux, On the weightwise nonlinearity of weightwise perfectly balanced functions, Discrete Applied Mathematics, 322 (2022), 320-341. doi: 10.1016/J.DAM.2022.08.017.
[5]	A. Gini and P. Méaux, Weightwise almost perfectly balanced functions: Secondary constructions for all n and better weightwise nonlinearities, In Progress in Cryptology - INDOCRYPT 2022, 13774 (2022), 492-514. doi: 10.1007/978-3-031-22912-1_22.
[6]	A. Gini and P. Méaux, On the algebraic immunity of weightwise perfectly balanced functions, In Progress in Cryptology - LATINCRYPT 2023, 14168 (2023), 3-23. doi: 10.1007/978-3-031-44469-2_1.
[7]	A. Gini and P. Méaux, Weightwise perfectly balanced functions and nonlinearity, In Codes, Cryptology and Information Security - C2SI 2023, 13874 (2023), 338-359. doi: 10.1007/978-3-031-33017-9_21.
[8]	H. W. Gould, Combinatorial Identities: A Standardized Set of Tables Listing 500 Binomial Coefficient Summations, Gould, 1972.
[9]	X. Guo and S. Su, Construction of weightwise almost perfectly balanced Boolean functions on an arbitrary number of variables, Discrete Applied Mathematics, 307 (2022), 102-114. doi: 10.1016/J.DAM.2021.10.011.
[10]	X.-D. Hou, On the norm and covering radius of the first-order Reed-Muller codes, IEEE Transactions on Information Theory, 43 (1997), 1025-1027. doi: 10.1109/18.568715.
[11]	J. Li and S. Su, Construction of weightwise perfectly balanced Boolean functions with high weightwise nonlinearity, Discrete Applied Mathematics, 279 (2020), 218-227. doi: 10.1016/j.dam.2020.01.020.
[12]	J. Liu and S. Mesnager, Weightwise perfectly balanced functions with high weightwise nonlinearity profile, Designs, Codes and Cryptography, 87 (2019), 1797-1813. doi: 10.1007/S10623-018-0579-X.
[13]	É. Lucas, Sur les congruences des nombres eulériens et des coefficients différentiels des fonctions trigonométriques suivant un module premier, Bull. Soc. Math. France, 6 (1878), 49-54. doi: 10.24033/bsmf.127.
[14]	P. Méaux, A. Journault, F.-X. Standaert and C. Carlet, Towards stream ciphers for efficient FHE with low-noise ciphertexts, In Advances in Cryptology - EUROCRYPT 2016, 9665 (2016), 311-343. doi: 10.1007/978-3-662-49890-3_13.
[15]	W. Meier, E. Pasalic and C. Carlet, Algebraic attacks and decomposition of boolean functions, In Advances in Cryptology - EUROCRYPT 2004, 3027 (2004), 474-491. doi: 10.1007/978-3-540-24676-3_28.
[16]	S. Mesnager and S. Su, On constructions of weightwise perfectly balanced Boolean functions, Cryptography and Communications, 13 (2021), 951-979. doi: 10.1007/S12095-021-00481-3.
[17]	S. Mesnager, S. Su and J. Li, On concrete constructions of weightwise perfectly balanced functions with optimal algebraic immunity and high weightwise nonlinearity, In The 6th International Workshop on Boolean Functions and Applications, 2021.
[18]	S. Mesnager, Z. Zhou and C. Ding, On the nonlinearity of Boolean functions with restricted input, Cryptography and Communications, 11 (2019), 63-76. doi: 10.1007/s12095-018-0293-6.
[19]	S. Su, The lower bound of the weightwise nonlinearity profile of a class of weightwise perfectly balanced functions, Discrete Applied Mathematics, 297 (2021), 60-70. doi: 10.1016/J.DAM.2021.02.033.
[20]	D. Tang and J. Liu, A family of weightwise (almost) perfectly balanced Boolean functions with optimal algebraic immunity, Cryptography and Communications, 11 (2019), 1185-1197. doi: 10.1007/s12095-019-00374-6.
[21]	R. Zhang and S. Su, A new construction of weightwise perfectly balanced Boolean functions, Advances in Mathematics of Communications, 17 (2023), 757-770.
[22]	L. Zhu and S. Su, A systematic method of constructing weightwise almost perfectly balanced Boolean functions on an arbitrary number of variables, Discrete Applied Mathematics, 314 (2022), 181-190. doi: 10.1016/j.dam.2022.02.017.