On nonlinearity and hamming weight preserving bijective mappings acting on boolean functions

Abstract

Kriptografik literatürde Boole fonksiyonları, türlü kriptografik projelerdeki rolleri ve uygulamaları nedeniyle, oldukça sık çalışılmaktadır. Özellikle simetrik kriptosistemlerin kriptografik saldırılara dayanıklı olması için Boole fonksiyonları birkaç kriptografik tasarım kriterleri ile ilişkilendirilir. Shannon'ın gizlilik sistemlerinin benzerliği teorisi gereği, kriptografik tasarım kriterleri en azından temel dönüşümlerin etkisi altında korunmalıdır. Bu tasarım kriterleri arasından nonlineerite kriterleri, Meier ve Staffelbach tarafından fonksiyonların girdileri üzerine tanımlı tersinir dönüşümlerin etkisi altında incelenmiştir. Daha sonra, Preneel nonlineeritenin afin denklik dönüşümlerinin etkisi altında da sabit kaldığını ispatlamıştır. Önceki çalışmalardan hareketle, yazar, yüksek lisans tezinde nonlineeriteyi koruyan yeni tersinir dönüşümlerin varlığını göstermiştir.Bu çalışmada öncelikle, Boole fonksiyonları üzerine etki edebilecek maksimal grubun tanımını vermekteyiz. Bu maksimal grup Boole fonksiyonlarının doğruluk tablolarının oluşturduğu kümeye karşılık gelen vektör uzayının simetrik grubuna tekabül eder. Koordinat fonksiyonlarının cebirsel normal formlarını baz alarak bu simetrik grubun öğelerine bir gösterim veriyor ve sonrasında bu sismetrik grubun çalışmada odaklanacağımız altgruplarını listeliyoruz. Bu altgrupları dikkate alarak; amacımız butersinir dönüşümlerin içinden bir kriptografik tasarım kriterini koruyanlarını saymak veya sınıflandırmakdır. Gerekli tanım ve nosyonlardan sonra, çoğunlukla nonlineeriteyi koruyan tersinir dönüşümleri incelemekteyiz. Ardından nonlineeritenin korunması üzerine oluşturulan prosedürleri diğer bir kriptografik tasarım kriteri olan Hamming ağırlığı için uygulamaktayız. Teorik bakış açısıyla, temelde nonlineeriteyi (benzer şekilde Hamming ağırlığını) sabit bırakan yeni tersinir dönüşümler ailesinin varlığını göstermekteyiz.Lineer ve afin tersinir dönüşümlerin etkisi altında, nonlineeritenin sabit kalması için gerek ve yeter şartları veriyoruz. Afin denklik dönüşümler altgrubu ile Sylvester Hadamard matrislerinin otomorfizma grubu arasında açıkca bir izomorfizma oluşturuyor ve bu otomorfizma grubunun eleman sayısını veriyoruz. Devamında nonlineeriteyi koruyan afin olmayan bir tersinir dönüşümler ailesini açıkca oluşturuyoruz. Fakat, açıkca bilinen nonlineeriteyi koruyan tersinir dönüşümlerin tamamının afin denklik dönüşümler ile aynı yörünge yapısını ürettiklerini gösteriyoruz. Öte yandan, $n/leq 6$ değişkenli fonksiyonlar için nonlineeriteyi koruyan dönüşümlerin tam sayılarını veriyoruz. Ondan sonra bu sayılardan hareketle, açıkca oluşturmadan afin olmayan nonlieeriteyi koruyan yeni tersinir dönüşümlerin varlığını ispatlıyoruz. Bu afin olmayan dönüşümlerin bazı örneklerini veriyoruz.Nonlineeriteyi koruyan tersinir dönüşümler için elde edilen sonuçları izleyerek; çalışmamızı Hamming ağırlığını koruyan tersinir dönüşümleri de kapsayacak şekilde genişletiyoruz. Öncelikle Hamming ağırlığını koruyan dönüşümlerin sayılması problemini tamamıyla çözümlüyor ve tüm Boole fonksiyonları için Hamming ağırlığını koruyan tersinir dönüşümlerin sayısını veriyoruz. Sonrasında sınıflandırma problemi üzerine çalışıyor ve kısmi sonuçlar veriyoruz. Lechner Hamming ağırlığı özelliğinin girdi vektör uzayının simetrik grubunun etkisi altında korunduğunu göstermiştir. Biz afin tersinir dönüşümlerin içinde de sadece bu dönüşümlerin Hamming ağırlığınu koruduğunu kanıtladık. Son olarak ise yine Hamming ağırlığını koruyan dönüşümlerin sayısından hareketle afin olmayan Hamming ağırlığını koruyan dönüşümlerin varlığını ispatlıyoruz.

Boolean functions are widely studied in cryptography due to their key role and ap-plications in various cryptographic schemes. Particularly in order to make symmetriccrypto-systems resistant against cryptanalytic attacks, Boolean functions are associ-ated some cryptographic design criteria. As a result of Shannon's similarity of secrecysystems theory, cryptographic design criteria should be at least preserved under theaction of basic transformations. Among these design criteria, Meier and Staffelbachanalyzed behavior of the nonlinearity criteria under the action of bijective mappingsdefined on input values of the functions. Later, Preneel proved that nonlinearity stillremains invariant under the action of affine equivalence mappings. Motivated by theprevious studies, in his master thesis, the author showed the existence of new nonlin-earity preserving bijective mappings.In this thesis, we first give definition of the maximal group that can act on Booleanfunctions. This maximal group is the symmetric group of the vector space that cor-responds to the set comprised of the truth table of the Boolean functions. We give arepresentation, based on the coordinate functions' algebraic normal form, for the ele-ments of this symmetric group and then we list its subgroups that we mainly focus on.Regarding these subgroups, our aim is to enumerate or classify these bijective map-pings with respect to preserving a cryptographic design criterion. After the necessarydefinitions and notions, we mainly investigate the nonlinearity preserving bijectivemappings. Then we apply the procedures constructed on nonlinearity preservabilityviito another cryptographic design criterion, namely the Hamming weight. From a the-oretical viewpoint, our basic result is that we show the existence of new families ofbijective mappings that leaves nonlinearity (respectively, Hamming weight) invariant.Under the action of linear and affine bijective mappings we give the necessary andsufficient conditions to keep nonlinearity invariant. We explicitly construct an iso-morphism between the affine equivalency mappings subgroup and the automorphismgroup of the Sylvester Hadamard matrices and give the order of this automorphismgroup. Next we construct a family of non-affine nonlinearity preserving bijective map-pings explicitly. However, we also show that all of these explicitly constructed non-linearity preserving bijective mappings produce the same orbit structure as the affineequivalency mappings. On the other hand, we give the exact number of nonlinearitypreserving bijective mappings for the functions with n ≤ 6 variables. Then, based onthese cardinalities, we prove the existence of new non-affine nonlinearity preservingmappings, without constructing explicitly. We demonstrate some examples for thesenon-affine mappings.Following the results obtained for nonlinearity preserving bijective mappings, we ex-tend our study to the Hamming weight preserving bijective mappings. First we com-pletely solve the enumeration problem of Hamming weight preserving bijective map-pings, and give the exact number of the Hamming weight preserving bijective map-pings for all Boolean functions. Afterwards, we study the classification problem andgive partial results. Lechner proved that the Hamming weight property is preserved un-der the action of symmetric group of input vector space. We further prove that amongthe affine bijective mappings only these mappings preserve the Hamming weight. Fi-nally, again based on the enumeration of the Hamming weight preserving bijectivemappings we proved the existence of Hamming weight preserving non-affine bijectivemappings.