A survey on known algorithms in solving generalization birthday problem (K-list)
Genel doğum günü probleminin (K-liste) çözen bilinen algoritmalar üzerine bir araştırma
- Tez No: 324793
- Danışmanlar: PROF. DR. FERRUH ÖZBUDAK
- Tez Türü: Yüksek Lisans
- Konular: Matematik, Mathematics
- Anahtar Kelimeler: Doğum Günü Paradoksu, Kriptanaliz, Genel Doğum Günü Problemi, K-Ağaç Algoritmaları, Altküme Toplam Problemi, Birthday Paradox, Cryptanalysis, Generalized Birthday Problem, K-tree Algorithms, Subset Sum Problem
- 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ı: 59
Özet
Doğum günü paradoksu, kriptogra?k uygulamalardaki en önemli problemlerdendir. Doğum günü problemi, artan özet fonksiyonları, açık anahtar kriptogra?deki e- imzaları ve akan şifrelerdeki LFSR?ların az-ağırlıklı pariti kontrol denklemleri gibi sitemlere atak yapmada kullanılır. Wagner, k-boyutlu doğum günü problemini sunmuş ve formüle etmiştir, ayrıca problemi O(k m1=logk ) karmaşıklıkta çözen bir algoritma tasarlamı?tır. Genel doğum günü çözümleri Knapsack temelli sistemleri kırmada veya özet fonksiyonlarına çarpı?ma bulmada kullanılmıştır. NP- zor olduğuna inanılan n-boyutluKnapsack problemi genelleştirilmiş doğum günü algoritmaları ile çözülebilir. Bunun eş-problemi, Z/mZ kümesinde tanımlanan Altküme Toplam Problemidir. Problemi sı- nı?andırmadaki temel özellik yoğunluktur. Yoğunluk yeteri kadar küçük olduğundaproblem, en kısa latis problemine dönüşür ve problemin polinom zamanlı çözümü vardır. Listenin her eleman?na bir değişken atanmasıyla, bunların matris formunda ayrıştırılmasıyla ve matrisin her satırının bir denklem gibi düşünülmesiyle çok-değişkenli polinom denklem sistemi elde ederiz. Bu çeşit sistemlere bütün çözümler (örneğin: F4, F5, XL, sl) k-list problemine çözüm olabilir. Bu çalışmada k-list problemine çö- züm algoritmaların karmaşıklığını azaltmaya yönelik yaklaşımları ve yöntemleri inceleyeceğiz. Özellikle deği?ken sayısından fazla denklemin bulunduğu sistemlere Wolfve Thomea?nın tek çözüm getiren yöntemi F5 algoritmasının karmaşıklığını önemli ölçüde düşürmüştür. Ayrıca, onların grupları, özel dereceli tek-terimlileri ve küçük listelerin doğrusal denklemlerini kullanarak problemi çözmeye çalışıyor. Bu araştırma çalışmasında bütün önerilen yöntemleri göstereceğiz ve karşılaştıracağız.
Özet (Çeviri)
A well known birthday paradox is one the most important problems in cryptographic applications. Incremental hash functions or digital signatures in public key cryptography and low-weight parity check equations of LFSRs in stream ciphers are examples of such applications which bene?t from birthday problem theories to run their attacks.Wagner introduced and formulated the k-dimensional birthday problem and proposed an algorithm to solve the problem in O(k:m1 logk ) . The generalized birthday solutions used in some applications to break Knapsack based systems or collision ?nding in hash functions. The optimized birthday algorithms can solve Knapsack problems of dimension n which is believed to be NP-hard. Its equivalent problem is Subset Sum Problem ?nds the solution over Z=mZ. The main property for the classi?cation of the problem is density. When density is small enough the problem reduces to shortest lattice vectorproblem and has a solution in polynomial time. Assigning a variable to each element of the lists, decoding them into a matrix and considering each row of the matrix as an equation lead us to have a multivariate polynomial system of equations and all solution of this type can be a solution for the k- list problem such as F4; F5, another strategy called eXtended Linearization (XL) and sl. We discuss the new approaches and methods proposed to reduce the complexity of the algorithms. For particular cases in over-determined systems, more equations than variables, regarding to have a singlesolutions Wolf and Thomea work to make a gradual decrease in the complexity of F5. Moreover, his group try to solve the problem by monomials of special degrees and linear equations for small lists. We observe and compare all suggested methods in this survey.
Benzer Tezler
- Kaynak kısıtlı proje çizelgeleme probleminde tekrarsız kromozom destekli paralel genetik algoritma uygulaması
A parallel genetic algorithm application with nonrepetitive chromosome improvement for resource constrained project scheduling problem
ŞAFAK EBESEK
- Cisim genişlemeleri ve origami çizimleri
Field extensions and origami constructions
BURCU ŞANSAN
Yüksek Lisans
Türkçe
2019
Matematikİstanbul Teknik ÜniversitesiMatematik Mühendisliği Ana Bilim Dalı
DOÇ. DR. ERGÜN YARANERİ
- 600 MWe gücünde PWR tipi bir nükleer reaktör kalp öndizayn analizi
Başlık çevirisi yok
FARZAD REZAEİ BASHARAT
- Derivative free optimization methods: Application in stirrer configuration and data clustering
Türevsiz optimizasyon metotları: Karıştırıcı konfigürasyonları ve veri sınıflandırması uygulaması
BAŞAK AKTEKE
Yüksek Lisans
İngilizce
2005
MatematikOrta Doğu Teknik ÜniversitesiBilimsel Hesaplama Ana Bilim Dalı
PROF.DR. BÜLENT KARASÖZEN
- A Survey and applications in simulated annealing and nevral networks in combinatorial optimization
Başlık çevirisi yok
İSMAİL İLKAY BODUROĞLU
Yüksek Lisans
İngilizce
1989
Endüstri ve Endüstri MühendisliğiBoğaziçi ÜniversitesiDOÇ. DR. M. AKİF EYLER