Olasılıksal şifreleme

Probabilistik kriptosistem şifreleme algoritması içinde rastgeleselliğin kullanımıdır böylece aynı mesaj birçok kez şifrelendiğinde genel olarak farklı şifreli metinler üretecektir.

Probabilistik şifreleme terimi tipik olarak açık anahtar şifreleme algoritmalarına referans olarak kullanılmıştır ancak çeşitli simetrik anahtar şifreleme algoritmaları aynı özelliği başarabilir (mesela blok şifreleyiciler şifreleyici blok zinciri modunda kullanıldığında). Anlamsal olarak güvenli olması için, yani düzmetin hakkındaki kısmi bilgiyi bile hasımdan saklamak için, bir şifreleme algoritması probabilistik olmalıdır.

Probabilistik şifreleme özellikle açık anahtar kriptografi kullanıldığında önemlidir. Varsaylım hasım şifreli metni gözlemleyebilsin ve düz metnin ya Evet ya da Hayır olduğundan şüphelensin veya düz metnin [Calais saldırısı] olabileceğini sezinlesin. Bir belirlenimci veya deterministik şifreleme algoritması kullanıldığında hasım basitçe alıcının açık anahtarı altında kendi tahminlerinin her birini şifrelemeyi deneyebilir ve her bir sonucu hedef şifreli metinle karşılaştırır. Bu atakların üstesinden gelmek için, açık anahtar şifreleme şemaları rastgeleleliğin bir elamanını kapsayacak şekilde her bir düz metni mümkün olduğunca çok sayıda şifreli metinle eşleştirmeyi garanti etmelidir.

Belirlenimci şifreleme yöntemini probabilistik şifreleme yöntemine dönüştürmeye sezgisel bir yaklaşım basitçe deterministik algoritmayla şifrelemeden önce rastgele bir string ile düz metni genişletmektir. Buna karşın, deşifreleme, deterministik algoritmaya başvurmayı ve rastgele eklemeyi yok saymayı içermektedir. Bununla birlikte bu kaba kuvvet yaklaşımına başvuran önceki yöntemler bazı deterministik şifreleme yöntemleri içindeki sınırlamalar yüzünden kırılmıştır. Optimal asimetrik şifreleme ekleme (OAEP) gibi teknikler rastgele eklemeyi herhangi bir tek yönlü fonksiyon permütasyonu kullanarak güvenli olan bir tarzda düz metnin içerisine entegre eder.

İlk kanıtlanabilir güvenli probabilistik açık anahtar şifreleme yöntemi kuadratik kalan probleminin zorluğuna ve açık anahtar boyutuna eşit mesaj genişletme faktörüne dayanılarak Shafi Goldwasser ve Silvio Micali, tarafından önerilmiştir.Daha verimli probabilistik algoritmalar Elgamal, Pailier ve rastgele oracle modeli altındaki değişik yapılardır ve optimal asimetrik şifreleme ekleme(OAEP) içerirler.

Herhangi bir trapdoor permutasyonu kullanarak Probabilistik şifreleme örneği

x - tek bit tek bir düzmetin
f - tekyönlü fonksiyon (deterministik şifreleme algoritması)
b - tahmini zor bir kökü f nin
r - rastgele string

${\rm {Enc}}(x)=(f(r),x\oplus b(r))$

${\rm {Dec}}(y,z)=b(f^{-1}(y))\oplus z$

Bu verimsizdir çünkü sadece tek bir bit şifrelendi.Diğer bir deyişle mesaj genişletme faktörü açık anahtar boyutuna eşittir.

Rastgele oracle model içinde probabilistik şifreleme örneği

x - düzmetin
f - tekyönlü fonksiyon (deterministik şifreleme algoritması
h - random oracle (tipik implementasyonu açık belirli bir hash fonksiyonu kullanılarak yapılır)
r - rastgele string

${\rm {Enc}}(x)=(f(r),x\oplus h(r))$ ${\rm {Dec}}(y,z)=h(f^{-1}(y))\oplus z$