A wide class of Boolean functions generalizing the hidden weight bit function, by Claude Carlet

Designing Boolean functions with fast output to compute and meeting all the criteria necessary for allowing the stream ciphers in which they are used as nonlinear components to resist all major attacks has been an open problem since the beginning of this century, when the algebraic attacks were invented (in 2003). Functions allowing good resistance are known since 2008, but their output is too slow and complex to compute. Functions with a fast and simple to compute output are known, such as majority functions and the so-called hidden weight bit (HWB) functions, but they all have a cryptographic weakness: their too small nonlinearity. \In the present paper, we introduce a generalization of the HWB function into a construction of $n$-variable balanced functions $f$ from $(n-1)$-variable Boolean functions $g$ having some property held by a large number of functions. Function $f$ is defined by its support, equal to the image set of a vectorial function depending on $g$. This makes the function complex enough for allowing good cryptographic parameters, while its output is light to compute. The HWB function is what we obtain with $f$ when the initial function $g$ equals 1. Other well chosen functions $g$ provide functions $f$ having good cryptographic parameters.
We analyze the constructed functions $f$, we provide a fast way to compute their output, we determine their algebraic normal forms and we show that, most often, their algebraic degree is optimal. We study their Walsh transform and their nonlinearity and algebraic immunity. We observe with computer investigations that this generalization of the HWB function allows to keep its quality of being fast to compute and having good enough algebraic immunity, while significantly improving its nonlinearity. The functions already obtained in the investigations provide a quite good (and never reached before) trade-off between speed and security. Further (probably difficult) work should allow obtaining, among such generalized HWB functions whose number is huge, still better filter functions to be used in stream ciphers.