Paper 2021/762
A wide class of Boolean functions generalizing the hidden weight bit function
Claude Carlet
Abstract
Designing Boolean functions whose output can be computed with light means at high speed, and satisfying all the criteria necessary to resist all major attacks on the stream ciphers using them as nonlinear components, has been an open problem since the beginning of this century, when algebraic attacks were invented. Functions allowing good resistance are known since 2008, but their output is too complex to compute. Functions with fast and easy to compute output are known which have good algebraic immunity, such as majority functions and the socalled hidden weight bit (HWB) functions, but they all have the same cryptographic weakness: their too small nonlinearity. \\In the present paper, we introduce a generalization of the HWB functions into a construction of $n$variable balanced functions $f$ from $(n1)$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 constant 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) tradeoff 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.
Metadata
 Available format(s)
 Category
 Secretkey cryptography
 Publication info
 Published elsewhere. MINOR revision.IEEE Transactions on Information Theory
 Keywords
 Boolean functionnonlinearityalgebraic immunity
 Contact author(s)
 claude carlet @ gmail com
 History
 20211106: revised
 20210609: received
 See all versions
 Short URL
 https://ia.cr/2021/762
 License

CC BY
BibTeX
@misc{cryptoeprint:2021/762, author = {Claude Carlet}, title = {A wide class of Boolean functions generalizing the hidden weight bit function}, howpublished = {Cryptology ePrint Archive, Paper 2021/762}, year = {2021}, note = {\url{https://eprint.iacr.org/2021/762}}, url = {https://eprint.iacr.org/2021/762} }