Parameterization of Boolean functions by vectorial functions and associated constructions
Claude Carlet · Advances in Mathematics of Communications · 2022
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.