Boolean Function Cryptography Algebraic Degree Enumeration Distribution
Issue Date:
2019
Publisher:
Institute of Mathematics and Informatics Bulgarian Academy of Sciences
Citation:
Serdica Journal of Computing, Vol. 13, No 1-2, (2019), 017p-026p
Abstract:
Knowledge on the enumeration and distribution of
Boolean functions according to their algebraic degrees is
important for the theory as well as for its applications. As of now,
this knowledge is not complete; for example, it is well-known that
half of all Boolean functions have a maximal algebraic degree. In
this paper, a formula for the number of all Boolean functions of n
variables and algebraic degree = k is derived. A direct
consequence from it is the assertion (formulated already by
Claude Carlet) that when n →∞, almost half of all Boolean functions
of n variables have an algebraic degree = n−1. The results
obtained by this formula were used in creating the sequence
A319511 in the OEIS. The discrete probability of a random Boolean
function having a certain algebraic degree is defined and the
corresponding distribution is computed, for 3 ≤ n ≤ 10. Four
applications are considered: at the design and analysis of efficient
algorithms for exact or probabilistic computing the algebraic
degree of Boolean functions; when checking 4 test files for
representativeness; when creating benchmark files of Boolean functions.
