You are looking at a specific version 20210609:062034 of this paper. See the latest version.

Paper 2021/762

A wide class of Boolean functions generalizing the hidden weight bit function

Claude Carlet

Abstract

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.

Metadata
Available format(s)
PDF
Category
Secret-key cryptography
Publication info
Preprint. MINOR revision.
Keywords
Boolean functionnonlinearityalgebraic immunity
Contact author(s)
claude carlet @ gmail com
History
2021-11-06: revised
2021-06-09: received
See all versions
Short URL
https://ia.cr/2021/762
License
Creative Commons Attribution
CC BY
Note: In order to protect the privacy of readers, eprint.iacr.org does not use cookies or embedded third party content.