Some enumeration problems for cryptographic Boolean functions
MetadataShow full item record
This dissertation consists of two parts: Counting balanced Boolean functions, and Counting SAC ( n - 1) functions over GF ( p ). The Strict Avalanche Criterion (SAC), Balance, and Correlation Immunity are important properties for many types of cryptographic functions. It is of interest to count the functions satisfying these criterions. In the first part of this dissertation, we obtain good upper and lower bounds on the number [Special characters omitted.] <math> <f> B<sup>n</sup><inf>k</inf></f> </math> which is defined as the number of balanced Boolean functions in n variables with degree ≤ k . The weight distribution of k -th order Reed-Muller code of length 2 n ( R ( k, n )), is the list of the possible weights of the codewords in R ( k, n ). We apply the theory of Reed-Muller codes to obtain the number of balanced Boolean functions, since [Special characters omitted.] <math> <f> B<sup>n</sup><inf>k</inf></f> </math> count the codewords of the middle weight 2 n -1 . Also we suggest conjectures for bounds on the number of balanced Boolean functions. The second part of the dissertation addresses counting functions satisfying the strict avalanche criterion functions over finite fields. We extend the SAC concept from GF (2) to GF ( p ). We describe the important properties of SAC ( n - 1) functions over GF ( p ) such as if f is SAC ( n - 1), then the degree of each x i must be 2. We also count 20,150 SAC ( n - 1) functions over GF (3) in 3 variables without O ( x 1 , x 2 , x 3 ).