Efficient batch algorithms for the post-quantum Crystals dilithium signature scheme and Crystals Kyber encryption scheme
Tezin Türü: Doktora
Tezin Yürütüldüğü Kurum: Orta Doğu Teknik Üniversitesi, Uygulamalı Matematik Enstitüsü, Kriptografi Anabilim Dalı, Türkiye
Tezin Onay Tarihi: 2024
Tezin Dili: İngilizce
Öğrenci: NAZLI DENİZ TÜRE
Asıl Danışman (Eş Danışmanlı Tezler İçin): Oğuz Yayla
Eş Danışman: Murat Cenk
Açık Arşiv Koleksiyonu: AVESİS Açık Erişim Koleksiyonu
Ö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.