Hide/Show Apps

Constructions of resilient boolean functions with maximum nonlinearity

Şahin, M. Özgür
In this thesis, we work on the upper bound for nonlinearity of t-resilient Boolean functions given by Sarkar and Maitra, which is based on divisibility properties of spectral weights of resilient functions and study construction methods that achieve the upper bound. One of the construction methods, introduced by Maity and Johansson, starts with a bent function and complements some values of its truth table corresponding to a previously chosen set of inputs, S, which satisfies three criteria. In this thesis, we show that a fourth criterion is needed for t-resiliency of the resulting function, and prove that three criteria of Maity and Johansson do not guarantee resiliency. We also work on other constructions, one by Sarkar and Maitra, which uses a Maiorana-McFarland like technique to satisfy the upper bound and the other by Tarannikov, which satisfies the nonlinearity bound using a technique with low computational complexity. However, these methods have tendency to maximize the order of resiliency for a given number of variables, therefore one cannot construct functions for all possible resiliency values given the number of variables, using this method. We further go into details and compute the auto-correlation functions of the constructed Boolean functions to find the absolute indicator and sum-of-squared-errors for each of them. We also provide a comparison of Boolean functions constructed by other techniques given in the literature, together with the ones studied in this thesis.