Upper bounds on the numbers of resilient functions and of bent functions

To appear in Special Issue Dedicated to Philippe Delsarte, Springer Verlag LNCS.

Andrew Klapper, 779A Anderson Hall, Dept. of Computer Science, University of Kentucky, Lexington, KY, 40506-0046, klapper at cs.uky.edu. www.cs.uky.edu/~klapper/andy.html
Claude Carlet, INRIA

Abstract Bent and resilient functions play significant roles in cryptography, coding theory, and combinatorics. However, the numbers of bent and resilient functions on a given number of variables are not known. Even a reasonable bound on the number of bent functions is not known and the best known bound on the number of resilient functions seems weak for functions of high orders. In this paper we present new bounds which significantly improve upon those which can be directly deduced from the restrictions on the degrees of these functions. In the case of bent functions, it is the first one of this type. In the case of m-resilient functions, it improves upon the known bounds for m large.

Index Terms -- Boolean function, nonlinearity, bent, resilient, correlation-immune.