Analysis of Boolean functions with respect to Walsh spectrum

---

Tezin Türü: Doktora

Tezin Yürütüldüğü Kurum: Orta Doğu Teknik Üniversitesi, Fen Edebiyat Fakültesi, Matematik Bölümü, Türkiye

Tezin Onay Tarihi: 2013

Öğrenci: ERDENER UYAN

Danışman: ALİ DOĞANAKSOY

Özet:

Boolean functions appear in various scientific disciplines including coding theory, combinatorics, complexity theory, cryptography, graph theory, etc. In cryptography, the design and analysis of Boolean functions possessing a range of cryptographic characteristics has often been the focus of attention. A productive ground of research for most of these cryptographic characteristics is Walsh spectrum, one of the most common representations of a Boolean function. This thesis presents an analysis of Boolean functions with respect to Walsh spectrum. The research is mainly devoted to the problem of determining the existence, construction and enumeration of n-variable Boolean functions having an arbitrary value, ?, appearing a certain number of times, s, in their Walsh spectrum. The thesis develops a new framework for the solution of this problem with parameters n, ? and s. Complete classification of Boolean functions of up to 6-variables is obtained within this framework. In higher dimensions, proof of existence by construction, several explicit formulas and bounds for various ? and s values are devised. On the other hand, the use of affine equivalence and the local connectivity is discussed. A new affine invariant property and an algorithm for computing the sizes of equivalence classes are introduced.