Hatalarla Öğrenme (LWE) Temeli

Regev'in (2005) Learning With Errors (LWE) yaklaşımı: Z_q üzerinde çok sayıda gürültülü doğrusal denklem verildiğinde gizli vektör s'yi bulun. Gürültü e küçüktür, ancak Gauss elemesini engeller. Gürültü olmadığında sistem kolaydır; en küçük bir gürültüyle bile hesaplama açısından zor hâle gelir.

Gizli s ∈ Z_q^n. Saldırgan, a_i ∈ Z_q^n'nin rastgele olduğu ve b_i = + e_i mod q bağıntısını sağlayan (a_i, b_i) örneklerini alır; e_i, χ dağılımından gelen küçük bir gürültüdür (örneğin σ = √n olan Gauss dağılımı). Görev: polinom sayıda örnek verildiğinde s'yi bulmak.

Gürültü olmadan: b_i = mod q. Gauss elemesi, s'yi O(n^3) sürede geri kazanır. Gürültü varken: tek bir yanlış denklem bile eleme işlemini bozar. Gürültü, şifre çözmenin (anahtar kullanılarak) çalışmasına yetecek kadar küçük, ancak kriptanalizi engelleyecek kadar büyüktür.

Regev, LWE'nin en kötü durum kafes problemlerine (SIVP, GapSVP) kuantum indirgemeyle indirgendiğini kanıtladı. Bunun anlamı şudur: LWE kırılırsa birçok zor kafes problemi çözülmüş olur — ancak kafes problemleri için bilinen hiçbir kuantum algoritması yoktur. LWE, kuantum sonrası güvenlidir.

RLWE, Z_q^n'nin yerine siklotomik polinom f için Z_q[x]/(f(x)) halkasını kullanır. Tek bir RLWE örneği n denklemi kodlar; bu çok daha verimlidir. RLWE, Kyber (KEM), Dilithium (imza) ve BFV/BGV/CKKS HE şemalarının temelidir.

Güvenlik şunlara bağlıdır: n (boyut, genellikle 512-2048), q (modül, 1024-2^60) ve σ (gürültünün standart sapması). Daha büyük n ve daha küçük σ/q oranı, problemi zorlaştırır. NIST kuantum sonrası standartları, k modüllü (k=2,3,4) n=256'yı (modül boyutu) kullanır.

Açık anahtar: (A, b=As+e). Bit m'yi şifrelemek için rastgele r seçin ve şifreli metni (u=A^T r, v = b^T r + m*q/2) olarak hesaplayın. Şifreyi çözme: v - s^T u = e^T r + m*q/2 ≈ m*q/2. En yakın m değerine yuvarlayın. Gürültü e, şifreleme sırasında şifreli metnin m'yi gizli tutmasını sağlar.

Karar-LWE: u'nun düzgün rastgele olduğu (a, u) çifti ile (a, As+e) çiftini ayırt etme problemidir. LWE'nin zorluğu varsayımı altında hesaplama açısından ayırt edilemezdir. Bu, anlamsal güvenliğin temelidir — gizli anahtarı olmayan saldırganlara şifreli metinler rastgele gürültü gibi görünür.

Bilinen en iyi saldırılar: BKZ (Blok Korkine-Zolotarev) kafes indirgemesi. Karmaşıklık: üstel altı, ancak polinom değil. BKZ-β, 2^{0.292β} işlem gerektirir. LWE-512 için BKZ'ye karşı güvenlik yaklaşık 128 bittir. BKZ için bilinen bir kuantum hızlanması yoktur.

Kyber'de kullanılan Module-LWE, k dereceli modüller üzerinde RLWE'dir. Esneklik sağlar: 512 bitlik güvenlik için k=2, 768 bitlik güvenlik için k=3 ve 1024 bitlik güvenlik için k=4. Güvenlik ve performans k ile birlikte ölçeklenir. NIST, PQC standardı olarak Kyber'i (ML-KEM olarak yeniden adlandırıldı) seçti.

RSA/ECC güvenliği, tamsayı çarpanlara ayırma ve ayrık logaritmaya dayanır (Shor algoritması aracılığıyla kuantuma karşı savunmasızdır). LWE güvenliği, en kötü durum kafes problemlerine dayanır (bilinen bir kuantum hızlanması yoktur). Anahtar boyutları: LWE anahtarları yaklaşık 1 KB, RSA-2048 ise 256 bayttır. LWE daha büyüktür, ancak kuantuma karşı güvenlidir.

LWE'yi, çok sayıda örnekle bile çözülmesi zor yapan nedir?

LWE: gürültülü doğrusal denklemlerden gizli s'yi bulma — kuantum bilgisayarlar için de zordur. RLWE, verimlilik için polinom halkaları kullanır. Kyber, Dilithium ve HE şemalarının temelidir. Sırada: tamsayı işlemleri için BGV ve BFV HE şemaları.