New TMVP-based multiplication algorithms for polynomial quotient rings and application to post-quantum cryptography
Polinom halkaları için yeni TMVP-tabanlı çarpım algoritmaları ve quantum-sonrası kriptografiye uygulamaları
- Tez No: 750001
- Danışmanlar: PROF. 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ı: 112
Özet
Kuantum bilgisayarlara karşı güvenli kriptografi araştırma alanlarından biri kafes tabanlı kriptografidir. Kafes tabanlı sistemlerin birçoğu, polinom bölüm halkalarında çarpma için verimli algoritmalara ihtiyaç duyar. Çarpma için bilinen en hızlı algoritma, halkanın parametrelerinde modülün asal olması gibi belirli kısıtlamalar gerektiren Sayı Kuramsal Dönü¸ sümdür (NTT). Bu kısıtlamalara uymayan bazı şemalar için doğrudan NTT uygulaması bir seçenek değildir; örneğin, ikinin kuvveti bir modül kullanan PQC standardizasyon yarışmasının iki finalisti Saber ve NTRU gibi. Toom-Cook ve Karatsuba, NTT direkt uygulanamadığında en yaygın kullanılan çarpma algoritmalarıdır. NTT'ye uygun olmayan halkalarda, modüler indirgeme gerektirmeyen daha büyük parametreler ile NTT kullanımına olanak veren bir yöntem önerilmiş olsa da, NTT olmayan verimli çarpma algoritmaları geliştirmek de bu halkalardaki çarpma işlemini iyileştirebilir. Bu tezde, kuantum-sonrası kriptografik (PQC) sistemler için Toeplitz Matris-Vektör Çarpımı (TMVP) tabanlı çarpma algoritmaları geliştirmeye odaklandık. İlk olarak, beş ve yedi çarpma gerektiren yeni üçlü ve dörtlü TMVP formüllerini önerdik. Uygulama için Saber ve NTRU şemalarını seçtik. Saber ve NTRU'nun tanımlandığı halkalar için yeni dörtlü formülü kullanarak TMVP tabanlı çarpma algoritmaları geliştirdik. Ayrıca, Saber için geliştirilen algoritmanın iyileştirilmiş bir versiyonunu sunduk ve NTRU şemasındaki çarpma işlemlerinde TMVP formüllerini kullanabilmek için bir doldurma yöntemi önerdik. Ayrıca, önerilen algoritmaları, PQC adaylarının mikroişlemciler üzerinde değerlendirilmesi için NIST tarafından önerilen platform olan ARM Cortex-M4 üzerinde gerçekledik. Performans ve hafıza kullanımını, literatürdeki tüm Toom gerçeklemelerine kıyasla iyileştirdik. Ayrıca, TMVP tabanlı algoritmaların, NTRU'nun üç parametre seti için NTT'den daha hızlı olduğunu ve tümü için hafıza kullanımını azalttığını gözlemledik. Algoritmalarımızın şemalar üzerindeki etkisini görmek için, kodlarımızı literatürdeki en gelişmiş Saber ve NTRU gerçeklemelerine entegre ettik. Saber için önerilen algoritmamız, Toom yöntemine kıyasla performansta %18,6'ya ve bellek tüketiminde %44.2'ye varan iyileştirmeler sağlamıştır. NTRU'nun tüm parametreleri için, hafıza kullanımını Toom'a kıyasla %5,9-%20,9 ve NTT'ye kıyasla %5,1-%19,3 arasında azalttık. Ayrıca, tüm parametreler için Toom metoduna kıyasla %4.4-%17.5 arasında performans artışı gözlemledik. NTRU'nun bir tanesi dışındaki parametreleri için, algoritmalarımız NTT yönteminden daha iyi performans göstermiştir. Ayrıca, kare olmayan TMVP hesaplamaları için yeni formüller sunduk ve bunları kullanarak yeni TMVP formülleri türetmek için bir yaklaşım önerdik. Önerilen formüllerin aritmetik karmaşıklık hesaplamaları ve teorik verimlilik karşılaştırmaları da bu tezde sunulmaktadır.
Özet (Çeviri)
One of the quantum-safe cryptography research areas is lattice-based cryptography. Most lattice-based schemes need efficient algorithms for multiplication in polynomial quotient rings. The fastest algorithm known for multiplication is the Number Theoretic Transform (NTT), which requires certain restrictions on the parameters of the ring, such as prime modulus. Direct NTT application is not an option for some schemes that do not comply with these restrictions, e.g., the two finalists of the PQC standardization competition, Saber and NTRU, which use a power-of-two modulus. Toom-Cook and Karatsuba are the most commonly used non-NTT multiplication algorithms. Even though a method of using NTT in NTT-unfriendly rings with larger parameters that prevent any modular reduction on the original result is proposed, developing non-NTT multiplication algorithms can also improve the efficiency of multiplication in such rings. In this thesis, we focused on developing Toeplitz Matrix-Vector Product (TMVP) based multiplication algorithms for PQC schemes. First, we propose new three- and four-way TMVP split formulas with five and seven multiplications. We choose Saber and NTRU schemes for our case study. We develop TMVP-based multiplication algorithms using the new four-way formula for the rings on which Saber and NTRU are defined. We also propose an improved version of the algorithm for Saber and present a padding method for NTRU to utilize TMVP split formulas. Moreover, we implement the proposed algorithms on ARM Cortex-M4, which NIST recommends as an evaluation platform for PQC candidates on microprocessors. We improve performance and stack memory consumption compared to all Toom imple- mentations. We also observe that our TMVP-based algorithms are faster than NTT for three of the parameter sets of NTRU, and they reduce the stack usage for all. We integrate our codes into state-of-the-art implementations of Saber and NTRU in the literature to see the effect of our algorithm on the total performance of the schemes. For Saber, our algorithm achieves improvements up to 18.6% in performance and up to 44.2% in memory consumption compared to the Toom method. For all parameter sets of NTRU, we reduce stack usage between 5.9%−20.9% compared to Toom and 5.1% − 19.3% compared to NTT. Moreover, we observe performance improvements between 4.4%−17.5% compared to Toom for all parameter sets. Except for one of the parameter sets of NTRU, our algorithms outperform the NTT method. Furthermore, we propose new formulas for non-square TMVP calculations and a new approach for deriving new TMVP split formulas using the non-square ones. The arithmetic complexity calculations and theoretical efficiency comparisons are also presented in this thesis.
Benzer Tezler
- Efficient implementation of TMVP-based prime field multiplication and its applications to ecc
TMVÇ tabanlı verimli asal cisim çarpması gerçeklemesi ve eliptik eğri kriptografiye uygulamaları
HALİL KEMAL TAŞKIN
Doktora
İngilizce
2019
MatematikOrta Doğu Teknik ÜniversitesiKriptografi Ana Bilim Dalı
DOÇ. DR. MURAT CENK
- A new efficient TMVP algorithm and an application for post-quantum cryptography
Yeni ve verimli bir TMVP algortitması ve kuantum ertesi kriptografiye bir uygulaması
ANIL BURAK GÖKCE
Yüksek Lisans
İngilizce
2023
Bilgisayar Mühendisliği Bilimleri-Bilgisayar ve KontrolOrta Doğu Teknik ÜniversitesiKriptografi Ana Bilim Dalı
DOÇ. DR. OĞUZ YAYLA
- Comparison of New York, stock exchange, London stock exchange and Istanbul stock exchange: Cost focus
New York, Londra ve İstanbul borsalarının karşılaştırılması: Maliyet odaklı
MUSTAFA YÜCEL ÇAKIR
Yüksek Lisans
İngilizce
1997
İşletmeMarmara Üniversitesiİşletme (İngilizce) Ana Bilim Dalı
PROF. DR. DOĞAN ALTUNER
- Yeni dünya düzeni ve Türkiye'de iletişim özgürlüğü: Türk yazılı basını üzerine bir inceleme
New world order and freedom of communication in Turkey: An investigation of Turkish press
GÜL KARAGÖZ
Yüksek Lisans
Türkçe
1999
Siyasal BilimlerAnkara ÜniversitesiKamu Yönetimi ve Siyaset Bilimi Ana Bilim Dalı
PROF.DR. ÖMÜR SEZGİN
- New historicism in theory and fiction: A study of three contemporary British novels (Graham Swift's Waterland, A.S. Byatt's Possession and Derek Beaven's Newton's Niece)
Edebiyat kuramı ve romanda yeni tarihselcilik: Üç çağdaş İngiliz romanı üzerine bir çalışma (Graham Swift'in Waterland'ı, A.S. Byatt'ın Possessian'ı ve Derek Beaven'ın Newton's Niece'i)
AYTÜL ÖZÜM
Doktora
İngilizce
1999
İngiliz Dili ve EdebiyatıHacettepe Üniversitesiİngiliz Dili ve Edebiyatı Ana Bilim Dalı
DOÇ. DR. SERPİL OPPERMANN