On provable security of some public key encryption schemes

Abstract

Bu tezde, bazı açık anahtar şifreleme sistemlerinin güvenlik kriterlerini analiz ediyoruz. Bu anlamda, sistemi kırmaya çalışanın amacını ve bu amaca yönelik kapasitelerini sunuyoruz. Standart modelde ve rastgele kahin modelinde sistem kırıcı ile oynanan çeşitli oyunlar vasıtasıyla ispatlanabilir güvenliğin tanımını veriyoruz. Bu iki model arasındaki esas farkları belirtiyoruz ve kriptografik sistemlere saldıran düşmanın başarı olasılığının avantajını gözlemliyoruz. Zayıf varsayımlar altında verimli, pratikte kullanışlı ve güvenliği ispatlanmış sistemler yapmanın yollarını arıyoruz. Bu amaç doğrultusunda RSA, ElGamal, Cramer-Shoup, Paillier, Damgard ve son olarak Zheng-Seberry açık anahtar şifreleme sistemlerinin yapılarını inceliyoruz ve bu sistemlerin hangi durumlarda hangi güvenlik notasyonlarını sağladıklarını açıklıyoruz. Son olarak, Zheng-Seberry'in önerdiği ElGamal imzasına dayanan sistemi Schnorr imza algoritması kullanarak modifiye ederek daha etkili bir sistem elde ediyoruz ve bu sistemin rastgele kahin modelinde güvenli olduğunu ispatlıyoruz.

In this thesis, we analyse the security criteria of some public key encryption schemes. In this respect, we present the notion of adversarial goals and adversarial capabilities. We give the definition of provably security by means of several games between the challenger and the adversary in some security models, namely the standard model and the random oracle model. We state the main differences between these two models and observe the advantage of the success probability of the adversary in breaking the cryptographic schemes. We search the ways of making more efficient and provably secure encryption schemes under weak assumptions. In this context, we examine the constructions of some public key encryption schemes such as RSA, ElGamal, Cramer-Shoup, Paillier, Damgard and finally Zheng-Seberry schemes and discuss under which circumstances they satisfy which security notions. Finally, we modify one of the schemes proposed by Zheng-Seberry -which is based on ElGamal signature- by adapting Schnorr signature in order to enhance the efficiency and give a rigorous proof of security in the random oracle model.