New efficient characteristic three polynomial multiplication algorithms and their applications to NTRU prime
Yeni verimli karakteristik üç polinom çarpımı algoritmaları ve NTRU prime'a uygulamaları
- Tez No: 708796
- Danışmanlar: DOÇ. DR. MURAT CENK
- Tez Türü: Doktora
- Konular: Matematik, Mathematics
- Anahtar Kelimeler: Belirtilmemiş.
- Yıl: 2022
- 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ı: 110
Özet
Bazı kuantum-sonrası kriptografik protokoller karakteristik üç polinom çarpımı gerektirmektedir, böylece bu tarz çarpma algoritmalarının verimliği son zamanlarda daha çok önem kazanmaktadır. Bu tezde karakteristik üç cisimlerinde dört yeni polinom çarpımı algoritması tasarlanmıştır ve bunların şu dönemdeki en son yöntemlerden daha verimli oldukları gösterilmiştir. Öncelikle iyi bilinen okulkitabı yöntemi, Karatsuba 2-yönlü ve 3-yönlü ayrılmalı metotları, Bernstein'ın 3-yönlü ayrılmalı metodu, Toom-Cook benzeri formüller ve son zamanlardaki diğer algoritmalar analiz edilmiştir. Çeşitli 4, 5, veya fazla ayrılmalı algoritma versiyonlarına sahip olan ikili (karakteristik iki) cisimlerden farklı olarak, karakteristik üç cisimlerinde hiç 4-yönlü veya 5-yönlü ayrılmalı çarpma algoritmalarının olmadığı farkedilmiştir. Sonrasında F_9'da interpolasyon tekniği kullanılarak geliştirilen üç farklı 4-yönlü ayrılmalı polinom çarpımı algoritması tasarlanmıştır. Dahası, yeni bir 5-yönlü ayrılmalı polinom çarpımı algoritması tasarlanmış ve sonrasında tüm bahsigeçen yöntemlerin aritmetik karmaşıklığı ve implementasyon sonuçları karşılaştırılmıştır. Yeni 4-yönlü ve 5-yönlü ayrılmalı algoritmaların, 1280 girdi boyutu için, F_9 üzerindeki çarpmaların aritmetik karmaşıklığında 48.6% ve F_3 üzerindeki çarpmaların aritmetik karmaşıklığında da 26.8% oranında düşüş sağladığı gösterilmiştir. Dahası, yeni 4-yönlü ve 5-yönlü ayrılmalı algoritmalar şu dönemdeki en son yöntemlere kıyasla daha hızlı implementasyon sonuçları sağlamıştır. Tasarlanan metotlar, bir anahtar kapsülleme mekanizması olarak Bernstein et al. tarafından NIST PQC Standartlaştırma Süreci'ne sunulan ve kapsülden çıkarma aşamasında karakeristik üç polinom çarpımı gerektiren, NTRU Prime protokolüne uygulanmıştır. Yeni metotların C'de implementasyonu yapılmış ve NTRU Prime anahtar çıkarmasındaki karakteristik üç polinom çarpımı adımında strup653 için 26.85% 'lik bir hızlanma ve strup761 için de 35.52%'lik bir hızlanma gözlenmiştir.
Özet (Çeviri)
Some of the post-quantum cryptographic protocols require polynomial multiplication in characteristic three fields, thus the efficiency of such multiplication algorithms gain more importance recently. In this thesis, we propose four new polynomial multiplication algorithms in characteristic three fields and we show that they are more efficient than the current state-of-the-art methods. We first analyze the well-known algorithms such as the schoolbook method, Karatsuba 2-way and 3-way split methods, Bernstein's three 3-way split method, Toom-Cook-like formulas, and other recent algorithms. We realize that there are not any 4-way or 5-way split multiplication algorithms in characteristic three fields unlike the binary (characteristic two) fields which have various 4, 5, or more split versions. We then propose three different 4-way split polynomial multiplication algorithms which are derived by using the interpolation technique in F_9. Furthermore, we propose a new 5-way split polynomial multiplication algorithm and then compare the arithmetic complexities and the implementation results for all of the aforementioned methods. We show that the new 4-way and 5-way split algorithms provide a 48.6% reduction in the arithmetic complexity for multiplication over F_9 and a 26.8% reduction for multiplication over F_3 for the input size 1280. Moreover, the new 4-way and 5-way algorithms yield faster implementation results compared to the current state-of-the-art methods. We apply the proposed methods to NTRU Prime protocol, a key encapsulation mechanism, submitted to NIST PQC Standardization Process by Bernstein et al., which executes characteristic three polynomial multiplication in its decapsulation stage. We implement the new methods in C and observe a 26.85% speedup for stnrup653 and a 35.52% speedup for sntrup761 in the characteristic three polynomial multiplication step of the NTRU Prime decapsulation.
Benzer Tezler
- Determination of parameter regions for diagonal dominance and stability of MIMO systems
MIMO sistemlerin köşegen baskınlığı ve kararlılığı için parametre bölgelerinin belirlenmesi
İLHAN MUTLU
Doktora
İngilizce
2017
Bilgisayar Mühendisliği Bilimleri-Bilgisayar ve Kontrolİstanbul Teknik ÜniversitesiKontrol ve Otomasyon Mühendisliği Ana Bilim Dalı
PROF. DR. MEHMET TURAN SÖYLEMEZ
- Stability analysis of multiple time-delay systems and design of time-delay filters
Çoklu zaman gecikmeli sistemlerin kararlılık analizi ve gecikme tabanlı filtre tasarımı
BARAN ALİKOÇ
Doktora
İngilizce
2017
Bilgisayar Mühendisliği Bilimleri-Bilgisayar ve Kontrolİstanbul Teknik ÜniversitesiKontrol ve Otomasyon Mühendisliği Ana Bilim Dalı
YRD. DOÇ. DR. ALİ FUAT ERGENÇ
- Katsayı diyagram yöntemi ve uygulamaları
The coefficient diagram method and its applications
SELMAN FATİH AVŞAR
Yüksek Lisans
Türkçe
2012
Elektrik ve Elektronik Mühendisliğiİstanbul Teknik ÜniversitesiKontrol ve Otomasyon Mühendisliği Ana Bilim Dalı
DOÇ. DR. MEHMET TURAN SÖYLEMEZ
- İç mekan konum belirleme sistemlerinde konum kestirim doğruluğunun yükseltilmesi
Improvement of the location estimation accuracy in indoor localization systems
EMRE DORUK
Yüksek Lisans
Türkçe
2021
Bilgisayar Mühendisliği Bilimleri-Bilgisayar ve Kontrolİstanbul Teknik ÜniversitesiKontrol ve Otomasyon Mühendisliği Ana Bilim Dalı
DOÇ. DR. OSMAN KAAN EROL
DOÇ. DR. TANER ARSAN
- Kafes kodlamalı-dik kısmi yanıtlı sistemlerin )QPR-TCM) hata başarım analizi
Performance analysis of quadrature partiel response trellis coded modulation
OSMAN NURİ UÇAN
Doktora
Türkçe
1995
Elektrik ve Elektronik Mühendisliğiİstanbul Teknik ÜniversitesiPROF.DR. ERDAL PANAYIRCI