Kafes Şemalarında Güvenlik İspatları ve İndirgemeler

Bir kriptografik şema için güvenlik ispatı, şemayı kırmanın temelindeki zor problemi çözmeyi gerektirdiğini gösteren biçimsel bir matematiksel kanıttır. İspat mutlak güvenliği garanti etmez; şemaya karşı çalışan her etkin saldırganın, zor problem için etkin bir çözücüye dönüştürülebileceğini gösterir. Zor problem hesaplanamaz derecede zorsa şema güvenlidir.

Regev'in 2005 tarihli öncü ispatı, karar vermeye dayalı LWE'yi çözen polinom zamanlı bir algoritmanın, n boyutlu kafeslerdeki en kötü durum GapSVP'yi (Aralıklı En Kısa Vektör Problemi) çözmek için kullanılabileceğini gösterir. İndirgeme kuantumdur: bir LWE çözücüsünü kafes çözücüsüne dönüştürmek için kuantum örnekleme yordamı kullanır. Bu, kuantum hesaplama altında LWE'nin en kötü durum kafes problemleri kadar zor olduğunu gösterir.

Regev'in indirgemesi sıkı değildir: indirgemedeki polinom çarpanları, ispatın garanti ettiği güvenlik düzeyinin bilinen en iyi saldırıların işaret ettiğinden bir miktar daha düşük olması anlamına gelir. Pratik parametre seçimi için kriptograflar, indirgeme sınırı ihtiyatlı olduğu için kuramsal indirgeme sınırı yerine bilinen en iyi saldırıların sağladığı somut güvenliği, yani kafes kestirim aracının sonuçlarını kullanır.

LWE tabanlı bir şifreleme şemasının IND-CPA (seçilmiş açık metin saldırısına karşı ayırt edilemezlik) güvenliği, hibrit bir argümanla ispatlanır. İspat, bir IND-CPA ayırt edicisinin bir LWE ayırt edicisini gerektirdiğini gösterir. İlk hibritte gerçek şifreli metin, eş olasılıklı rastgele bir dizeyle değiştirilir; ayırt edilemezlik LWE varsayımından çıkar. Bu, temel kafes şifrelemesi için açık ve anlaşılır bir güvenlik ispatı sağlar.

IND-CPA güvenliği, TLS'de kullanılan anahtar kapsülleme mekanizmaları için yeterli değildir: bunların IND-CCA2 (seçilmiş şifreli metin saldırısına karşı) güvenliğine sahip olması gerekir. Fujisaki-Okamoto (FO) dönüşümü, herhangi bir IND-CPA şemasını Rastgele Kehanet Modeli'nde (ROM) IND-CCA2 güvenli bir KEM'e dönüştürür. ML-KEM, temelindeki Modül-LWE şifrelemesine FO dönüşümünün bir çeşidini uygulayarak gerçek dünyada kullanıma sunulmak için gereken CCA2 güvenliğini sağlar.

Rastgele Kehanet Modeli (ROM), özet işlevlerini gerçekten rastgele işlevler olarak modeller. FO dönüşümünün ispatları da dâhil olmak üzere birçok güvenlik ispatı ROM'u gerektirir. Pratikte SHA-3 gibi özet işlevleri gerçekten rastgele kehanetler değildir; bu nedenle ROM ispatları standart modelde güvenliği garanti etmez. Bununla birlikte ROM ispatları, kriptografi topluluğunda güvenliğe dair güçlü kanıtlar olarak geniş ölçüde kabul edilir.

Standart model ispatı, özet işlevleri hakkında hiçbir ideal kabul yapmaz ve ROM ispatından kesin olarak daha güçlüdür. Çoğu pratik kafes şeması ROM ispatlarını kullanır; çünkü kafes tabanlı KEM'ler için standart modeldeki CCA2 ispatları çok daha karmaşıktır ve daha kötü somut parametreler verir. NIST, ML-KEM için ROM tabanlı ispatları kabul ederek bunları hedeflenen güvenlik düzeyleri için yeterli gördü.

ML-KEM güvenlik ispatı iki adımda ilerler. İlk olarak, temelindeki Modül-LWE şifrelemesinin M-LWE varsayımı altında IND-CPA güvenli olduğu gösterilir. İkinci olarak, Fujisaki-Okamoto dönüşümü (özellikle Kyber'de kullanılan T ve U dönüşümleri), bunu kuantum ROM'da (QROM) IND-CCA2 güvenliğine yükseltir; QROM, rastgele kehanete süperpozisyon içinde sorgu yönelten saldırganları ele alır.

Albrecht, Player ve Scott tarafından geliştirilen kafes kestirim aracı, LWE tabanlı şemaların somut güvenliğini hesaplamak için kullanılan standart araçtır. Bilinen en iyi kafes saldırılarının (eleme veya numaralandırma kullanan BKZ) maliyetini modeller ve verilen parametreler (n, q, sigma) için tahmini bit güvenliğini verir. Yeni algoritmalar ve donanım maliyeti modelleri yayımlandıkça araç düzenli olarak güncellenir.

Blok Korkine-Zolotarev (BKZ) algoritması, pratikteki en iyi kafes indirgeme algoritmasıdır. beta blok boyutuna sahip BKZ, en iyi eleme algoritmalarını kullanarak yaklaşık 2^{0.292*beta} kapı işlemi karmaşıklığıyla kısa vektörler bulur. ML-KEM-768 için tahmini klasik güvenlik yaklaşık 180 bit, kuantum güvenliği ise yaklaşık 164 bittir; bu değerler 192 bitlik hedefin oldukça üzerindedir.

Asimptotik güvenlik ispatları, bir şemanın yeterince büyük parametreler için güvenli olduğunu gösterir; ancak pratikte "yeterince büyük" ifadesinin ne anlama geldiğini belirtmez. Somut güvenlik analizi, seçilen parametreler için en iyi saldırının gerçek maliyetini tahmin ederek bu açığı kapatır. Kuantum sonrası standardizasyon büyük ölçüde somut güvenlik analizine dayanır; parametreler, 30 yıllık bir dönem boyunca öngörülen kuantum donanımındaki saldırılara direnmek üzere seçilir.

ML-KEM'de IND-CPA kafes şifrelemesini IND-CCA2 güvenliğine yükseltmek için hangi dönüşüm kullanılır?

Kafes şemelerinin güvenlik ispatları, şemanın güvenliğini LWE veya SVP problemlerinin zorluğuna indirger. Regev'in indirgemesi, LWE'nin en kötü durum kafes problemleri kadar zor olduğunu garanti eder. Fujisaki-Okamoto dönüşümü, ROM'da IND-CPA güvenliğini IND-CCA2 güvenliğine yükseltir. Somut güvenlik, BKZ karmaşıklık modelleri kullanılarak kafes kestirim aracıyla değerlendirilir. İndirgeme sıkılığındaki açıklar nedeniyle pratik parametreler yalnızca indirgeme sınırlarına değil, saldırı maliyeti tahminlerine dayanır.