Paper 2021/761

Parameterization of Boolean functions by vectorial functions and associated constructions

Claude Carlet

Abstract

Despite intensive research on Boolean functions for cryptography for over thirty years, there are very few known general constructions allowing to satisfy all the necessary criteria for ensuring the resistance against all the main known attacks on the stream ciphers using them. In this paper, we investigate the general construction of Boolean functions $f$ from vectorial functions, in which the support of $f$ equals the image set of an injective vectorial function $F$, that we call a parameterization of $f$. Any Boolean function whose Hamming weight is a power of 2, and in particular, every balanced Boolean function, can be obtained this way. We study five illustrations of this general construction. The three first correspond to known classes of functions (Maiorana-McFarland, majority functions and balanced functions in odd numbers of variables with optimal algebraic immunity). The two last correspond to new classes of Boolean functions: - sums of indicators of disjoint graphs of $(k,n-k$)-functions, - functions parameterized by highly nonlinear injective vectorial $(n-1,n)$-functions derived from functions due to Beelen and Leander. We study the cryptographic parameters (corresponding to the main criteria) 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 handled (in two ways) by means of the graph indicator of $F$. We show how the algebraic degree and the nonlinearity of the parameterized function can be controlled. We revisit each of the five classes for each criterion. We show that 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. Its sub-class made of the sums of indicators of affine functions, for which we prove an upper bound on the nonlinearity, seems also interesting. The fifth class includes functions with optimal algebraic degree, good nonlinearity and good AI. We leave for future works the determination of simple effective sufficient conditions on $F$ ensuring that $f$ has a good AI, the completion of the study of the fourth class, the mathematical study of the AI and fast algebraic immunity of the functions in the fifth class, and the introduction and study of a class of parameterized functions having good parameters and whose output is fast to compute.