Parameterization of Boolean functions by vectorial functions and associated constructions

Claude Carlet

doi:10.3934/amc.2022013

Article Contents

2024, Volume 18, Issue 3: 624-650. Doi: 10.3934/amc.2022013

This issue Previous Article Finding small roots for bivariate polynomials over the ring of integers Next Article Self-orthogonal codes from equitable partitions of distance-regular graphs

Parameterization of Boolean functions by vectorial functions and associated constructions

Claude Carlet

Department of informatics, University of Bergen, Norway and LAGA, University of Paris 8, France

Received: October 2021

Early access: March 2022

Published online: March 2022

The research of the author is partly supported by the Trond Mohn Foundation and Norwegian Research Council.

Abstract / Introduction Full Text(HTML) Related Papers Cited by

Abstract

Too few general constructions of Boolean functions satisfying all cryptographic criteria are known. We investigate the construction in which the support of $ f $ equals the image set of an injective vectorial function $ F $, that we call a parameterization of $ f $. Every balanced Boolean function can be obtained this way. We study five illustrations of this general construction. The three first correspond to known classes (Maiorana-McFarland, majority functions and balanced functions in odd numbers of variables with optimal algebraic immunity). The two last correspond to new classes:

- the sums of indicators of disjoint graphs of $ (k,n-k $)-functions,

- functions parameterized through $ (n-1,n) $-functions due to Beelen and Leander.

We study the cryptographic parameters of balanced Boolean functions, according to those of their parameterizations: the algebraic degree of $ f $, that we relate to the algebraic degrees of $ F $ and of its graph indicator, the nonlinearity of $ f $, that we relate by a bound to the nonlinearity of $ F $, and the algebraic immunity (AI), whose optimality is related to a natural question in linear algebra, and which may be approached (in two ways) by using the graph indicator of $ F $. We revisit each of the five classes for each criterion. The fourth class is very promising, thanks to a lower bound on the nonlinearity by means of the nonlinearity of the chosen $ (k,n-k $)-functions. The sub-class of the sums of indicators of affine functions, for which we prove an upper bound and a lower bound on the nonlinearity, seems also interesting. The fifth class includes functions with an optimal algebraic degree, good nonlinearity and good AI.

Keywords:

Mathematics Subject Classification: Primary: 11T71, 43A46; Secondary: 12E20.

Citation:

Full Text(HTML)

Related Papers

Cited by

References

[1]	E. F. Assmus, Jr. and J. D. Key, Designs and Their Codes, volume 103 of Cambridge Tracts in Mathematics. Cambridge University Press, Cambridge, UK, 1992. doi: 10.1017/CBO9781316529836.
[2]	P. Beelen and G. Leander, A new construction of highly nonlinear S-boxes, Cryptogr. Commun., 4 (2012), 65-77. doi: 10.1007/s12095-011-0052-4.
[3]	A. Canteaut, Open problems related to algebraic attacks on stream ciphers, Coding and Cryptography, 3969 (2006), 120-134. doi: 10.1007/11779360_10.
[4]	C. Carlet, A larger class of cryptographic Boolean functions via a study of the Maiorana-McFarland construction, Advances in Cryptology—CRYPTO, 2442 (2002), 549-564. doi: 10.1007/3-540-45708-9_35.
[5]	C. Carlet, Handling vectorial functions by means of their graph indicators, IEEE Trans. Inform. Theory, 66 (2020), 6324-6339. doi: 10.1109/TIT.2020.2981524.
[6]	C. Carlet, Graph indicators of vectorial functions and bounds on the algebraic degree of composite functions, IEEE Trans. Inform. Theory, 66 (2020), 7702-7716. doi: 10.1109/TIT.2020.3017494.
[7]	C. Carlet, Boolean Functions for Cryptography and Coding Theory, Monograph in Cambridge University Press 562 pages, 2021. doi: 10.1017/9781108606806.
[8]	C. Carlet, P. Charpin and V. Zinoviev, Codes, bent functions and permutations suitable for DES-like cryptosystems, Des. Codes Cryptogr., 15 (1998), 125-156. doi: 10.1023/A:1008344232130.
[9]	C. Carlet, D. Dalai, K. Gupta and S. Maitra, Algebraic immunity for cryptographically significant Boolean functions: Analysis and construction, IEEE Trans. Inform. Theory, 52 (2006), 3105-3121. doi: 10.1109/TIT.2006.876253.
[10]	C. Carlet and K. Feng, An infinite class of balanced functions with optimum algebraic immunity, good immunity to fast algebraic attacks and good nonlinearity, Advances in cryptology—ASIACRYPT, 5350 (2008), 425-440. doi: 10.1007/978-3-540-89255-7_26.
[11]	C. Carlet and P. Méaux, Boolean functions for homomorphic-friendly stream ciphers, Algebra, Codes and Cryptology, 1133 (2019), 166-182. doi: 10.1007/978-3-030-36237-9_10.
[12]	C. Carlet and S. Picek, On the practical limits of a generalization of the hidden weight bit function and of another construction of highly nonlinear functions, Preprint, 2022.
[13]	D. K. Dalai, S. Maitra and S. Sarkar, Basic theory in construction of boolean functions with maximum possible annihilator immunity, Des. Codes Cryptogr., 40 (2006), 41-58. doi: 10.1007/s10623-005-6300-x.
[14]	C. Ding, C. Li and Y. Xia, Another generalisation of the binary Reed-Muller codes and its applications, Finite Fields Appl., 53 (2018), 144-174. doi: 10.1016/j.ffa.2018.06.006.
[15]	H. Dobbertin, Construction of bent functions and balanced Boolean functions with high nonlinearity, Fast Software Encryption, 1008 (1995), 61-74. doi: 10.1007/3-540-60590-8_5.
[16]	I. Dumer and O. Kapralova, Spherically punctured Reed-Muller codes, IEEE Trans. Inform. Theory, 63 (2017), 2773-2780.
[17]	K. Li, S. Mesnager and L. Qu, Further study of 2-to-1 mappings over $\mathbb{F}_2^n$, IEEE Trans. Inform. Theory, 67 (2021), 3486-3496. doi: 10.1109/TIT.2021.3057094.
[18]	F. J. MacWilliams and N. J. Sloane, The Theory of Error-Correcting Codes, Amsterdam-New York-Oxford, 1977.
[19]	P. Méaux, C. Carlet, A. Journault and F.-X. Standaert, Improved filter permutators for efficient FHE: Better instances and implementations, Proceedings of Indocrypt 2019, Lecture Notes in Computer Science, 11898 (2019), 68-91.
[20]	P. Méaux, A. Journault, F.-X. Standaert and C. Carlet, Towards stream ciphers for efficient FHE with low-noise ciphertexts, Advances in Cryptology—EUROCRYPT, 9665 (2016), 311-343. doi: 10.1007/978-3-662-49890-3_13.
[21]	S. Mesnager, Linear Codes from Functions, Chapter 20 in "A Concise Encyclopedia 1419 Coding Theory" CRC Press/Taylor and Francis Group (Publisher), London, New York, 2021 (94 pages).
[22]	S. Mesnager and L. Qu, On two-to-one mappings over finite fields, IEEE Trans. Inform. Theory, 65 (2019), 7884-7895. doi: 10.1109/TIT.2019.2933832.
[23]	G. Mullen and D. Panario, Handbook of Finite Fields, CRC Press Book, 2013. doi: 10.1201/b15006.
[24]	Q. Wang, C. Carlet, P. Stănică and C. H. Tan, Cryptographic properties of the hidden weighted bit function, Discrete Appl. Math., 174 (2014), 1-10. doi: 10.1016/j.dam.2014.01.010.