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: Kriptografi, Polinom halkaları, Polinomlar, Toeplitz operatörleri, Cryptography, Polynominal rings, Polynomials, Toeplitz operators
- Yıl: 2022
- Dil: İngilizce
- Üniversite: Orta Doğu Teknik Üniversitesi
- Enstitü: Uygulamalı Matematik Enstitüsü
- Ana Bilim Dalı: Kriptografi Ana Bilim Dalı (disiplinlerarası)
- Bilim Dalı: Belirtilmemiş.
- Sayfa Sayısı: Belirtilmemiş.
Ö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ı (disiplinlerarası)
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ı (disiplinlerarası)
DOÇ. DR. OĞUZ YAYLA
- Mitral kapak prolapsusu olan çocuklarda kardiyak otonomik disfonksiyonun ve aritmi riskinin değerlendirilmesi
Evaluation of cardiac autonomic dysfunction and the risk of arrhythmia in children with mitral valve prolapse
ABDULLAH BİNDAL
Tıpta Uzmanlık
Türkçe
2022
Çocuk Sağlığı ve HastalıklarıTrakya ÜniversitesiÇocuk Sağlığı ve Hastalıkları Ana Bilim Dalı
DR. ÖĞR. ÜYESİ MURAT DEVECİ
- New algorithms and techniques for microprocessor-controlled PWM induction drives
Başlık çevirisi yok
OSMAN KÜKRER
Doktora
İngilizce
1987
Elektrik ve Elektronik MühendisliğiOrta Doğu Teknik ÜniversitesiElektrik-Elektronik Mühendisliği Ana Bilim Dalı
PROF. DR. H. BÜLENT ERTAN
- New algorithms for the bin packing problem
Başlık çevirisi yok
ALİ TAMER ÜNAL
Yüksek Lisans
İngilizce
1988
Endüstri ve Endüstri MühendisliğiBoğaziçi ÜniversitesiEndüstri Mühendisliği Ana Bilim Dalı
DOÇ.DR. GÜNDÜZ ULUSOY