Analysis and synthesis of cryptographic Boolean functions in Haar domain

Abstract

Cryptographic Boolean functions serve as an integral part of symmetric-key ciphers. A strong cipher requires that the underlying functions meet specific security criteria. Traditionally, the Walsh transform and autocorrelation function of Boolean functions have been deployed as the main tools for studying whether such functions meet the desired criteria. This thesis introduces the Haar transform as an alternative tool for studying cryptographic Boolean functions. The thesis presents Haar analysis and synthesis (construction) of cryptographically significant functions, including their related application specific designs. The study parallels with the earlier ones based on the Walsh domain approach. For the analysis part, the work begins by establishing the missing connections between the Haar, Walsh, and autocorrelation spectra. This stage presents new Haar representations of the Walsh-Paley transform and autocorrelation function, along with the related connection to the power spectrum. Using the Walsh analogy, the work then proceeds to derive the Haar based measures for the main cryptographic criteria including; Hamming distance and weight, balancedness, bentness, nonlinearity, correlation immunity, resiliency, strict-avalanche, global-avalanche and propagation criteria. The work presents the Haar general formulation and representation of all the stated criteria. The synthesis part is divided into two sub-parts related to testing and construction algorithms. The former introduces Haar based algorithms for testing and measuring main cryptographic criteria. The latter includes algorithms in two forms of Haar stochastic multistage search and Haar spectrum manipulation techniques. Both of these algorithms work on modifying bent functions to yield optimum functions with desired trade-off between criteria. This part also presents the simulation results of the Haar based algorithms in comparison to the existing benchmarks. The last part of the work involves deploying the synthesized functions for the design of S-boxes and combiner/filtering functions. A new design approach to S-boxes is presented along with its related experimental results for 4x4 and 6x4 mappings. For the 6x4 mapping, a set of 8 new DES-like S-boxes are selected and their security characteristics are compared to the existing benchmarks of DES and its improved variants. Additionally, the work proposes a new approach to the design of the underlying combiner/filtering functions. The simulation results demonstrate that the Haar based testing algorithms exhibit better computational complexity compared to their counterparts, possess the unique ability to quit the testing even when the spectrum is only processed partially, and their local zones' view allows for possible parallel and independent processing. Moreover, the construction algorithms have the flexibility to yield a single as well as a pool of cryptographically desired functions, and provide the lower variables' domain view in terms of the related sub-functions without leaving the current domain. The new designed S-boxes have shown improved security characteristics in terms of nonlinearity, differential characteristics, average probabilities and cross correlations. These methods allow for more design decision flexibility with an alternative local view that is not possible from the existing methods.