Analysis of Boolean functions with respect to Walsh spectrum

Abstract

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.

Boole fonksiyonları kodlama teorisi, kombinatorik, karmaşıklık teorisi, kriptografi, çizge kuramı vs. gibi çeşitli bilimsel disiplinlerde ortaya çıkmaktadır. Kriptografide, kriptografik karakteristik çeşitliliği içeren Boole fonksiyonlarının tasarım ve analizi sık sık ilgi odağı olmuştur. Bu kriptografik karakteristiklerin çoğu için verimli bir araştırma alanı, Boole fonksiyonlarının en sık rastlanan gösterimlerinden biri olan Walsh spektrumdur. Bu tez Boole fonksiyonlarının Walsh spektruma göre bir analizini sunmaktadır. Araştırma temel olarak Walsh spektrumunda belirli bir s sayısı kadar gözüken rastgele bir ? değerine sahip n değişkenli Boole fonksiyonlarının varlığı, yapılandırılması ve sayılmasının belirlenmesi problemine adanmıştır. Tez bu problemin çözümü için n, ? ve s parametreleriyle yeni bir çerçeve geliştirmektedir. Bu çerçeve dahilinde 6 değişkene kadar Boole fonksiyonlarının tam sınıflandırılması elde edilmiştir. Daha yüksek boyutlarda, yapılandırma yöntemiyle ispat, birkaç açık formül ve sınır bulunmuştur. Diğer taraftan, afin denkliğin kullanılması ve lokal bağlantısallık ele alınmıştır. Yeni bir afin değişmez ve denklik sınıflarının boyutlarını hesaplamak için bir algoritma sunulmuştur.