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.

Available format(s)
Category
Secret-key cryptography
Publication info
Published elsewhere. Minor revision.Advances in Mathematics of Communications
Keywords
Boolean functionvectorial functionnonlinearityalgebraic immunity
Contact author(s)
claude carlet @ gmail com
History
2022-01-26: revised
See all versions
Short URL
https://ia.cr/2021/761

CC BY

BibTeX

@misc{cryptoeprint:2021/761,
author = {Claude Carlet},
title = {Parameterization of Boolean functions by vectorial functions and associated  constructions},
howpublished = {Cryptology ePrint Archive, Paper 2021/761},
year = {2021},
note = {\url{https://eprint.iacr.org/2021/761}},
url = {https://eprint.iacr.org/2021/761}
}

Note: In order to protect the privacy of readers, eprint.iacr.org does not use cookies or embedded third party content.