Geri Dön

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

Boole fonksiyonları üzerine tanımlı nonlineerite ve hamming ağırlığını koruyan tersinir dönüşümler

  1. Tez No: 371212
  2. Yazar: İSA SERTKAYA
  3. Danışmanlar: DOÇ. DR. ALİ DOĞANAKSOY
  4. Tez Türü: Doktora
  5. Konular: Matematik, Mathematics
  6. Anahtar Kelimeler: Belirtilmemiş.
  7. Yıl: 2014
  8. Dil: İngilizce
  9. Üniversite: Orta Doğu Teknik Üniversitesi
  10. Enstitü: Uygulamalı Matematik Enstitüsü
  11. Ana Bilim Dalı: Kriptografi Ana Bilim Dalı
  12. Bilim Dalı: Belirtilmemiş.
  13. Sayfa Sayısı: 86

Özet

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 bu tersinir 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.

Özet (Çeviri)

Boolean functions are widely studied in cryptography due to their key role and ap- plications in various cryptographic schemes. Particularly in order to make symmetric crypto-systems resistant against cryptanalytic attacks, Boolean functions are associ- ated some cryptographic design criteria. As a result of Shannon's similarity of secrecy systems theory, cryptographic design criteria should be at least preserved under the action of basic transformations. Among these design criteria, Meier and Staffelbach analyzed behavior of the nonlinearity criteria under the action of bijective mappings defined on input values of the functions. Later, Preneel proved that nonlinearity still remains invariant under the action of affine equivalence mappings. Motivated by the previous 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 Boolean functions. 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 a representation, 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 necessary definitions and notions, we mainly investigate the nonlinearity preserving bijective mappings. Then we apply the procedures constructed on nonlinearity preservability viito 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 of bijective mappings that leaves nonlinearity (respectively, Hamming weight) invariant. Under the action of linear and affine bijective mappings we give the necessary and sufficient conditions to keep nonlinearity invariant. We explicitly construct an iso- morphism between the affine equivalency mappings subgroup and the automorphism group of the Sylvester Hadamard matrices and give the order of this automorphism group. 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 affine equivalency mappings. On the other hand, we give the exact number of nonlinearity preserving bijective mappings for the functions with n ≤ 6 variables. Then, based on these cardinalities, we prove the existence of new non-affine nonlinearity preserving mappings, without constructing explicitly. We demonstrate some examples for these non-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 and give 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 among the affine bijective mappings only these mappings preserve the Hamming weight. Fi- nally, again based on the enumeration of the Hamming weight preserving bijective mappings we proved the existence of Hamming weight preserving non-affine bijective mappings.

Benzer Tezler

  1. Meta-sezgisel algoritmalar ile kriptografik boole fonksiyonlarının tasarımı

    Design of cryptographic boolean functions with meta-heuristic algorithms

    EROL ÖZÇEKİÇ

    Doktora

    Türkçe

    Türkçe

    2024

    Bilgisayar Mühendisliği Bilimleri-Bilgisayar ve KontrolKarabük Üniversitesi

    Bilgisayar Mühendisliği Ana Bilim Dalı

    DOÇ. DR. HAKAN KUTUCU

    PROF. DR. SELÇUK KAVUT

  2. Farksal güç analizi saldırılarına dayanıklı döngüsel simetrik s-kutularının tasarımı

    Farksal güç anali̇zi̇ saldirilarina dayanikli döngüsel si̇metri̇k s-kutularinin tasarimi

    MUHAMMET ALİ EVCİ

    Yüksek Lisans

    Türkçe

    Türkçe

    2014

    Elektrik ve Elektronik MühendisliğiGebze Yüksek Teknoloji Enstitüsü

    Elektronik Mühendisliği Ana Bilim Dalı

    DR. SELÇUK KAVUT

  3. Çok genlikli minimum kaydırmalı anahtarlama için kafes kodlar

    Trellis codes for multi-amplitud minimum shift keying modulation

    İLKNUR AKKAYA

    Yüksek Lisans

    Türkçe

    Türkçe

    1994

    Elektrik ve Elektronik Mühendisliğiİstanbul Teknik Üniversitesi

    DOÇ.DR. H. ÜMİT AYGÖLÜ

  4. İçerisinde akışkan bulunan değişken yarıçaplı elastik tüplerde nonlineer dalga yayılımı

    Nonlinear wave propagation in fluid filled tapared elastic tubes

    ALİ ERİNÇ ÖZDEN

    Yüksek Lisans

    Türkçe

    Türkçe

    2005

    Matematikİstanbul Teknik Üniversitesi

    Matematik Mühendisliği Ana Bilim Dalı

    Y.DOÇ.DR. NALAN ANTAR