
Parameterization of Boolean functions by vectorial functions and associated constructions
Author(s) -
Claude Carlet
Publication year - 2024
Publication title -
advances in mathematics of communications
Language(s) - English
Resource type - Journals
SCImago Journal Rank - 0.601
H-Index - 26
eISSN - 1930-5346
pISSN - 1930-5338
DOI - 10.3934/amc.2022013
Subject(s) - mathematics , combinatorics , boolean function , injective function , parameterized complexity , function (biology) , disjoint sets , discrete mathematics , arithmetic , biology , evolutionary biology
Too few general constructions of Boolean functions satisfying all cryptographic criteria are known. We investigate the construction in which the support of \begin{document}$ f $\end{document} equals the image set of an injective vectorial function \begin{document}$ F $\end{document} , that we call a parameterization of \begin{document}$ f $\end{document} . 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 \begin{document}$ (k,n-k $\end{document} )-functions, - functions parameterized through \begin{document}$ (n-1,n) $\end{document} -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 \begin{document}$ f $\end{document} , that we relate to the algebraic degrees of \begin{document}$ F $\end{document} and of its graph indicator, the nonlinearity of \begin{document}$ f $\end{document} , that we relate by a bound to the nonlinearity of \begin{document}$ F $\end{document} , 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 \begin{document}$ F $\end{document} . 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 \begin{document}$ (k,n-k $\end{document} )-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.