Provable Security for Public Key Cryptosystems: How to Prove that the Cryptosystem is Secure

Abstract

In the early years after the invention of public key cryptography by Diffie and Hellman in 1976, the design and evaluation of public key cryptosystems has been done merely in ad-hoc manner based on trial and error. The public key cryptosystem said to be secure as long as there is no successful cryptanalytic attack on it. But due to various successful attacks on the cryptosystems after development, the cryptographic community understood that this ad-hoc approach might not be good enough. The paradigm of provable security is an attempt to get rid of ad hoc design. The goals of provable security are to define appropriate models of security on the one hand, and to develop cryptographic designs that can be proven to be secure within the defined models on the other. There are two general approaches for structuring the security proof. One is reductionist approach and other is game-based approach. In these approaches, the security proofs reduce a well known problem (such as discrete logarithm, RSA) to an attack against a proposed cryptosystem. With this approach, the security of public key cryptosystem can be proved formally under the various models viz. random oracle model, generic group model and standard model. In this chapter, we will briefly explain these approaches along with the security proofs of well known public key cryptosystems under the appropriate model.