Hatalarla Öğrenme: Zor Problem

Hatalarla Öğrenme (LWE) problemi, kuantum sonrası kriptografinin temeli olarak 2005 yılında Oded Regev tarafından ortaya atılmıştır. Z_q üzerinde rastgele bir A matrisi ve b = As + e vektörü verildiğinde amaç, gizli s vektörünü bulmaktır. e vektörü, ayrık Gauss dağılımından seçilen küçük bir hatadır; bu da problemi hesaplama açısından çözülemez hâle getirir.

LWE probleminde A, q'nun asal modül olduğu Z_q üzerinde eşit olasılıkla örneklenen m x n boyutunda rastgele bir matristir. Gizli s, n boyutlu bir vektördür ve e, bileşenleri dar bir Gauss dağılımından seçilen küçük bir hata vektörüdür. A'nın yapısını bilmek bile saldırganın b'yi eşit olasılıklı rastgele bir vektörden ayırt etmesine yardımcı olmaz.

LWE'nin iki standart biçimi vardır. Arama LWE'sinde, çok sayıda (A, b) örneği verildiğinde gizli s'nin geri elde edilmesi istenir. Karar LWE'sinde ise (A, As + e) örneklerinin, eşit olasılıklı rastgele (A, u) çiftlerinden ayırt edilmesi istenir. İki biçim polinomik açıdan eşdeğerdir; yani birini çözen bir algoritma, diğerini çözecek şekilde dönüştürülebilir.

LWE'deki hata terimi, standart sapma sigma ile parametreleştirilen tamsayılar üzerindeki ayrık Gauss dağılımından seçilir. Küçük sigma değerleri, e'nin q'ya kıyasla küçük olmasını ve b'nin q modunda As'ye neredeyse benzemesini sağlar. sigma sıfır olsaydı hata bulunmaz ve sistem Gauss elemesiyle çözülebilirdi; dolayısıyla zorluğun temelinde hata vardır.

Regev dikkat çekici bir indirgeme kanıtlamıştır: ortalama durumdaki LWE örneklerini çözmek, kafeslerdeki en kötü durum Shortest Vector Problem (SVP) örneklerini çözmek kadar zordur. Bu, LWE'yi verimli biçimde kırabilirseniz herhangi bir kafes problemini de verimli biçimde çözebileceğiniz anlamına gelir. En kötü durum SVP'yi polinom zamanda çözen bilinen bir klasik veya kuantum algoritma yoktur.

RSA ve eliptik eğri kriptografisinin aksine, bilinen hiçbir kuantum algoritması LWE'ye karşı üstel bir hızlanma sağlamamaktadır. Grover algoritması en fazla karesel bir hızlanma sunar ve en iyi kuantum kafes algoritmaları (BKZ varyantları), uygun parametreler seçildiğinde LWE'yi kıramaz. Bu, LWE'yi kuantum sonrası güvenlik için güçlü bir temel hâline getirir.

LWE güvenliği üç parametre tarafından belirlenir: boyut n (gizli değerin uzunluğu), modül q ve hatanın standart sapması sigma. Daha büyük n ve daha küçük q/sigma oranı güvenliği artırır. 128 bitlik kuantum sonrası güvenlik için tipik değerler n = 1024, q yaklaşık 12289 ve sigma yaklaşık 3.2'dir. Albrecht ve çalışma arkadaşlarının kafes tahmin aracı, somut güvenliği değerlendirmek için kullanılır.

Kısa Tamsayı Çözümü (SIS) problemi, imzalar için kullanılan ve bununla ilişkili bir kafes zorluğu varsayımıdır. Z_q üzerinde rastgele bir A matrisi verildiğinde, Ax = 0 mod q koşulunu sağlayan kısa ve sıfır olmayan bir x vektörü bulunması istenir. SIS, kafes tabanlı dünyadaki özet işlevlerinin ve imza şemalarının temelidir; şifreleme ile anahtar kapsüllemenin temelini oluşturan LWE'yi tamamlar.

Basit bir LWE şifreleme şeması şöyle çalışır: açık anahtar (A, b = As + e), gizli anahtar ise s'dir. Bir m bitini şifrelemek için gönderici, rastgele bir ikili r vektörü seçer ve (u, v) = (A^T r, b^T r + m * floor(q/2)) değerini hesaplar. Şifre çözme işlemi v - s^T u değerini hesaplar ve m'yi elde etmek için yuvarlama yapar. Bu şema, LWE varsayımı altında IND-CPA güvenliği sağlar.

LWE, temel şifrelemenin ötesinde çok çeşitli kriptografik yapıların geliştirilmesini mümkün kılmıştır. Bunlar arasında tam homomorfik şifreleme (FHE), kimlik tabanlı şifreleme (IBE), öznitelik tabanlı şifreleme (ABE) ve anahtar değişimi protokolleri bulunur. CRYSTALS-Kyber (artık ML-KEM olarak anılmakta ve FIPS 203 kapsamında standartlaştırılmaktadır), uygulamada en yaygın kullanılan LWE tabanlı şemadır.

LWE tabanlı kriptografi üretim sistemlerine girmeye başlamıştır. Google ve Cloudflare, 2018-2020 yıllarında Kyber kullanarak TLS deneyleri gerçekleştirdi. Chrome ve Firefox, 2024 yılında hibrit TLS el sıkışmalarında ML-KEM-768 desteği ekledi. Signal Protocol, ileriye dönük gizlilik sağlamak ve uzun vadeli ileti gizliliğini gelecekteki kuantum bilgisayarlarına karşı korumak için ML-KEM-1024 kullanan kuantum sonrası bir katman (PQXDH) ekledi.

Aşağıdaki ifadelerden hangisi LWE probleminin zorluk garantisini en iyi açıklar?

LWE, kafes problemlerinden gelen güçlü bir en kötü durum indirgemesiyle desteklenen, kuantum sonrası en kapsamlı biçimde incelenmiş zorluk varsayımlarından biridir. Üç parametresi (n, q, sigma), güvenlik ile performans arasındaki dengeyi belirler. LWE, kuantum saldırılarına dayanır ve NIST tarafından standartlaştırılan şemaların temelini oluşturur. LWE'yi anlamak, ML-KEM ve ML-DSA dahil olmak üzere modern kafes tabanlı kriptografinin tamamına açılan kapıdır.