Kanıtlanabilir Güvenlik ve İndirgemeler
Kanıtlanabilir güvenlik, bir kriptografik şemayı kırmanın, çözülmesi güç olduğuna inanılan bir problemi çözmek kadar zor olduğunu, varsayılan zor problemden şemaya yönelik herhangi bir saldırıya açık bir indirgeme sunarak göstermektedir.
Tanım
Bir güvenlik indirgemesi, bir kriptografik şemayı kıran herhangi bir verimli düşmanı, zor olduğu varsayılan bir problemi çözen verimli bir algoritmaya dönüştüren bir ispat olup, bu sayede şemanın, söz konusu problem kolay olmadığı sürece güvenli olduğunu göstermektedir.
Kapsam
Bu konu, kriptografik ispatların indirgeme tabanlı metodolojisini kapsamaktadır: bir güvenlik indirgemesinin yapısı, sıkılık ve somut güvenlik, oyun tabanlı ve simülasyon tabanlı ispat stilleri, random-oracle ve standart modeller ile yaklaşımın sınırları ve eleştirileri. Güvenlik garantilerinin nasıl ifade edildiği ve savunulduğu ele alınmaktadır. Özgül zorluk varsayımları ile tanımlar ve düşman modelleri bu konunun dışında tutulmuştur; bunlar ilgili diğer konularda ele alınmaktadır.
Temel sorular
- Bir indirgeme, bir şemaya yönelik saldırıyı zor bir problemin çözümüne nasıl dönüştürmektedir?
- Oyun tabanlı ve simülasyon tabanlı ispatlar arasındaki fark nedir?
- Bir indirgemenin 'sıkılığı', gerçek dünya güvenlik parametreleri için ne anlama gelmektedir?
- Random-oracle ve standart modeller nelerdir ve ilki neden tartışmalıdır?
- Kanıtlanabilir güvenlik argümanlarının sınırları ve yaygın tuzakları nelerdir?
Anahtar kavramlar
- güvenlik indirgemesi
- oyun tabanlı ispatlar
- simülasyon tabanlı ispatlar
- sıkı ve gevşek indirgemeler
- somut güvenlik
- random-oracle modeli
- standart model
- ihmal edilebilir avantaj
- zorluk varsayımı
Temel kuramlar
- İndirgemeci ispat metodolojisi
- Bir şemayı güvenli ispatlamak için, onu kıran bir düşman varsayılır ve bu düşmanı bir alt yordam olarak kullanarak, temel zor problemi çözen bir algoritma inşa edilir; böylece başarılı bir saldırı, zorluk varsayımıyla çelişecektir.
- Random-oracle modeli
- Birçok verimli şema, bir hash fonksiyonunu gerçekten rastgele bir kahin (random oracle) olarak idealleştirerek güvenli ispatlanmaktadır; bu model pratik yapılar için ispatları mümkün kılmakla birlikte, hiçbir gerçek fonksiyon rastgele bir kahin olmadığı için sezgiseldir.
Mekanizmalar
Bir indirgemede, ispatlayıcı, şemayı ihmal edilemez bir avantajla kıran varsayımsal bir düşman varsayar ve zor problemin bir örneğini düşmanın görüş alanına yerleştiren, düşmanı çalıştıran ve çıktısını problemi çözmek için kullanan bir sarmalayıcı (wrapper) oluşturur. Oyun tabanlı ispatlar, gerçek şemadan, düşmanın açıkça kazanamayacağı bir duruma kadar ayırt edilemez oyunlar dizisi aracılığıyla ilerlemektedir. İndirgemelerin sıkılığı — ne kadar avantaj ve çalışma süresinin kaybedildiği — hedeflenen güvenlik seviyesi için gereken anahtar boyutlarını belirlemektedir.
Klinik önem
Kanıtlanabilir güvenlik, kriptografik şemaların güven ve standardizasyon kazanmasında bir standarttır: NIST'in AES, SHA-3 ve kuantum sonrası süreçleri güvenlik ispatlarını büyük ölçüde dikkate almış, TLS 1.3 gibi protokoller ise indirgemeci ve makine destekli analizlerle birlikte sunulmuştur. İndirgemeleri anlamak, uygulayıcıların bir güvenlik iddiasının neyi garanti edip neyi etmediğini değerlendirmelerine ve indirgeme sıkılığını dikkate alan parametreleri seçmelerine olanak tanımaktadır.
Kanıt ve kılavuzlar
Modern uygulamalar, mümkün olduğunda standart modeldeki ispatları tercih etmekte ve random-oracle ispatlarını mutlak garantiler yerine güçlü sezgisel kanıt olarak ele almaktadır. Araç destekli çerçeveler (EasyCrypt, CryptoVerif) makine destekli ispatlar sağlamaktadır. Düşman avantajını kaynakların bir fonksiyonu olarak nicelendiren somut (kesin) güvenlik analizi, gerçek parametreleri belirlemek için saf asimptotik ifadeler yerine tercih edilmektedir.
Tarihçe
İndirgemeci metodoloji, 1980'lerin başındaki tanımlayıcı devrimle ortaya çıkmış ve 1990'lar boyunca sistemleştirilmiştir. Bellare ve Rogaway, pratik şemaların güvenliğini ispatlamak için random-oracle modelini (1993) tanıtmış ve daha sonra garantileri nicelendirmek amacıyla 'somut güvenlik' analizini geliştirmişlerdir. Canetti, Goldreich ve Halevi'nin 1998'deki, random-oracle modelinde güvenli olan ancak somutlaştırıldığında güvensiz hale gelen şemaları gösteren sonuçları, idealleştirilmiş modeller üzerindeki tartışmayı keskinleştirmiştir.
Öne çıkan isimler
- Mihir Bellare
- Phillip Rogaway
- Oded Goldreich
- Shafi Goldwasser
- Silvio Micali
İlgili konular
Temel eserler
- bellare1993
- katz2020
- goldreich2001
Sıkça sorulan sorular
- Bir güvenlik ispatı, bir şemanın asla kırılamayacağı anlamına mı gelmektedir?
- Hayır. Bir ispat, şemayı kırmanın, belirtilen bir model içinde varsayılan zor bir problemi çözmeyi gerektirdiğini göstermektedir. Eğer varsayım başarısız olursa, model gerçekçi değilse veya uygulama analiz edilen şemadan saparsa, saldırılar hala mümkün olabilmektedir. İspatlar riski azaltır, ancak ortadan kaldırmaz.
- Random-oracle modeli neden tartışmalı kabul edilmektedir?
- Bir hash fonksiyonunu, hiçbir somut fonksiyonun gerçekten olmadığı, mükemmel rastgele bir fonksiyon olarak modellemektedir. Bu modeldeki ispatlar güçlü kanıtlar sunmakta ve verimli şemaları mümkün kılmaktadır, ancak modelde güvenli olan ancak kahin (oracle) herhangi bir gerçek hash ile değiştirildiğinde güvensiz hale gelen (yapay) şemalar bulunmaktadır; bu nedenle bu tür ispatlar sezgiseldir.