Hesaplamalı Zorluk Varsayımları
Hesaplamalı zorluk varsayımları, kriptografik şemaların güvenliğinin nihayetinde dayandığı, kanıtlanmamış ancak iyi incelenmiş varsayımlardır; bunlar arasında çarpanlara ayırma, ayrık logaritma ve kafes problemlerinin zorluğu gibi konular bulunmaktadır.
Tanım
Hesaplamalı zorluk varsayımı, belirli bir hesaplamalı problemin herhangi bir gerçekçi düşman tarafından verimli bir şekilde (polinom zamanda) çözülemeyeceğine dair bir varsayımdır ve kanıtlanabilir güvenliğin üzerine inşa edildiği temeli oluşturmaktadır.
Kapsam
Bu konu, kriptografinin dayandığı varsayımları kapsamaktadır: tek yönlü fonksiyonların varlığı, sayı teorisi problemleri (çarpanlara ayırma, RSA, ayrık logaritma) ve kuantum sonrası kriptografide kullanılan kafes ve kod problemleri. Varsayımlar arasındaki hiyerarşiyi, en kötü durum ve ortalama durum zorluğu arasındaki ayrımı ve varsayımların nasıl doğrulandığını ele almaktadır. Varsayımları şemalarla ilişkilendiren indirgeme mekanizmalarını ve kardeş konularda ele alınan güvenlik tanımlarının kendilerini içermemektedir.
Temel sorular
- Kriptografik güvenlik neden kanıtlanmamış zorluk varsayımlarına dayanmak zorundadır?
- Başlıca varsayımlar nelerdir (tek yönlü fonksiyonlar, çarpanlara ayırma, ayrık logaritma, kafesler)?
- Varsayımlar güç açısından birbirleriyle nasıl ilişkilidir?
- En kötü durum ve ortalama durum zorluğu arasındaki fark nedir?
- Aday zor problemler nasıl incelenir ve biri başarısız olduğunda ne olur?
Anahtar kavramlar
- tek yönlü fonksiyon
- tuzak kapılı fonksiyon
- tam sayı çarpanlara ayırma varsayımı
- ayrık logaritma varsayımı
- RSA ve Diffie-Hellman varsayımları
- hatalarla öğrenme (LWE)
- en kötü durum ve ortalama durum zorluğu
- P'ye karşı NP
- varsayım hiyerarşisi
Temel kuramlar
- Minimal bir varsayım olarak tek yönlü fonksiyonlar
- Tek yönlü fonksiyonların (hesaplanması kolay, tersine çevrilmesi zor) varlığı, simetrik kriptografinin çoğu için gerekli ve yeterlidir ve en temel varsayımdır; kriptografinin neredeyse tamamı en azından bunu ön varsaymaktadır.
- Sayı teorisi ve kafes varsayımları
- Açık anahtarlı kriptografi, yapılandırılmış problemlere dayanmaktadır — tam sayı çarpanlara ayırma, RSA problemi ve ayrık logaritmalar (klasik olarak) ile kafeslerdeki hatalarla öğrenme ve en kısa vektör problemleri (kuantum sonrası) — her biri onlarca yıllık kriptoanalitik incelemeyle desteklenmektedir.
Mekanizmalar
Kriptografi, anahtarlar rastgele seçildiği için sadece en kötü durumda değil, ortalama olarak (rastgele örnekler üzerinde) zor olan problemlere ihtiyaç duymaktadır. Varsayımlar kabaca bir hiyerarşi içinde düzenlenmektedir: daha zayıf bir varsayımın (örneğin çarpanlara ayırma) kırılması, genellikle üzerine inşa edilen şemaları da kırmaktadır; indirgemeler ise varsayımları birbirine bağlamaktadır. Kafes varsayımları, en kötü durumdan ortalama duruma indirgemeleriyle dikkat çekmekte ve daha güçlü bir güven sağlamaktadır. Herhangi bir varsayıma duyulan güven, kanıttan ziyade, uzun süreli ve başarısız kriptoanalitik çabalardan gelmektedir.
Klinik önem
Zorluk varsayımları, neyin güvenli bir şekilde dağıtılabileceğini ve neyin dağıtılamayacağını belirlemektedir. Kuantum bilgisayarların çarpanlara ayırma ve ayrık logaritmaları (Shor algoritması aracılığıyla) kıracağı keşfi, RSA ve eliptik eğri kriptografisinin kuantum düşmanlarına karşı dayandığı varsayımları geçersiz kılmış ve doğrudan kafes tabanlı kuantum sonrası standartlara geçişi tetiklemiştir. İyi incelenmiş varsayımlar üzerine inşa edilmiş şemaları seçmek ve bunların durumunu takip etmek, uzun vadeli güvenlik için hayati önem taşımaktadır.
Kanıt ve kılavuzlar
Standart belirleyici kurumlar, uzun kriptoanalitik geçmişe sahip varsayımları tercih etmektedir; NIST'in kuantum sonrası süreci, temel kafes, kod ve hash varsayımlarının olgunluğunu ve güvenilirliğini açıkça değerlendirmiştir. En iyi uygulama, yüksek güvenceli sistemler için egzotik veya yeni önerilen varsayımlardan kaçınmakta ve anahtar boyutları bilinen en iyi saldırılara göre belirlenmiş, muhafazakar, iyi incelenmiş problemleri tercih etmektedir.
Tarihçe
Zorluğa dayalı yaklaşım, 1976 yılında Diffie ve Hellman'ın güvenliği ayrık logaritmaya, RSA'nın ise çarpanlara ayırmaya bağlamasıyla açık anahtarlı kriptografi ile ortaya çıkmıştır. 1980'ler tek yönlü fonksiyonları ve en kötü durum/ortalama durum ayrımını resmileştirmiştir. Ajtai'nin en kötü durumdan ortalama duruma indirgemeleri (1996) ve Regev'in hatalarla öğrenme problemi (2005), kuantum dirençli temeller olarak önem kazanan ve yeni kuantum sonrası standartların temelini oluşturan kafes varsayımlarını tesis etmiştir.
Öne çıkan isimler
- Whitfield Diffie
- Martin Hellman
- Oded Goldreich
- Oded Regev
- Andrew Yao
İlgili konular
Temel eserler
- diffie1976
- goldreich2001
- katz2020
Sıkça sorulan sorular
- Bu problemlerin zor olduğunu neden kanıtlayamıyoruz?
- Bir problemin süper-polinom zaman gerektirdiğini kanıtlamak, karmaşıklık teorisindeki (özellikle P'ye karşı NP) derin açık soruları çözecektir, ancak bunlar henüz çözülememiştir. Bu nedenle kriptografi, güvenilirliği onları verimli bir şekilde çözme girişimlerinin onlarca yıldır başarısız olmasından gelen varsayımlara dayanmaktadır.
- Bir zorluk varsayımı kırılırsa ne olur?
- Güvenliği o varsayıma indirgenen her şema potansiyel olarak güvensiz hale gelmekte ve değiştirilmesi gerekmektedir. Çarpanlara ayırma ve ayrık logaritmalara yönelik kuantum tehdidinin, farklı, kuantum dirençli varsayımlara dayalı şemalara küresel bir geçişi tetiklemesinin nedeni budur.