Halka-LWE ve Modül Kafesleri

Standart LWE, büyük matris-vektör çarpımları gerektirir ve bu da büyük anahtar boyutlarına yol açar. Lyubashevsky, Peikert ve Regev tarafından 2010 yılında ortaya atılan Ring-LWE, vektör ve matrislerin yerine R_q = Z_q[X]/(f(X)) halkasındaki polinomları kullanır. Bu yapılı ortam, çok daha küçük anahtarlar ve daha hızlı aritmetik işlemler sağlar; böylece Ring-LWE, gerçek dünyadaki kafes kriptografisinin pratik temeli hâline gelir.

Ring-LWE'de kullanılan f(X) polinomu genellikle f(X) = X^n + 1 biçimindedir; burada n, 2'nin bir kuvvetidir. Bu, 2n'inci siklotomik polinomdur. Z üzerinde indirgenemez olması, R_q halkasının iyi cebirsel özelliklere sahip olmasını sağlaması ve verimli çarpma için Number Theoretic Transform (NTT) kullanımına olanak tanıması nedeniyle seçilir. Siklotomik halkalar kapsamlı biçimde incelenmiş olup güvenli olduklarına inanılmaktadır.

Ring-LWE'de gizli s, R_q içinde bir polinomdur ve örnekler (a, b = a*s + e) biçimindedir; burada a, halkadan eşit olasılıklı rastgele seçilen bir eleman, e ise küçük bir hata polinomudur. Saldırgan bu tür çok sayıda örnek görür ve s'yi geri elde etmeli veya bunları eşit olasılıklı örneklerden ayırt etmelidir. Zorluk, ideal kafeslerdeki en kötü durum problemlerinden bir indirgemeye sahip olan Ring-LWE varsayımına dayanır.

Ring-LWE, saldırgan açısından daha zor olmakla birlikte, temel LWE'den biraz farklı bir güvenlik indirgemesine de sahiptir. İndirgeme, rastgele kafeslerden değil, ideal kafeslerdeki en kötü durum problemlerinden (ideal-SVP) yapılır. İdeal kafeslerin ek yapısı, ilke olarak bunları genel kafeslerden daha kolay hâle getirebilir ve bu konu etkin bir araştırma alanıdır. Bu yapıdan yararlanan pratik bir saldırı bilinmemektedir.

Module-LWE (M-LWE), tek bir halka elemanı veya büyük bir tamsayı matrisi yerine halka elemanlarından oluşan k x k boyutunda bir matris kullanarak hem LWE'yi hem de Ring-LWE'yi geneller. k = 1 olduğunda Ring-LWE'ye indirgenir; k büyüdükçe standart LWE'ye yaklaşır. Ayarlanabilir k parametresi, güvenlik güvencesi ile performans arasında denge kurulmasını sağlar.

CRYSTALS-Kyber (şimdi ML-KEM, FIPS 203), R_q üzerinde k-rütbeli bir matrise sahip Modül-LWE'ye dayanır. k parametresi güvenlik düzeyini doğrudan belirler: k=2, 128 bitlik güvenliği (ML-KEM-512); k=3, 192 bitlik güvenliği (ML-KEM-768); k=4 ise 256 bitlik güvenliği (ML-KEM-1024) hedefler. Modül yapısı, güvenliği k değerini değiştirerek ölçeklendiren tek bir kod tabanına olanak tanır.

R_q = Z_q[X]/(X^n + 1) içindeki polinom çarpımı, performansın önündeki temel darboğazdır. Sayı Teorik Dönüşümü (NTT), polinomları değerlendirme biçimine dönüştüren ve bu biçimde çarpmanın noktasal hâle geldiği, Z_q üzerinde tanımlı ayrık bir Fourier dönüşümüdür. q, NTT uygulanabilecek şekilde seçildiğinde polinom çarpımı O(n log n) zamanda tamamlanır; bu, O(n^2) zamana kıyasla ML-KEM ve ML-DSA'da kritik bir optimizasyondur.

NTT, q'nun q = 1 mod 2n koşulunu sağlayan bir asal olmasını gerektirir; bu da Z_q'nun 2n'inci ilkel birlik kökünü içermesini sağlar. n = 256 olan ML-KEM için q = 3329 bu koşulu karşılar. Z_3329 üzerindeki NTT, SIMD yönergelerine sahip modern donanımlarda son derece hızlıdır ve yaygın işlemcilerde saniyede binlerce ML-KEM işleminin gerçekleştirilmesini sağlar.

Halka-LWE ve Modül-LWE, standart LWE'ye kıyasla anahtar boyutlarını büyük ölçüde küçültür. 128 bitlik güvenlik için standart bir LWE açık anahtarı 1 MB olabilir; Halka-LWE bunu yaklaşık 800 bayta indirir ve Modül-LWE (ML-KEM-768), kuantum sonrası 192 bitlik güvenlikle 1184 baytlık bir açık anahtar sağlar. Bu kompaktlık, kafes şemelerini TLS ve gömülü sistemler için uygulanabilir hâle getirir.

Bazı kriptograflar, siklotomik halkaların sahip olduğu ek cebirsel yapının yalın LWE'ye uygulanamayan saldırılara olanak sağlayabileceğinden endişe ediyor. Elias Rokicki ve çalışma arkadaşları 2024'te 2n'inci siklotomik polinom üzerine bir analiz yayımladı; pratikte kullanılabilecek bir saldırı bulamadılar, ancak araştırmaların sürdürülmesinin önemini vurguladılar. NIST PQC süreci bu riski değerlendirdi ve kısmen herhangi bir tek halka yapısına bağımlılığı azaltmak amacıyla Modül-LWE'yi seçti.

Kyber'in yanı sıra Halka-LWE, NIST tarafından standartlaştırılan imza şeması CRYSTALS-Dilithium'un (ML-DSA) temelini oluşturur. Microsoft'un SEAL kütüphanesi, Halka-LWE aracılığıyla homomorfik şifrelemeyi mümkün kılar. Google'ın Tink kriptografi kütüphanesi ML-KEM desteği içerir. Halka-LWE, NIST standardizasyon sürecinin etkisiyle son derece kısa bir sürede kuramsal bir yapıdan üretim ortamında kullanıma geçmiştir.

Halka-LWE, LWE'yi R_q = Z_q[X]/(X^n+1) polinom halkasına taşıyarak anahtar boyutlarını büyük ölçüde küçültür ve NTT tabanlı hızlı aritmetiği mümkün kılar. Modül-LWE, bunu k-rütbeli bir yapıyla genelleştirerek ML-KEM'in (FIPS 203) ve ML-DSA'nın (FIPS 204) temelini oluşturur. NTT ile uyumlu q = 3329 asalı, verimli bir uygulamayı mümkün kılar. Güvenlik, ideal ve modül kafesleri üzerindeki problemlerin zorluğuna dayanır.