CRYSTALS-Dilithium ve Falcon İmzaları

RSA ve ECDSA imzaları Shor algoritması tarafından kırılabilir. Kuantum sonrası imzalar şu alanlarda bunların yerini almalıdır: TLS sertifikaları, kod imzalama, e-posta imzalama (S/MIME, PGP) ve yazılım güncellemelerinin kimlik doğrulaması. NIST, kafes tabanlı iki şemayı standartlaştırmıştır: ML-DSA ve FN-DSA.

Dilithium, Module-LWE ve Module-SIS problemlerinin zorluğuna dayanır (Short Integer Solution, Kısa Tamsayı Çözümü). Güvenlik kanıtı QROM'da (Kuantum Rastgele Kahin Modeli) verilir. Üç çeşidi vardır: Dilithium2 (yaklaşık 128 bit), Dilithium3 (yaklaşık 192 bit), Dilithium5 (yaklaşık 256 bit). Basittir ve reddetmeli örnekleme içermeyen bir imzalama yoluna sahiptir.

Özel anahtar: gizli s1, s2 matrisleri. Açık anahtar: t = As1 + s2. İmzalama: rastgele y örnekleyin; w = Ay hesaplayın; w1 = HighBits(w) olacak şekilde c = H(mu || w1) meydan okumasını hesaplayın; z = y + cs1 hesaplayın; ||z|| veya ||r0|| çok büyükse reddedin ve yeniden deneyin. Çıktı (z, c, hint) olur.

(z, c, hint) değerlerini doğrulayın: ||z|| değerinin küçük olduğunu denetleyin; w' = Az - ct hesaplayın; w1'i geri elde etmek için ipucunu kullanın; c == H(mu || w1) olduğunu doğrulayın. İpucu, MakeHint() işlevinden alınan az sayıda bittir. Reddetme işlemi, z'nin s1'i sızdırmamasını sağlar; güvenlik gerekçesi “önce durdurma, sonra tekdüze dağılım” argümanına dayanır.

ML-DSA-65 (Dilithium3, 192 bit güvenlik): açık anahtar 1952 bayt, özel anahtar 4000 bayt, imza 3293 bayttır. Karşılaştırma için ECDSA-P256: açık anahtar 64 bayt, imza 64 bayttır. Dilithium imzalarda yaklaşık 40-50 kat daha büyüktür; ancak kuantuma karşı güvenlidir.

Falcon, NTRU kafeslerine dayanır ve NTRU kafesi üzerinde bir Gauss örnekleyicisi kullanır. İmzaları Dilithium'unkilerden önemli ölçüde küçüktür; ancak imzalama, kayan noktalı bir Gauss örnekleyicisi gerektirir. Bu örnekleyiciyi sabit zamanlı uygulamak daha zordur ve kodu güvenli biçimde yazmak daha karmaşıktır.

Falcon-512 (128 bit güvenlik): açık anahtar 897 bayt, imza 666 bayttır — Dilithium'dan çok daha küçüktür. Bunun karşılığında Falcon'ın güvenli biçimde uygulanması daha zordur (Gauss örneklemesi zamanlama saldırılarına açıktır). Bant genişliğinin kısıtlı olduğu ortamlar için uygundur; ancak dikkatli bir uygulama gerektirir.

SPHINCS+, özet tabanlı bir imza şemasıdır ve yapısal cebirsel varsayımlara dayanmayan ihtiyatlı bir seçimdir. Güvenliği yalnızca özet işlevinin güvenliğine dayanır. İmza boyutu yaklaşık 8-50 KB'tır (büyüktür). İmzalama yavaştır. Uzun vadeli güvenin kritik, performansın ise ikincil olduğu yerlerde kullanılır.

ML-DSA (Dilithium): genel amaçlıdır, uygulanması basittir; TLS sertifikaları ve kod imzalama için uygundur. FN-DSA (Falcon): bant genişliğinin kısıtlı olduğu ortamlar (IoT, LPWAN) içindir. SLH-DSA (SPHINCS+): son derece ihtiyatlıdır; uzun süre geçerli kökler (CA'lerin çevrimdışı anahtarları, yazılım güven kökü) için uygundur.

Dilithium: reddetmeli örnekleme, dallanma zamanlamasını sızdırabilir — sabit zamanlı karşılaştırma kullanın. Falcon: Gauss örnekleyicisi kayan nokta kullanır — FP belirlenimliliğini sağlayın. Her ikisinde de polinom aritmetiğindeki yan kanallardan kaçının. NIST başvuru paketlerindeki referans uygulamalarını kullanın.

NIST FIPS 204: ML-DSA (Dilithium). NIST FIPS 205: SLH-DSA (SPHINCS+). NIST FIPS 206: FN-DSA (Falcon). Üçü de Ağustos 2024'te yayımlandı. Kütüphaneler: OpenSSL 3.x, BoringSSL, liboqs (Open Quantum Safe projesi) üçünü de uygular.

ML-DSA (Dilithium): kafes tabanlı, basit, yaklaşık 3 KB imzalar. FN-DSA (Falcon): NTRU tabanlı, yaklaşık 700 baytlık imzalar, karmaşık uygulama. SLH-DSA (SPHINCS+): özet tabanlı, ihtiyatlı, büyük. Tümü FIPS 204/205/206'da standartlaştırılmıştır. Sırada: hibrit yaklaşımlarla PQC'ye geçiş.