YENİ VERİMLİ KARAKTERİSTİK ÜÇ POLİNOM ÇARPIMI ALGORİTMALARI VE NTRU PRIME’A UYGULAMALARI

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.Bazı kuantum-sonrası kriptografik protokoller karakteristik üç polinom çarpımı gerektirmektedir, 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 karakteristik üç 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.Ph.D. - Doctoral Progra