Characteristics of the binary decision diagrams of Boolean Bent Functions
Schafer, Neil Brendan.
Butler, Jon T.
MetadataShow full item record
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 function's 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.
Approved for public release, distribution unlimited
Showing items related by title, author, creator and subject.
Ang, Kwee Hua (Monterey, California. Naval Postgraduate School, 1995-03);The Binary Decision Diagram (BDD) is a very useful representation in the design and verification of switching functions. This is due to to its compactness, where size is measured by the number of nodes. In the implementation ...
Sasao, Tsutomu; Butler, Jon T. (1996);In VLSI, crossings of interconnect occupy space and cause delay. Therefore, there is significant benefit to planar circuits. We propose the use of planar multiple-valued decision diagrams for produce planar multiple-valued ...
Fisher, Paul D. (Monterey, California. Naval Postgraduate School, 1990-06);A computer program is developed to predict the performance of a thermoacoustic generator. The defining relationships are based on equations derived using short stack and boundary layer approximations. The engine modeled ...