Weightwise perfectly balanced functions and nonlinearity

[en] In this article we realize a general study on the nonlinearity of weightwise perfectly balanced (WPB) functions. First, we derive upper and lower bounds on the nonlinearity from this class of functions for all n. Then, we give a general construction that allows us to provably provide WPB functions with nonlinearity as low as 2 n/2−1 and WPB functions with high nonlinearity, at least 2 n−1 − 2 n/2 . We provide concrete examples in 8 and 16 variables with high nonlinearity given by this construction. In 8 variables we experimentally obtain functions reaching a nonlinearity of 116 which corresponds to the upper bound of Dobbertin’s conjecture, and it improves upon the maximal nonlinearity of WPB functions recently obtained with genetic algorithms. Finally, we study the distribution of nonlinearity over the set of WPB functions. We examine the exact distribution for n = 4 and provide an algorithm to estimate the distributions for n = 8 and 16, together with the results of our experimental studies for n = 8 and 16.

Disciplines :

Computer science
Mathematics

Author, co-author :

Gini, Agnese ; University of Luxembourg > Interdisciplinary Centre for Security, Reliability and Trust (SNT) > PI Coron

Meaux, Pierrick ; University of Luxembourg > Interdisciplinary Centre for Security, Reliability and Trust (SNT) > PI Coron

External co-authors :

Language :

English

Title :

Weightwise perfectly balanced functions and nonlinearity

Publication date :

2022

Event name :

Codes, Cryptology and Information Security: 4th International Conference

Event place :

Rabat, Morocco

Event date :

from 29-05-2023 to 31-05-2023

Main work title :

Codes, Cryptology and Information Security

Publisher :

Springer

ISBN/EAN :

978-3-031-33016-2

Pages :

338--359

Peer reviewed :

Peer reviewed

Focus Area :

Security, Reliability and Trust

Additional URL :

https://eprint.iacr.org/2022/1777.pdf

Available on ORBilu :

since 02 January 2023

Statistics

Number of views

52 (8 by Unilu)

Number of downloads

8 (1 by Unilu)

More statistics

Scopus citations^®

Scopus citations^®
without self-citations

Bibliography

[BP05] Braeken, A., Preneel, B.: On the algebraic immunity of symmetric Boolean functions. In: Maitra, S., Veni Madhavan, C.E., Venkatesan, R. (eds.) INDOCRYPT 2005. LNCS, vol. 3797, pp. 35–48. Springer, Heidelberg (2005). https://doi.org/10.1007/11596219 4
Carlet, C.: On the degree, nonlinearity, algebraic thickness, and nonnor-mality of Boolean functions, with developments on symmetric functions. IEEE Trans. Inf. Theory 50(9), 2178–2185 (2004)
Carlet, C.: Boolean Functions for Cryptography and Coding Theory. Cambridge University Press, Cambridge (2021)
Carlet, C., Méaux, P.: A complete study of two classes of Boolean functions: direct sums of monomials and threshold functions. IEEE Trans. Inf. Theory 68(5), 3404–3425 (2021)
Carlet, C., Méaux, P., Rotella, Y.: Boolean functions with restricted input and their robustness; application to the FLIP cipher. IACR Trans. Symmetric Cryptol. 3, 2017 (2017)
Canteaut, A., Videau, M.: Symmetric Boolean functions. IEEE Trans. Inf. Theory 51(8), 2791–2811 (2005)
Dalai, D.K., Maitra, S., Sarkar, S.: Basic theory in construction of Boolean functions with maximum possible annihilator immunity. Des. Codes Crypt. 40, 41–58 (2006). https://doi.org/10.1007/s10623-005-6300-x
[Dob95] Dobbertin, H.: Construction of bent functions and balanced Boolean functions with high nonlinearity. In: Preneel, B. (ed.) FSE 1994. LNCS, vol. 1008, pp. 61–74. Springer, Heidelberg (1995). https://doi.org/10.1007/3-540-60590-8 5
Gini, A., Méaux, P.: On the weightwise nonlinearity of weightwise perfectly balanced functions. Discret. Appl. Math. 322, 320–341 (2022)
[GM22b] Gini, A., Méaux, P.: Weightwise almost perfectly balanced functions: secondary constructions for all n and better weightwise nonlinearities. In: Isobe, T., Sarkar, S. (eds.) Progress in Cryptology (INDOCRYPT 2022). LNCS, vol. 13774, pp. 492–514. Springer, Cham (2022). https://doi.org/10.1007/978-3-031-22912-1 22
Guo, X., Sihong, S.: Construction of weightwise almost perfectly balanced Boolean functions on an arbitrary number of variables. Discret. Appl. Math. 307, 102–114 (2022)
Liu, J., Mesnager, S.: Weightwise perfectly balanced functions with high weightwise nonlinearity profile. Des. Codes Cryptogr. 87(8), 1797–1813 (2019)
Li, J., Sihong, S.: Construction of weightwise perfectly balanced Boolean functions with high weightwise nonlinearity. Discret. Appl. Math. 279, 218–227 (2020)
Millan, W., Clark, A., Dawson, E.: An effective genetic algorithm for finding highly nonlinear Boolean functions. In: Han, Y., Okamoto, T., Qing, S. (eds.) ICICS 1997. LNCS, vol. 1334, pp. 148–158. Springer, Heidelberg (1997). https://doi.org/10.1007/BFb0028471
[Méa21] Méaux, P.: On the fast algebraic immunity of threshold functions. Cryptogr. Commun. 13(5), 741–762 (2021)
Mesnager, S.: Bent Functions. Springer, Cham (2016). https://doi.org/10. 1007/978-3-319-32595-8
[MJSC16] Méaux, P., Journault, A., Standaert, F.-X., Carlet, C.: Towards stream ciphers for efficient FHE with low-noise ciphertexts. In: Fischlin, M., Coron, J.-S. (eds.) EUROCRYPT 2016. LNCS, vol. 9665, pp. 311–343. Springer, Heidelberg (2016). https://doi.org/10.1007/978-3-662-49890-3 13
[MKCL22] Mandujano, S., Ku Cauich, J.C., Lara, A.: Studying special operators for the application of evolutionary algorithms in the seek of optimal Boolean functions for cryptography. In: Pichardo Lagunas, O., Martínez-Miranda, J., Martínez Seis, B. (eds.) Advances in Computational Intelligence (MICAI 2022). LNCS, vol. 13612, pp. 383–396. Springer, Cham (2022). https://doi.org/10.1007/978-3-031-19493-1 30
[MMM+18] Maitra, S., Mandal, B., Martinsen, T., Roy, D., Stănică, P.: Tools in analyzing linear approximation for Boolean functions related to FLIP. In: Chakraborty, D., Iwata, T. (eds.) INDOCRYPT 2018. LNCS, vol. 11356, pp. 282–303. Springer, Cham (2018). https://doi.org/10.1007/978-3-030-05378-9 16
[MMM22] Maitra, S., Mandal, B., Roy, M.: Modifying Bent functions to obtain the balanced ones with high nonlinearity. In: Isobe, T., Sarkar, S. (eds.) Progress in Cryptology (INDOCRYPT 2022). LNCS, vol. 13774, pp. 449– 470. Springer, Cham (2022). https://doi.org/10.1007/978-3-031-22912-1 20
[MPJ+22] Mariot, L., Picek, S., Jakobovic, D., Djurasevic, M., Leporati, A.: Evolutionary construction of perfectly balanced Boolean functions. In: 2022 IEEE Congress on Evolutionary Computation (CEC), pp. 1–8. IEEE (2022)
MacWilliams, F.J., Sloane, N.J.A.: The Theory of Error-Correcting Codes, 2nd edn. North-Holland Publishing Company (1978)
Mesnager, S., Su, S.: On constructions of weightwise perfectly balanced Boolean functions. Cryptogr. Commun. 13, 951–979 (2021). https://doi. org/10.1007/s12095-021-00481-3
Mesnager, S., Su, S., Li, J.: On concrete constructions of weightwise perfectly balanced functions with optimal algebraic immunity and high weightwise nonlinearity. Boolean Funct. Appl. (2021)
Mesnager, S., Sihong, S., Li, J., Zhu, L.: Concrete constructions of weightwise perfectly balanced (2-rotation symmetric) functions with optimal algebraic immunity and high weightwise nonlinearity. Cryptogr. Commun. 14(6), 1371–1389 (2022)
Picek, S., Carlet, C., Guilley, S., Miller, J.F., Jakobovic, D.: Evolutionary algorithms for Boolean functions in diverse domains of cryptography. Evol. Comput. 24(4), 667–694 (2016)
Qu, L., Feng, K., Liu, F., Wang, L.: Constructing symmetric Boolean functions with maximum algebraic immunity. IEEE Trans. Inf. Theory 55(5), 2406–2412 (2009)
Rothaus, O.S.: On ”bent” functions. J. Comb. Theory Ser. A. 20(3), 300– 305 (1976)
Palash Sarkar and Subhamoy Maitra. Balancedness and correlation immunity of symmetric boolean functions. Discrete Mathematics, pages 2351– 2358, 2007
[SZZ93] Seberry, J., Zhang, X.-M., Zheng, Y.: Nonlinearly balanced Boolean functions and their propagation characteristics. In: Stinson, D.R. (ed.) CRYPTO 1993. LNCS, vol. 773, pp. 49–60. Springer, Heidelberg (1994). https://doi.org/10.1007/3-540-48329-2 5
[The17] The Sage Developers: SageMath, the Sage mathematics software system (Version 8.1) (2017). https://www.sagemath.org/
Tang, D., Liu, J.: A family of weightwise (almost) perfectly balanced Boolean functions with optimal algebraic immunity. Cryptogr. Commun. 11(6), 1185–1197 (2019)
Tokareva, N.: Bent Functions: Results and Applications to Cryptography. Academic Press, Cambridge (2015)
Varrette, S., Bouvry, P., Cartiaux, H., Georgatos, F.: Management of an academic HPC cluster: the UL experience. In: 2014 International Conference on High Performance Computing and Simulation (HPCS), pp. 959– 967. IEEE (2014) Sébastien Varrette, Pascal Bouvry, Hyacinthe Cartiaux, and Fotis Georgatos. Management of an academic HPC cluster: The UL experience. In 2014 International Conference on High Performance Computing & Simulation (HPCS), pages 959–967, 2014
Zhang, R., Su, S.: A new construction of weightwise perfectly balanced Boolean functions. Adv. Math. Commun. (2021)
Zhu, L., Sihong, S.: A systematic method of constructing weightwise almost perfectly balanced Boolean functions on an arbitrary number of variables. Discret. Appl. Math. 314, 181–190 (2022)