On the weightwise nonlinearity of weightwise perfectly balanced functions

;

2022 • In *Discrete Applied Mathematics, 322*, p. 320-341

Peer reviewed

GM22.pdf

Author preprint (509.45 kB)

All documents in ORBilu are protected by a user license.

copy to clipboard copied

Keywords :

Weightwise nonlinearity; Boolean functions; Weightwise perfectly balancedness; FLIP cipher; secret-key cryptography

Abstract :

[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 :

Mathematics

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 :

yes

Language :

English

Title :

On the weightwise nonlinearity of weightwise perfectly balanced functions

Publication date :

15 December 2022

Journal title :

Discrete Applied Mathematics

Volume :

322

Pages :

Pages 320-341

Peer reviewed :

Peer reviewed

Focus Area :

Security, Reliability and Trust

Available on ORBilu :

since 31 March 2022

Scopus citations^{®}

5

Scopus citations^{®}

without self-citations

without self-citations

2

OpenCitations

0

WoS citations^{™}

4

- 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.
- Canteaut, Anne, Videau, Marion, Symmetric Boolean functions. IEEE Trans. Inf. Theory, 2005, 2791–2811.
- 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, Boolean functions for homomorphic-friendly stream Ciphers. Algebra, Codes Cryptol., 2019, 166–182.
- 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.
- Dumer, Ilya, Kapralova, Olga, Spherically punctured biorthogonal codes. IEEE Trans. Inf. Theory 59:9 (2013), 6010–6017.
- Dumer, Ilya, Kapralova, Olga, Spherically punctured reed-muller codes. IEEE Trans. Inf. Theory 63:5 (2017), 2773–2780.
- 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.