[en] In this article we realize a general study on the nonlinearity of weightwise perfectly balanced (WPB)
<br />functions. First, we derive upper and lower bounds on the nonlinearity from this class of functions for all n. Then,
<br />we give a general construction that allows us to provably provide WPB functions with nonlinearity as low as
<br />2
<br />n/2−1
<br />and WPB functions with high nonlinearity, at least 2
<br />n−1 − 2
<br />n/2
<br />. We provide concrete examples in 8 and
<br />16 variables with high nonlinearity given by this construction. In 8 variables we experimentally obtain functions
<br />reaching a nonlinearity of 116 which corresponds to the upper bound of Dobbertin’s conjecture, and it improves
<br />upon the maximal nonlinearity of WPB functions recently obtained with genetic algorithms. Finally, we study the
<br />distribution of nonlinearity over the set of WPB functions. We examine the exact distribution for n = 4 and provide
<br />an algorithm to estimate the distributions for n = 8 and 16, together with the results of our experimental studies for
<br />n = 8 and 16.
Disciplines :
Sciences informatiques Mathématiques
Auteur, co-auteur :
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
Co-auteurs externes :
no
Langue du document :
Anglais
Titre :
Weightwise perfectly balanced functions and nonlinearity
Date de publication/diffusion :
2022
Nom de la manifestation :
Codes, Cryptology and Information Security: 4th International Conference
[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
[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)
