Hatalarla Öğrenme (LWE): Kafes Teorisi ve Kuantum İndirgeme Analizi

Özet: Bu çalışma, Oded Regev (2005) tarafından sunulan Learning with Errors (LWE) probleminin, Shortest Independent Vectors Problem (SIVP) gibi en kötü durum kafes problemlerine olan kuantum indirgemesini matematiksel bir çerçevede incelemektedir. Çalışma, Gaussian pürüzsüzleştirme, dual kafesler üzerindeki Fourier analizi ve kuantum örnekleme mekanizmalarına odaklanmaktadır [1].

1. Ön Bilgiler ve Notasyon

LWE probleminin zorluğunu analiz etmek için öncelikle kafes teorisindeki temel tanımları oturtmamız gerekir.

1.1. Primal ve Dual Kafesler

$n$-boyutlu bir kafes $\Lambda$, lineer bağımsız bir taban setinin $B = {b_1, \dots, b_n} \subset \mathbb{R}^n$ tam sayı kombinasyonlarıdır:

Kriptografik indirgemelerin merkezinde yer alan Dual Kafes ($\Lambda^*$) ise şöyle tanımlanır [6]:

Önem: Primal kafeste “kısa” vektörler bulmak (SIVP), dual kafes uzayında periyodikliği analiz etmekle yakından ilişkilidir. Bir fonksiyonun $\Lambda$ üzerindeki Fourier dönüşümü, $\Lambda^*$ üzerinde tanımlıdır. Poisson Toplama Formülü bu ikisi arasındaki ilişkiyi kurar:

1.2. Gaussian Dağılımı ve Pürüzsüzleştirme (Smoothing)

$\mathbb{R}^n$ üzerinde, $s$ genişlik parametresine sahip bir Gaussian fonksiyonu $\rho_s(x) = \exp(-\pi |x|^2 / s^2)$ olarak tanımlanır.

Kafes üzerindeki Ayrık Gaussian Dağılımı $D_{\Lambda, s}$ ise, olasılık kütlesinin kafes noktalarına normalize edilmesidir:

Buradaki kritik kavram Pürüzsüzleştirme Parametresi $\eta_\epsilon(\Lambda)$’dır. Bu parametre, Gaussian gürültüsü eklendiğinde, kafes yapısının “kaybolup” dağılımın uniforma ne kadar yaklaştığını belirler [2].

Teorem (Uniformluk): Eğer $s \geq \eta_\epsilon(\Lambda)$ ise, $\Lambda$ kafesine $e \sim D_{\mathbb{Z}^n, s}$ hatası eklendiğinde elde edilen dağılım, modulo $\Lambda$ uzayında uniform dağılıma $\epsilon$ kadar yakındır (istatistiksel uzaklık olarak).

2. LWE Probleminin Formülasyonu

Parametreler $n \geq 1$, modül $q \geq 2$ ve hata dağılımı $\chi$ (genellikle $D_{\mathbb{Z}, \alpha q}$) olsun.

LWE dağılımı $A_{s, \chi}$, $s \in \mathbb{Z}_q^n$ gizli vektörü için şöyle örneklenir [5]:

• $a \leftarrow U(\mathbb{Z}_q^n)$ (Uniform)
• $e \leftarrow \chi$
• Çıktı: $(a, b = \langle a, s \rangle + e \in \mathbb{Z}_q)$

Arama Problemi: $A_{s, \chi}$’den alınan polinom sayıda örnek ile $s$’i bulmak.

3. Worst-Case to Average-Case İndirgeme (Regev ‘05)

Regev’in ana teoremi şunu ifade eder:

Teorem 3.1: $\alpha q > 2\sqrt{n}$ olsun. Eğer $LWE_{n, q, \alpha}$ problemini polinom zamanda çözen bir algoritma varsa, o zaman $\tilde{O}(n/\alpha)$ yaklaşım faktörü ile $SIVP$ ve $GapSVP$ problemlerini çözen bir kuantum algoritma vardır [1].

İndirgeme zinciri şu şekildedir:

3.1. Klasik Adım: LWE ile BDD Çözümü (Gaussian Smoothing Detayı)

Bu adımda, LWE kahini kullanılarak Dual Kafes $\Lambda^*$ üzerinde Bounded Distance Decoding (BDD) problemi çözülür.

Elimizde $\Lambda^*$ dual kafesine yakın bir $x$ noktası olduğunu varsayalım. Amacımız en yakın kafes noktasını bulmaktır.

Bu problemi LWE’ye dönüştürmek için $q$-ary kafesler kullanılır.

Kafes noktalarını $q$ modunda parçalara ayırdığımızda, $x$’in koordinatları LWE örneklerindeki $(a, b)$ çiftlerine dönüşür.

Burada Gaussian Smoothing devreye girer: Eklenen hata miktarı, kafesin pürüzsüzleştirme parametresini ($\eta$) aştığında, $a$ vektörleri $\mathbb{Z}_q^n$ üzerinde uniform dağılır. Bu, LWE’nin girdisinin (a’nın uniform olması şartı) matematiksel olarak sağlanmasını garanti eder.

3.2. Kuantum Adımı: Fourier Dönüşümü ve Örnekleme

Regev’in kanıtının en can alıcı ve zor kısmı burasıdır. Klasik bilgisayarlar yüksek boyutlu kafeslerden verimli bir şekilde Gaussian örneklemesi yapamazlar. Ancak SIVP’yi çözmek için “kısa” vektörlere, yani $D_{\Lambda^*, r}$ dağılımından örneklere ihtiyacımız vardır.

Algoritma şu şekilde işler [1, 5]:

1. Süperpozisyon Hazırlığı: Bir kuantum durumu, kafes noktaları üzerinde bir Gaussian süperpozisyonu olarak hazırlanır. Ancak bu durum $\Lambda$ üzerindedir ve çok “geniş” bir Gaussian’dır (yani vektörler uzundur, işe yaramaz).

   \[|\psi\rangle = \sum_{x \in \Lambda} \rho_s(x) |x\rangle\]

2. Kuantum Fourier Dönüşümü (QFT): Bu duruma QFT uygulanır. Poisson Toplama Formülü gereği, bir kafesin Fourier dönüşümü, onun Dual Kafesi ($\Lambda^*$) üzerinde tanımlıdır. Ayrıca, geniş bir Gaussian’ın Fourier dönüşümü, dar (kısa) bir Gaussian’dır.

   \[QFT |\psi\rangle \approx \sum_{y \in \Lambda^*} \rho_{1/s}(y) |y\rangle\]

3. Ölçüm ve Çözüm: Bu yeni durum ölçüldüğünde, $\Lambda^*$ dual kafesinden “kısa” bir vektör elde edilir. Bu kısa vektörler SIVP probleminin çözümünü sağlar.

Buradaki kritik nokta, LWE Kahini’nin bu kuantum sürecinde hata düzeltme amacıyla kullanılmasıdır. QFT sonucunda elde edilen durum gürültülüdür; LWE çözen algoritma, bu gürültüyü (bounded distance decoding yaparak) temizler ve kuantum durumunun doğru dual kafes noktasına çökmesini sağlar.

4. Sayısal Analiz ve Örneklem

LWE probleminin soyut yapısını somutlaştırmak adına, Regev’in makalesinde verilen örneği $\mathbb{Z}_{17}$ uzayında inceleyelim [5]. Bu örnek, hata teriminin ($e$) lineer denklemlerde nasıl belirdiğini göstermektedir.

Parametreler:

• Modül: $q = 17$
• Gizli Vektör: $s = (0, 13, 9, 11) \in \mathbb{Z}_{17}^4$

Bize verilen LWE örneklerinden (denklemlerden) ikisini analiz edelim:

Örnek 1:

Verilen denklem: $14s_1 + 15s_2 + 5s_3 + 2s_4 \approx 8 \pmod{17}$

İç Çarpım Hesabı:

Modüler İndirgeme:

Gerçek iç çarpım sonucu 7’dir.

Hata Analizi:

Denklem bize sonucun 8 olduğunu söylemektedir.

Örnek 2:

Verilen denklem: $13s_1 + 14s_2 + 14s_3 + 6s_4 \approx 16 \pmod{17}$

İç Çarpım Hesabı:

Modüler İndirgeme:

Gerçek iç çarpım sonucu 0’dır.

Hata Analizi:

Denklem bize sonucun 16 olduğunu söylemektedir.

Modüler aritmetikte $16 \equiv -1 \pmod{17}$ olduğundan, buradaki hata $e = -1$ olarak kabul edilir.

Bu küçük hatalar ($+1, -1$), Gaussian eliminasyonu gibi kesin çözüm yöntemlerini işlevsiz kılar.

5. Sonuç

LWE’nin güvenliği, basit bir kombinatorik zorluktan değil, Primal ve Dual Kafesler arasındaki Fourier ilişkisinin karmaşıklığından gelir. Regev’in indirgemesi, LWE’yi çözmenin, $\Lambda^*$ üzerinde kısa vektörler bulmaya (yani SIVP’ye) eşdeğer olduğunu, bunun da ancak kuantum seviyesinde bir Fourier analizi ile mümkün olabileceğini (tersi ispatlanana kadar) göstermiştir.

6. Referanslar

[1] Regev, O. (2009). On lattices, learning with errors, random linear codes, and cryptography. Journal of the ACM, 56(6), 1-40. (İlk versiyon STOC 2005).

[2] Peikert, C. (2009). Public-key cryptosystems from the worst-case shortest vector problem. Proceedings of the 41st Annual ACM Symposium on Theory of Computing (STOC).

[3] Lyubashevsky, V., Peikert, C., & Regev, O. (2010). On ideal lattices and learning with errors over rings. Advances in Cryptology – EUROCRYPT 2010.

[4] Gentry, C., Peikert, C., & Vaikuntanathan, V. (2008). Trapdoors for hard lattices and new cryptographic constructions. STOC 2008.

[5] Regev, O. (2010). The Learning with Errors Problem. Invited Survey for CCC.

[6] CS 294 Lecture Notes. The Learning with Errors Problem: Introduction and Basic Cryptography.