Rassal Kahin

Şifrelemede rassal kahin, kendisine yapılan her sorguya, çıktı uzayından (gerçekten) rastgele, eşit olasılıkla seçilmiş, fakat her bir ayrı sorguya her seferinde aynı şekilde cevap veren bir kahin (kuramsal bir kara kutu)'dur. Başka bir deyişle, rassal kahin olası her bir sorguyu çıktı uzayından rastgele bir yanıta eşleyen matematiksel bir fonksiyondur.

Rassal kahinler, şifreleme bilimindeki kanıtlarda kullanılan bir matematiksel soyutlamadır; bunlar genellikle kanıtın gerektirdiği matematiksel özellikleri sağlayan bilinen gerçeklenebilir bir fonksiyon bulunmadığında kullanılmaktadır. Bu şekilde kanıtlanarak güvenli olduğu gösterilen bir sistem standart modeldeki güvenli kavramına karşılık olarak rassal kahin modelinde güvenli olarak tanımlanır. Uygulamada, rassal kahinler genellikle özet fonksiyonunun çıktısı hakkında güçlü rassal varsayımların gerektiği şemalara sahip şifreleme özüt fonksiyonlarını modellemek amacıyla kullanılır. Böyle bir kanıt, genel olarak bir sistemin veya bir protokolün, bir saldırganın protokolü kırabilmesi için ya kahinden olanaksız bir davranış görmesi gerektiğini ya da zor olduğuna inanılan matematiksel bir problemi çözmesi gerektiğini göstererek güvenli olduğunu gösterir. Bütün şifreleme özüt fonksiyonları rasssal kahinler gerektirmez: sadece çakışma dirençlilik özelliğini gerektiren şemaların standart modelde güvenliliği kanıtlanabilir (örn. Cramer-Shoup şifreleme sistemi).

Rassal kahinler Karmaşıklık Kuramında uzun zamandır kabul görmüştür. (örn. Bennett & Gill^[1]). Fiat ve Shamir (1986)^[2] imza üretimi protokollerinden etkileşimin çıkarılması konusunda rasssal kahinlerin önemli bir uygulamasını yapmışlardır. Impagliazzo ve Rudich (1989)^[3] sadece rasssal kahinlerin varlığının gizli anahtar değişimi için yeterli kanıt olmadığını söyleyerek rasssal kahin modelinin sınırlarını göstermişlerdir. Bellare ve Rogaway (1993)^[4] şifreleme yapılarında onların kullanımını savunmuştur. Bu tanımda, rassal kahin istenilen uzunluğa kesilebilecek olan sonsuz uzunlukta bir bit-dizgesi üretir. Bir rassal kahin bir güvenlik kanıtı içinde kullanıldığında, rakip ya da rakipler de dahil olmak üzere tüm oyuncular için kullanılabilir durumdadır. Tek bir rassal kahine her sorgudan önce sabit bir bit-dizgesi eklenerek (örn. başına "1|x" ya da "0|x" eklenmiş sorgular iki ayrı rassal kahine yapılmış gibi, benzer olarak "00|x", "01|x", "10|x" ve "11|x" eklenmiş sorgular da dört ayrı rassal kahine yapılmış sorgular gibi kabul edilebilir) birden fazla kahin gibi davranılabilir.

Hiçbir gerçek fonksiyon gerçek bir rassal kahini gerçekleyemez. Aslında, rassal kahin modelinde güvenliliği kanıtlanmış olan bazı yapay imza ve şifreleme şemalarının, rassal kahin yerine herhangi bir gerçek fonksiyon kullanıldığında basitçe güvensiz olduğu bilinmektedir.^[5] Bununla birlikte, herhangi bir daha doğal protokol için rassal kahin modelindeki bir güvenlik kanıtı, varsa (tamsayıların çarpanlara ayrılmasının zorluğu gibi) kanıtın diğer varsayımlarını kırmayan herhangi bir saldırının protokolde kullanılan özüt fonksiyonunun bilinmeyen ve istenmeyen bir özelliğini keşfetmesini gerektiren çok güçlü göstergeler sunar. Birçok şemanın rassal kahin modelinde güvenli olduğu gösterilmiştir, örnek olarak OAEP ve PSS verilebilir.

• Kahin makinesi
• Standart Model (şifreleme)
• Şifreleme içerisindeki konular

1. ^ Bennett, Charles H.; Gill, John (1981), "Relative to a Random Oracle A, P^A != NP^A != co-NP^A with Probability 1", SIAM Journal on Computing, 10 (1), ss. 96-113, ISSN 1095-7111 
2. ^ Amos Fiat and Adi Shamir: How to Prove Yourself: Practical Solutions to Identification and Signature Problems. CRYPTO 1986: pp. 186-194
3. ^ Russell Impagliazzo and Steven Rudich: Limits on the Provable Consequences of One-Way Permutations STOC 1989: pp. 44-61
4. ^ Mihir Bellare and Phillip Rogaway, Random Oracles are Practical: A Paradigm for Designing Efficient Protocols, ACM Conference on Computer and Communications Security 1993, pp. 62–73 (PS and PDF 4 Mayıs 2008 tarihinde Wayback Machine sitesinde arşivlendi.).
5. ^ Ran Canetti, Oded Goldreich and Shai Halevi, The Random Oracle Methodology Revisited, STOC 1998, pp. 209–218 (PS and PDF).

• Rassal Kahin Modeli - Helger Lipmaa tarafından düzenlenen bağlantılar