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

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

Syed Taqi Ali (National Institute of Technology Kurukshetra, India)
Copyright: © 2020 |Pages: 25
DOI: 10.4018/978-1-7998-1763-5.ch013

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.
Chapter Preview
Top

Introduction

In the early years after the invention of public key cryptography by Diffie and Hellman in 1976 (Diffie & Hellman, 1976), design and evaluation of public key cryptosystems has been done merely in an ad-hoc manner. That is the fact that the cryptosystem which withstood cryptanalytic attacks for several years is considered to be a secure cryptosystem. But there are many cryptosystems which have been broken after long time of their design. For example, Chor-Rivest cryptosystem (Chor & Rivest, 1985), (Lenstra, 1991), based on the knapsack problem, took more than 10 years to break totally (Vaudenay, 1998), whereas, before this attack it was believed that it is strongly secure. Due to various similar successful attacks on the cryptosystems, the cryptographic community understood that the lack of attacks at some time should never be considered as a security validation and demands the mathematical proof which guarantees the security of cryptosystems.

Complete Chapter List

Search this Book:
Reset