On constructions and enumeration of bent and semi-bent functions

Abstract

Bükük ve yarı-bükük fonksiyonlar kriptografi ve kodlama teorisinde önemli bir rol oynamaktadır. Bu fonksiyonlar yüksek nonlineeriteye sahip olmaları sebebiyle hızlı korelasyon saldırılarına ve lineer kriptanalize dayanıklı olduklarından simetrik anahtarlı kriptosistemlerde yapıtaşları olarak yaygın bir şekilde kullanılmışlardır. Bunun yanında, düşük otokorelasyon, yayılma kriteri, dayanıklılık ve yüksek cebirsel derece gibi istenen kriptografik özelliklere de sahip olabilirler. Bu nedenle, kriptanaliz tekniklerindeki gelişmelere paralel olarak bu tür fonksiyonları bulma ve inşa etme ihtiyacı gün geçtikçe artmaktadır. Bununla birlikte, girdi sayısı arttıkça tüm bükük ve yarı-bükük fonksiyonları bütün uzayda aramak imkansız hale gelmektedir. Bu kısıtlılık araştırmacıları bükük ve yarı-bükük fonksiyonlar elde etmek için makul bir hesaplama gücüne sahip yeni metotlar bulmaya sevk etmiştir. Bükük ve yarı-bükük fonksiyonların inşaası, sınıflandırılması ve sayılması konusunda oldukça çok araştırma yapılmıştır. Bu sebeplerden dolayı, bükük ve yarı-bükük fonksiyonların bilgi birikimine bunların inşaası, sınıflandırılması ve sayılması konusunda sonuçlar sunarak katkıda bulunulması amaç-lanmıştır.Bu tezde, ikinci derece bir Boole fonksiyon sınıfının yarı-büküklük açısından sınıflan-dırılması verilmiş ve yarı-bükük fonksiyonların girdi sayısı sadece 6'nın bir katı iken var olabileceği ispatlanmıştır. Ayrıca, belirli sınıflardaki bükük ve yarı-bükük fonksiyonların sayımı için genel bir yöntem önerilmiştir. Bu yöntem kullanılarak sınıflandırıl-ması yapılan yarı-bükük fonksiyonların tam olarak sayısı bulunmuştur. Buna ek olarak, literatürde var olan bazı bükük/yarı-bükük fonksiyon sınıflarının sayıları ile ilgili sonuç-lar genellenmiştir. Doğrusal yapılar ve çeviriciler kullanılarak Maiorana-McFarland sınıfına ait bükük ve yarı-bükük fonksiyonların inşaaları verilmiştir. Ayrıca, bu inşaalar ve türev gibi diğer cebirsel yapılar ile belirli ikinci ve üçüncü dereceden fonksiyonlar da kullanılarak bükük ve yarı-bükük fonksiyonlar için yeni ikincil inşa sınıfları elde edilmiştir.

Bent and semi-bent functions play an important role in cryptography and coding theory. They are widely studied as parts of building blocks in symmetric key cryptosystems because they provide resistance to fast correlation attacks and linear cryptanalysis due to their high nonlinearity. Besides, they can possess other desirable cryptographic properties such as low autocorrelation, propagation criteria, resiliency and high algebraic degree. Therefore, parallel to the advances in cryptanalysis techniques, the need for finding and constructing such functions increases day by day. However, as the number of inputs gets higher, it becomes impossible to search exhaustively all bent/semi-bent functions on the entire space. This limitation prompts researchers to deduce new methods to obtain bent/semi-bent functions with reasonable amount of computation power. A lot of research has been devoted to construction, characterization or enumeration of bent/semi-bent functions. For these reasons, we aim to contribute to the knowledge of bent and semi-bent functions by presenting new results on constructions, characterization and enumeration of these functions.In this thesis, characterization of a class of quadratic Boolean functions for semi-bentness is given and it is proved that semi-bent functions exist only when the input number is a multiple of 6. Furthermore, a generic method for enumeration of semi-bent and bent functions in certain classes is presented. Using this method, exact number of characterized semi-bent functions is found. Moreover, with this method some previous partial and incomplete enumeration results for three other classes of semi-bent/bent functions in the literature are completed. Explicit constructions of bent and semi-bent functions of Maiorana-McFarland class via linear structures and linear translators are proposed. Also, by using these explicit constructions as well as other algebraic structures like derivatives, certain quadratic and cubic functions, new secondary constructions of bent and semi-bent functions are obtained.