Computing cryptographic properties of Boolean functions from the algebraic normal form representation
Boole fonksiyonlarının kriptografik özelliklerinin cebirsel normal biçim gösteriminden hesaplanması
- Tez No: 324790
- Danışmanlar: DOÇ. DR. ALİ DOĞANAKSOY
- Tez Türü: Doktora
- Konular: Matematik, Mathematics
- Anahtar Kelimeler: Belirtilmemiş.
- Yıl: 2013
- Dil: İngilizce
- Üniversite: Orta Doğu Teknik Üniversitesi
- Enstitü: Uygulamalı Matematik Enstitüsü
- Ana Bilim Dalı: Kriptografi Ana Bilim Dalı
- Bilim Dalı: Belirtilmemiş.
- Sayfa Sayısı: 72
Özet
Boole fonksiyonları simetrik anahtarlı kriptosistemlerin tasarım ve analizinde önemli rol oynamanın yanı sıra kodlama teorisi gibi alanlarda uygulamaları olan bir araştırma alanıdır. Girdi sayısı fazla olan Boole fonksiyonları, kriptografik özelliklerin hesaplanması problemini beraberinde getirir. Bu özellikleri hesaplamanın geleneksel yolu, hesaplama ve hafıza kaynakları girdi sayısına üstel olarak bağlı olan dönüşümler gerektirir. Yüksek girdi sayılı Boole fonksiyonları genellikle cebirsel normal biçim (ANF) gösterimi ile ifade edilir. Bu tezde, ANF gösterimi verilen bir Boole fonksiyonunun ağırlığını ve doğrusallıktan sapma miktarını hesaplayan yöntemler araştırılmıştır. Bir Boole fonksiyonunun ANF katsayıları ve ağırlığı arasındaki ilişki Carlet ve Guillot tarafından gösterilmiştir. Bu ifade, ANF gösteriminde $p$ adet terim olan bir Boole fonksiyonunun ağırlığının $\mathcal{O}(2^p)$ işlemde hesaplanabilmesine olanak sağlamıştır. Bu çalışmada, ağırlık ifadesindeki gereksiz işlemlerden kaçınan daha verimli bir algoritma önerilmiştir. Ağırlık ifadesi genelleştirilerek, doğrusal fonksiyonlara uzaklığın bir formülü elde edilmiştir. Bu formül sayesinde bir Boole fonksiyonunun doğrusallıktan sapma miktarını ANF gösteriminden bulma problemi, ilgili bir ikili tamsayı programlama problemine indirgenmiştir. Bu yaklaşımla, yüksek girdi sayılı ve az sayıda terim içeren Boole fonksiyonlarının doğrusallıktan sapma miktarı makul sürelerde hesaplanabilmektedir.
Özet (Çeviri)
Boolean functions play an important role in the design and analysis of symmetric-key cryptosystems, as well as having applications in other fields such as coding theory. Boolean functions acting on large number of inputs introduces the problem of computing the cryptographic properties. Traditional methods of computing these properties involve transformations which require computation and memory resources exponential in the number of input variables. When the number of inputs is large, Boolean functions are usually defined by the algebraic normal form (ANF) representation. In this thesis, methods for computing the weight and nonlinearity of Boolean functions from the ANF representation are investigated. The relation between the ANF coefficients and the weight of a Boolean function was introduced by Carlet and Guillot. This expression allows the weight to be computed in $\mathcal{O}(2^p)$ operations for a Boolean function containing $p$ monomials in its ANF. In this work, a more efficient algorithm for computing the weight is proposed, which eliminates the unnecessary calculations in the weight expression. By generalizing the weight expression, a formulation of the distances to the set of linear functions is obtained. Using this formulation, the problem of computing the nonlinearity of a Boolean function from its ANF is reduced to an associated binary integer programming problem. This approach allows the computation of nonlinearity for Boolean functions with high number of input variables and consisting of small number of monomials in a reasonable time.
Benzer Tezler
- Kardiyopulmoner bypass ile açık kalp cerrahisi uygulanan hastalarda orta ve hafif hipotermik bypass yöntemlerinin neutrophıl gelatınase assocıated lıpocalın (NGAL), cystatın c ve near ınfrared spectroscopy (NIRS) yöntemi ile ölçülen renal perfüzyon üzerine etkilerinin karşılaştırılması
Comparing the effects of mild and moderate hypothermia on renal perfusion evaluated with neutrophil gelatinase associated lipocalin, cystatin c and near-infrared spectroscopy in patients undergoing cardiopulmonary bypass graft surgery
SERKAN YILDIRIM
Tıpta Uzmanlık
Türkçe
2014
Göğüs Kalp ve Damar CerrahisiSelçuk ÜniversitesiKalp ve Damar Cerrahisi Ana Bilim Dalı
DOÇ. DR. MEHMET ALKILIÇ HORASANI ÖÇ
- Fuzûlî'nin Sıhhat u Maraz'ı ile Derviş Siyahî'nin Mecma'-ı Tıbb'ında Ahlât-ı Erbaanın İşlenişi
Discussing of Ahlat-ı Erbaa at Fuzuli's Sıhhat u Maraz an Derviş Siyahi's Mecma-ı Tıbb
ÖMER GÖK
Yüksek Lisans
Türkçe
2013
Deontoloji ve Tıp TarihiKırıkkale ÜniversitesiTürk Dili ve Edebiyatı Ana Bilim Dalı
PROF. DR. MUHİTTİN ELİAÇIK
- Erol Akyavaş'ın gelenekle somutlaşan resimlerinde karşılaştırmalı kompozisyon çözümlemeleri
Comparative composition analysis in Erol Akyavaş's tradation enbodied paintings
AYŞE YETGİN
- Elektif kolonoskopi vakalarında sedasyon-analjezi: Ketamin, fentanil, meperidin'in karşılaştırılması
Sedation and analgesia in electi̇ve colonoscopy procedure; comparing to ketami̇ne, fentanyl and meperi̇di̇ne
SEÇKİN ÖZOZAN
Tıpta Uzmanlık
Türkçe
2016
Anestezi ve ReanimasyonSağlık BakanlığıAnesteziyoloji ve Reanimasyon Ana Bilim Dalı
UZMAN ŞENAY GÖKSU TOMRUK
- Klon ve normal sığır embriyo plasentalarında insülin benzeri büyüme faktör-ı (IGF-I), vasküler endotelyal büyüme faktör (VEGF) ve nöronal hücre adhezyon molekül (NCAM) ekspresyonun immunositokimyasal ve moleküler tekniklerle incelenmesi
Evaluation of expression of insulin-like growth factor-i (IGF-I), vascular endothelial growth factor (VEGF) and neuronal cell adhesion molecule (NCAM) by immunocytochemical and molecular techniques in cloned and normal bovine placentas
FATİH KARAKAYA
Yüksek Lisans
Türkçe
2013
BiyoteknolojiKocaeli ÜniversitesiHistoloji ve Embriyoloji Ana Bilim Dalı
PROF. DR. HAKKI DALÇIK
PROF. DR. SEZEN ARAT