SAĞDIÇOĞLU, Serhat
M.S., Mathematics
Supervisor : Assoc. Prof. Dr. Ali Doğanaksoy
Co-supervisor : -
September 2003, 99 pages

Boolean functions are the main building blocks of most cipher systems. Various aspects of their cryptological characteristics are examined and investigated by many researchers from different fields. This thesis has no claim to obtain original results but consists in an attempt at giving a unified survey of the main results of the subject. In this thesis, the theory of boolean functions is presented in details, emphasizing some important cryptological properties such as balance, nonlinearity, strict avalanche criterion and propagation criterion. After presenting many results about these criteria with detailed proofs, two upper bounds and two lower bounds on the nonlinearity of a boolean function due to Zhang and Zheng are proved. Because of their importance in the theory of boolean functions, construction of Sylvester-Hadamard matrices are shown and most of their properties used in cryptography are proved. The Walsh transform is investigated in detail by proving many properties. By using a property of Sylvester-Hadamard matrices, the fast Walsh transform is presented and its application in finding the nonlinearity of a boolean function is demonstrated. One of the most important classes of boolean functions, so called bent functions, are presented with many properties and by giving several examples, from the paper of Rothaus. By using Bent functions, relations between balance, nonlinearity and propagation criterion are presented and it is shown that not all these criteria can be simultaneously satisfied completely. For this reason, several constructions of functions optimizing these criteria which are due to Seberry, Zhang and Zheng are presented.

Keywords : Cryptography, Boolean functions, Hadamard matrices, Sylvester-Hadamard matrices, Nonlinearity, Strict avalanche criterion, Propagation criterion, Walsh transform, Fast Walsh transform, Bent function.

SAĞDIÇOĞLU, Serhat
Yüksek.Lisans., Matematik
Supervisor : Assoc. Prof. Dr. Ali Doğanaksoy
Co-supervisor : -
Eylul 2003, 99 sayfa

Boole fonksiyonları bir çok şifre sisteminin ana yapı taşıdır. Bunların muhtelif kriptolojik karakteristikleri farklı alanlardan bir çok araştırmacı tarafından ele alınmış ve incelenmiştir. Bu tez hiç bir özgün sonuç elde etme iddasında bulunmamakta, sadece konunun ana sonuçlarının bütünleşik bir mütalaasını vermeye teşebbüs etmektedir. Bu tezde Boole fonksiyonlarının teorisi dengelilik, doğrusal olmama, tam çığ ölçütü ve yayılma ölçütü gibi bazı önemlik kriptolojik özellikler vurgulanarak detayları ile sunulmaktadır. Bu ölçütler hakkındaki bir çok sonucu detaylı ispatlar ile sunduktan sonra bir Boole fonksiyonunun doğrusal olmaması üzerinde Zhang ve Zheng’e ait iki üst sınır ve iki alt sınır ispatlanmıştır. Boole fonksiyonlar teorisindeki önemlerinden dolayı, Sylvester-Hadamard matrislerinin inşaası gösterilmiş ve kriptografide kullanılan birçok özellikleri ispatlanmıştır. Walsh dönüşümü birçok özellikleri ispatlanarak detayları ile incelenmiştir. Sylvester-Hadamard matrislerinin bir özelliğini kullanarak hızlı Walsh dönüşümü sunulmuş ve bir Boole fonksiyonunun doğrusal olmama değerinin bulunmasındaki uygulaması gösterilmiştir. Bükük (bent) fonksiyonlar olarak anılan Boole fonksiyonlarının en önemli sınıflarından birisi Rothaus’un makalesinden birçok özellikler ve çeşitli örnekler vererek sunulmuştur. Bükük fonksiyonları kullanarak dengelilik, doğrusal olmama ve yayılma ölçütü arasındaki ilişkiler sunulmuş ve bu kriterlerin hepsinin aynı zamanda tamamen sağlanamayacağı gösterilmiştir. Bu nedenden dolayı, Seberry, Zhang ve Zheng’e ait olan ve bu kriterleri optimize eden birçok fonksiyon inşaası sunulmuştur.

Anahtar Kelimeler : Kriptografi, Boole fonksiyonları, Hadamard matrisleri, Sylvester-Hadamard matrisleri, Doğrusal olmama, Tam çığ ölçütü, Yayılma ölçütü, Walsh dönüşümü, Hızlı Walsh dönüşümü, Bükük fonksiyon.