[en] In this article we perform a general study on the criterion of weightwise nonlinearity for the functions which are weightwise perfectly balanced (WPB). First, we investigate the minimal value this criterion can take over WPB functions, deriving theoretic bounds, and exhibiting the first values. We emphasize the link between this minimum and weightwise affine functions, and we prove that for n≥8 no n-variable WPB function can have this property. Then, we focus on the distribution and the maximum of this criterion over the set of WPB functions. We provide theoretic bounds on the latter and algorithms to either compute or estimate the former, together with the results of our experimental studies for n up to 8. Finally, we present two new constructions of WPB functions obtained by modifying the support of linear functions for each set of fixed Hamming weight. This provides a large corpus of WPB function with proven weightwise nonlinearity, and we compare the weightwise nonlinearity of these constructions to the average value, and to the parameters of former constructions in 8 and 16 variables.
Disciplines :
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 :
yes
Langue du document :
Anglais
Titre :
On the weightwise nonlinearity of weightwise perfectly balanced functions
Alenezi, Ahmad M., Integral zeroes of Krawtchouk polynomials. (Ph.D. thesis), 2012, Brunel University, School of Information Systems, Computing and Mathematics.
An Braeken, Bart Preneel, On the Algebraic Immunity of Symmetric Boolean Functions, in: Progress in Cryptology - INDOCRYPT 2005, 6th International Conference on Cryptology in India, Bangalore, India, December 10-12, 2005, Proceedings, 2005, pp. 35–48.
Bryant, Randal E., On the complexity of VLSI implementations and graph representations of boolean functions with application to integer multiplication. IEEE Trans. Comput. 40:2 (1991), 205–213.
Carlet, Claude, On the degree, nonlinearity, algebraic thickness, and nonnormality of boolean functions, with developments on symmetric functions. IEEE Trans. Inf. Theory, 2004, 2178–2185.
Carlet, Claude, Boolean Functions for Cryptography and Coding Theory. 2021, Cambridge University Press.
Carlet, Claude, Méaux, Pierrick, A complete study of two classes of Boolean functions: direct sums of monomials and threshold functions. IEEE Trans. Inform. Theory, 2021, 1.
Carlet, Claude, Méaux, Pierrick, Rotella, Yann, Boolean functions with restricted input and their robustness; application to the FLIP cipher. IACR Trans. Symmetric Cryptol., 2017(3), 2017.
Chen, Y., Lu, P., Two classes of symmetric boolean functions with optimum algebraic immunity: Construction and analysis. IEEE Trans. Inform. Theory 57:4 (2011), 2522–2538.
Dalai, Deepak Kumar, Maitra, Subhamoy, Sarkar, Sumanta, Basic theory in construction of Boolean functions with maximum possible annihilator immunity. Des. Codes Cryptogr., 2006.
Krasikov, Ilia, Litsyn, Simon, On integral zeros of Krawtchouk polynomials. J. Comb. Theory, Ser. A 74:1 (1996), 71–99.
Li, Jingjing, Su, Sihong, Construction of weightwise perfectly balanced Boolean functions with high weightwise nonlinearity. Discrete Appl. Math. 279 (2020), 218–227.
Liu, Jian, Mesnager, Sihem, Weightwise perfectly balanced functions with high weightwise nonlinearity profile. Des. Codes Cryptogr. 87:8 (2019), 1797–1813.
MacWilliams, F.J., Sloane, N.J.A., The Theory of Error-Correcting Codes. second ed., 1978, North-holland Publishing Company.
Subhamoy Maitra, Bimal Mandal, Thor Martinsen, Dibyendu Roy, Pantelimon Stanica, Tools in Analyzing Linear Approximation for Boolean Functions Related to FLIP, in: Progress in Cryptology - INDOCRYPT 2018 - 19th International Conference on Cryptology in India, New Delhi, India, December 9-12, 2018, Proceedings, 2018, pp. 282–303.
Mario, Luca, Picek, Stjepan, Jakobovic, Domagoj, Djurasevic, Marko, Leporati, Alberto, Evolutionary construction of perfectly balanced Boolean functions. 2022.
Méaux, Pierrick, On the fast algebraic immunity of majority functions. Schwabe, Peter, Thériault, Nicolas, (eds.) Progress in Cryptology - LATINCRYPT LNCS, vol.11774, 2019, Springer, 86–105.
Méaux, Pierrick, On the fast algebraic immunity of threshold functions. Cryptogr. Commun. 13:5 (2021), 741–762.
Méaux, Pierrick, Journault, Anthony, Standaert, François-Xavier, Carlet, Claude, Towards stream ciphers for efficient FHE with low-noise ciphertexts. Fischlin, Marc, Coron, Jean-Sébastien, (eds.) EUROCRYPT 2016, Part I LNCS, vol.9665, 2016, Springer, Heidelberg, 311–343.
Mesnager, Sihem, Su, Sihong, On constructions of weightwise perfectly balanced Boolean functions. Cryptogr. Commun., 2021.
Mesnager, Sihem, Su, Sihong, Li, Jingjing, On concrete constructions of weightwise perfectly balanced functions with optimal algebraic immunity and high weightwise nonlinearity. Boolean Funct. Appl., 2021.
Mesnager, Sihem, Zhou, Zhengchun, Ding, Cunsheng, On the nonlinearity of Boolean functions with restricted input. Cryptogr. Commun. 11:1 (2019), 63–76.
Picek, Stjepan, Carlet, Claude, Guilley, Sylvain, Miller, Julian F., Jakobovic, Domagoj, Evolutionary algorithms for Boolean functions in diverse domains of cryptography. Evol. Comput. 24:4 (2016), 667–694.
Sarkar, Palash, Maitra, Subhamoy, Balancedness and correlation immunity of symmetric Boolean functions. Discrete Math., 2007, 2351–2358.
Stroeker, Roel J., Weger, De, On integral zeroes of binary krawtchouk polynomials. Nieuw Archief Voor Wiskunde, 1999.
Su, Sihong, The lower bound of the weightwise nonlinearity profile of a class of weightwise perfectly balanced functions. Discrete Appl. Math. 297 (2021), 60–70.
Tang, Deng, Liu, Jian, A family of weightwise (almost) perfectly balanced boolean functions with optimal algebraic immunity. Cryptogr. Commun. 11:6 (2019), 1185–1197.
The Sage Developers, SageMath, the sage mathematics software system (version 8.1). 2017 https://www.sagemath.org.
Wang, Qichun, Carlet, Claude, Stanica, Pantelimon, Tan, Chik How, Cryptographic properties of the hidden weighted bit function. Discrete Appl. Math. 174 (2014), 1–10.
Zhang, Rui, Su, Sihong, A new construction of weightwise perfectly balanced boolean functions. Adv. Math. Commun., 2021.
