Efficient batch algorithms for the post-quantum Crystals dilithium signature scheme and Crystals Kyber encryption scheme
Crystals dilithium imza şeması ve Crystals Kyber şifreleme şeması için verimli toplu kuantum ertesi algoritmalar
- Tez No: 904599
- Danışmanlar: DOÇ. DR. OĞUZ YAYLA, PROF. DR. MURAT CENK
- Tez Türü: Doktora
- Konular: Bilim ve Teknoloji, Matematik, Science and Technology, Mathematics
- Anahtar Kelimeler: Belirtilmemiş.
- Yıl: 2024
- 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ı: 155
Özet
Dijital imzalar kimlik doğrulama ve veri bütünlüğü sağlarlar ve bilgi teknolojileri, finans, eğitim, hukuk gibi birçok alanda yaygın olarak kullanılırlar. Kullanıcı ile sunucu arasındaki iletişimlerde kimlik doğrulama amaçlı kullanılarak sunucuların siber saldırılara karşı güvenliklerinin sağlanması konusunda da oldukça önemlidirler. Diğer bir yandan şifreleme ise veri güvenliğini sağlamak amacıyla güvenli iletişim, bulut ve veritabanı güvenliği gibi birçok alanda kullanılmaktadır. Dijital imzalar ve şifreleme mekanizmalarında sıklıkla açık anahtarlı kriptosistemler kullanılır. Açık anahtarlı kriptosistemlerin güvenliği ise tam sayılarda çarpanlara ayırma ve ayrık logaritma problemi gibi çözümü zor matematiksel problemlere dayanmaktadır. P. Shor (1999), güvenlikleri ayrık logaritma ve tam sayılarda çarpanlara ayırma problemlerine dayanan kriptosistemlerin, gelişmiş kuantum bilgisayarlar kullanılarak kırılabileceğini göstermiştir. Güvenliklerini kaybedecek olan algoritmaların, yeni nesil kuantum güvenli algoritmalar ile değiştirilmesi için NIST (Ulusal Standartlar ve Teknoloji Enstitüsü, ABD) tarafından kuantum sonrası standartlaşma süreci düzenleşmiştir. Bunun sonucunda Crystals Dilithium, Falcon ve SPHINCS+ dijital imza standartları, Crystals Kyber ise şifreleme/anahtar kapsülleme standardı olarak seçilmiştir. Bu çalışmada, NIST'in (Ulusal Standartlar ve Teknoloji Enstitüsü, ABD) kuantum ertesi kriptografi dijital imza standardı olarak belirlemiş olduğu Crystals Dilithium algoritması ile toplu imza üretimi ve bir kullanıcıdan gelen imzaların doğrulaması, kuantum ertesi şifreleme standardı olarak belirlenmiş olan Crystals Kyber ile bir kullanıcı için toplu şifreleme üzerine yoğunlaşılmıştır. Dilithium ve Kyber'ın barındırdığı en önemli işlemlerden biri de; girdileri polinom olan matris ve vektörlerin çarpımıdır. m>1 olmak üzere m adet imza klasik Dilithium yöntemi ile üretildiğinde ya da doğrulandığında (m adet mesaj klasik Kyber ile şifrelendiğinde) m adet benzer çarpım gerekmektedir. Bu tezde, Dilithium ile m imzayı üretmek/doğrulamak için üçten büyük matrislerde ve Kyber ile m mesajı şifrelemek için ikiden büyük boyutlu matrislerde verimli matris çarpımlarının kullanılabileceği gösterilmiştir. Bu sebeple, Dilithium imza üretimi, doğrulama ve Kyber şifreleme algoritmaları analiz edilmiştir. Bu çalışmada, birden fazla mesaj veya imza için ayrı ayrı gerçekleştirilen işlemlerin, toplu şekilde yapılabilmesi için yeni algoritmalar tasarlaşmıştır. Bu amaçla, bu algoritmalardaki matris-vektör çarpımları, matris-matris çarpımlarına dönüştürülmüş ve yeni toplu Dilithium imza üretimi/doğrulama ve toplu Kyber şifreleme algoritmaları tasarlanmıştır. Ayrıca, verimli toplu Dilithium imza üretim algoritmasının tek bir imzanın üretilmesinde kullanılabileceği de gösterilmiştir. Bu, olasılık ve verimlilik analizleri ile doğrulanmıştır. Yeni toplu algoritmalar, orijinal Dilithium ve Kyber'in güvenliğini sağlayan bileşenlere sahiptir ve güvenlik açıklarına neden olmadan toplu imzalama/doğrulama ve şifrelemeye olanak sağlar. Matris-vektör çarpımlarını matris-matris çarpımlarına dönüştürerek, bu sistemlerde verimli değişmeli veya değişmeli olmayan matris-matris çarpım algoritmalarının kullanılmasına imkan tanır. Elde edilen verimlilik, belirli bir mimari, cihaz veya platformdan bağımsızdır ve matematiksel iyileştirmelere dayanmaktadır. Tasarlanan toplu algoritmalar, herhangi bir toplu işlem boyutunun seçilmesine ve uygun matris-matris çarpım tekniğinin uygulanmasına olanak sağlar. Bu bağlamda, farklı toplu işlem boyutlarına göre hem toplu hem de tekli imzalar için Dilithium imza algoritmasının kullanımı üzerine olasılık hesaplamaları yapılmış ve seçilen matris-matris çarpım tekniklerine dayalı olarak verimlilik yüzdeleri elde edilmiştir. Ayrıca, değişen toplu işlem boyutları için uygun matris-matris çarpım yöntemleri aracılığıyla toplu Kyber şifrelemesi ve Dilithium doğrulamasının sağladığı iyileştirme yüzdeleri hesaplanmıştır. Teorik hesaplamaları örneklemek amacıyla, örnek toplu işlem değerleri seçilmiş ve uygun matris-matris çarpım yöntemleri belirlenmiştir. Matrislerin boyutlarına göre, Dilithium ve Kyber'ın üç güvenlik seviyesi için çarpım formülleri elde edilmiştir. Hesaplamaları test etmek amacıyla, bu çalışmada tasarlanan toplu Dilithium imzalama, doğrulama ve Kyber şifreleme algoritmaları C programlama dilinde gerçeklenmiştir. Türetilen matris-matris çarpım formülleri de, Kyber ve Dilithium'un altyapısına uyacak şekilde C dilinde gerçeklenmiş ve yeni toplu algoritmalara entegre edilmiştir. Yeni algoritmalar ile referans algoritmalar arasında verimlilik karşılaştırmaları yapılmıştır. Sonuç olarak, Dilithium'un imzasının üç farklı güvenlik seviyesinde aritmetik karmaşıklıkta sırasıyla %28.1, %33.3 ve %31.5 oranında iyileşmeler gözlemlenmiştir. Verimli matris çarpım yöntemi kullanılan toplu Dilithium imza algoritması, üç güvenlik seviyesi için CPU döngü sayılarında sırasıyla %34.22, %17.40 ve %10.15 iyileştirmeler sağlamıştır. Toplu Dilithium imza üretimi için kullanılan çarpım formülleri, aynı zamanda toplu Dilithium doğrulaması için de kullanılmıştır. Üç farklı güvenlik seviyesi için aritmetik karmaşıklıkta sırasıyla %28.13, %33.33 ve %31.25 oranında iyileşmeler gözlemlenmiştir. Ayrıca, üç güvenlik seviyesi için CPU döngü sayıları açısından sırasıyla %49.88, %56.60 ve %61.08 iyileşmeler elde edilmiştir. Verimli çarpım algoritmaları kullanılan toplu Kyber şifrelemesi uygulandığında, aritmetik karmaşıklıkta %12.50, %22.22 ve %28.13 oranında iyileşmeler ile birlikte, üç güvenlik seviyesi için CPU döngü sayılarında %22.34, %24.07 ve %30.83 oranında iyileşmeler gözlemlenmiştir.
Özet (Çeviri)
Digital signatures ensure authenticity and data integrity and are widely utilized in various fields such as information technologies, finance, education, and law. They are crucial in securing servers against cyber attacks by authenticating connections between clients and servers. Additionally, encryption is used in many areas, such as secure communication, cloud, server and database security to ensure data confidentiality. Public-key cryptosystems are widely used as digital signature and encryption mechanisms. The security of public-key cryptosystems is based on difficult mathematical problems such as the integer factorization problem and the discrete logarithm problem. Security of the public-key cryptosystems is based on solving challenging mathematical problems like the discrete logarithm and integer factorization problems. P. Shor (1999) has shown that high-capacity quantum computers can be used to break cryptosystems whose security depends on solving the discrete logarithm problem and the integer factorization problem. The post-quantum standardization procedure has been organized by NIST (National Institute of Standards and Technology, USA) to replace cryptographic algorithms that will lose their security with the next-generation quantum-secure algorithms. Following this procedure, Crystals Dilithium, Falcon, and SPHINCS+ are chosen as the digital signature standards, and Crystals Kyber is chosen as the encryption/KEM standard. This work focuses on efficient batch signature generation with Dilithium, batch verification of signatures from the same user using Crystals Dilithium (NIST's post-quantum digital signature standard), and batch encryption to a single user with Crystals Kyber (NIST's post-quantum encryption/KEM standard). One of the main operations of Dilithium and Kyber is the matrix-vector product with polynomial entries. So, the naive approach to generate/verify m signatures with Dilithium (or encrypt m messages with Kyber) where m>1 is to perform m such multiplications. In this thesis, we propose to use efficient matrix multiplications of sizes greater than three to generate/verify m signatures with Dilithium and greater than two to encrypt m messages with Kyber. To this end, Dilithium signature generation, verification, and Kyber encryption algorithms are analyzed. In this study, individual operations for multiple messages or signatures are redesigned to allow for batch processing. For this purpose, the matrix-vector multiplications contained in these algorithms are converted into matrix-matrix multiplications, and the new batch Dilithium signature generation/verification and batch Kyber encryption algorithms are designed. Furthermore, it is shown that the efficient batch Dilithium signature generation algorithm can be used for the generation of a single signature. This is confirmed through probability and efficiency analyses. New batch algorithms have components that ensure the security of the original Dilithium and Kyber and allow batch signing/verification and encryption without causing security vulnerabilities. By transforming matrix-vector multiplications into matrix-matrix multiplications, efficient non-commutative or commutative matrix-matrix multiplication algorithms are allowed to be used in these systems. The efficiency achieved is independent of any specific architecture, device, or platform and is based on mathematical improvements. The designed batch algorithms provide the opportunity to select any batch size and apply the suitable matrix-matrix multiplication technique. In this context, probability computations are made for the usability of the Dilithium signature algorithm in both multiple and single signatures according to various batch sizes, and efficiency percentages are obtained based on the selected matrix-matrix multiplication techniques. Furthermore, improvement percentages provided by batch Kyber encryption and Dilithium verification are computed via matrix-matrix multiplication methods appropriate for changing batch sizes. To exemplify the theoretical calculations made, sample batch values are selected, and suitable matrix-matrix multiplication methods are determined. According to the dimensions of the matrices, multiplication formulas are derived for three security levels of Dilithium and Kyber. To test the calculations, the batch Dilithium signing, verification, and Kyber encryption algorithms designed within this study are implemented in the C programming language. The derived matrix-matrix multiplication formulas are also implemented in C to fit the infrastructure of Kyber and Dilithium and integrated into the batch algorithms. Efficiency comparisons are made between the new algorithms and reference algorithms. As a result, improvements up to 28.1%, 33.3%, and 31.5% in the arithmetic complexities are observed at three different security levels of Dilithium's signature, respectively. The batch Dilithium signature algorithm with an efficient matrix-multiplication method provides 34.22%, 17.40%, and 10.15% improvements on CPU cycle counts for three security levels. The multiplication formulas used for batch Dilithium signature generation are also applied for batch Dilithium verification. At three different levels of security, improvements in the arithmetic complexity are observed of up to 28.13%, 33.33%, and 31.25%. Furthermore, 49.88%, 56.60%, and 61.08% improvements on CPU cycle counts for three security levels are achieved, respectively. As a result of implementing Kyber Batch Encryption with efficient multiplication algorithms, 12.50%, 22.22%, and 28.13% improvements on arithmetic complexity, as well as 22.34%, 24.07%, and 30.83% improvements on CPU cycle counts, are observed for three security levels.
Benzer Tezler
- Constructing peptide (GEPI)-protein molecular hybrids by using genetic engineering methods for materials and medical applications.
Malzeme ve medikal uygulamalar için gen mühendisliği yoluyla peptid (GEPI)-protein hibritlerin oluşması.
DENİZ ŞAHİN
Doktora
İngilizce
2011
Biyomühendislikİstanbul Teknik Üniversitesiİleri Teknolojiler Ana Bilim Dalı
PROF. DR. CANDAN TAMERLER
PROF. DR. MEHMET SARIKAYA
- Tailored indirect algorithms for efficient on-line optimization of batch and semi-batch processes
Kesikli ve yari kesikli süreçlerin çevrimiçi optimizasyonuna yönelik özel yapimli dolayli algoritmalar
ERDAL AYDIN
Doktora
İngilizce
2018
Endüstri ve Endüstri MühendisliğiOtto von Guericke UniversityKimya ve Süreç Mühendisliği Ana Bilim Dalı
PROF. DR. KAI SUNDMACHER
- New approaches for channel estimation in wireless communications
Telsiz haberleşmede kanal kestirimi için yeni yaklaşımlar
HABİB ŞENOL
Doktora
İngilizce
2006
Elektrik ve Elektronik MühendisliğiIşık ÜniversitesiElektronik Mühendisliği Ana Bilim Dalı
DOÇ. DR. HAKAN A. ÇIRPAN
DOÇ. DR. ULUĞ BAYAZIT
- İşaretlerin seyrek gösterilimi için sözlük tasarımı
Dictionary design for sparse signal representation
EMRAH YAVUZ
Yüksek Lisans
Türkçe
2011
Elektrik ve Elektronik Mühendisliğiİstanbul Teknik ÜniversitesiElektronik ve Haberleşme Mühendisliği Ana Bilim Dalı
YRD. DOÇ. DR. ENDER METE EKŞİOĞLU
- Hücresel imalatın başlangıç aşamaları için uzman sistem yaklaşımı
An Expert systems approach to the early stages of cellular manufacturing systems design
UFUK CEBECİ