Characteristics of the Binary Decision Diagrams of Boolean Bent Functions
NAVAL POSTGRADUATE SCHOOL MONTEREY CA
Pagination or Media Count:
Boolean bent functions have desirable cryptographic properties in that they have maximum nonlinearity, which hardens a cryptographic function against linear cryptanalysis attacks. Furthermore, bent functions are extremely rare and difficult to find. Consequently, little is known generally about the characteristics of bent functions. One method of representing Boolean functions is with a reduced ordered binary decision diagram. Binary decision diagrams BDD represent functions in a tree structure that can be traversed one variable at a time. Some functions show speed gains when represented in this form, and binary decision diagrams are useful in computer aided design and real-time applications. This thesis investigates the characteristics of bent functions represented as BDDs, with a focus on their complexity. In order to facilitate this, a computer program was designed capable of converting a functions truth table into a minimally realized BDD. Disjoint quadratic functions DQF, symmetric bent functions, and homogeneous bent functions of 6-variables were analyzed, and the complexities of the minimum binary decision diagrams of each were discovered. Specifically, DQFs were found to have size 2n - 2 for functions of n-variables symmetric bent functions have size 4n - 8, and all homogeneous bent functions of 6-variables were shown to be P-equivalent.
- Numerical Mathematics