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.
TopIntroduction
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.
Key Terms in this Chapter
Public Key Cryptography: Public key cryptography or Asymmetric cryptography is a group of algorithms or protocols where two, related and distinct, keys are involved, one is called secret (or private) key and other is called public key. Public-key encryption schemes and signature schemes are examples of public key cryptography.
Exact Security: Proving the security of the cryptosystem with exact bounds and relations with respect to its input key length.
Negligible Function: The function is negligible if it vanishes faster than the inverse of any polynomial. Formally, is negligible if for every constant there exists an integer such that for all .
Adaptive Chosen-Ciphertext Attack (CCA2): In CCA2, adversary knows the public key (through which she can only encrypt messages of her choice) and has access to decryption oracle even after the challenge ciphertext is given to her, but with the restriction that she cannot query challenge ciphertext to the decryption oracle. Later adversary chooses two challenge messages, after which she is given a challenge ciphertext (which is the encryption of one of the challenge messages). We say a public key encryption scheme is secure under CCA2 if it is hard for an adversary to relate the challenge ciphertext to its plaintext.
Existential Forgery: Adversary succeeds in breaking the underlying signature scheme if she is able to forge the signature of at least one message of her choice.
Indistinguishability or Semantic Security: Unable to learn any information about the underlying plaintext when given a challenge ciphertext in the public key encryption scheme.
Total Break: The signature scheme is said to be total bread is adversary is able to compute the signer’s secret key.
Random-Oracle Model: Proving the security of the cryptosystem with the assumption that the underlining primitives, such as hash functions, works in an ideal form, i.e. assuming it to be a pure random function.
Generic Group Model: Proving the security of the cryptosystem with the assumption that the attacker did not utilize the special properties of the underlining implementation details or she is unaware of the underlining implementation details at the time of breaking the cryptosystem.
Chosen-Ciphertext Attack (CCA1): In CCA1, adversary knows the public key (through which she can only encrypt messages of her choice) and also given an access to decryption oracle (through which she can get the decryption of ciphertext of her choice) before the challenge ciphertext is produced. Later adversary chooses two challenge messages, after which she is given a challenge ciphertext (which is the encryption of one of the challenge messages). We say a public key encryption scheme is secure under CCA1 if it is hard for an adversary to relate the challenge ciphertext to its plaintext.
Chosen Message Attack (CMA): In the signature scheme, adversary is allowed to get the signature of number of messages, of her choice, from the signer (i.e. has access to signature oracle).
Chosen-Plaintext Attack (CPA): In CPA, adversary knows only the public key, through which she can only encrypt messages of her choice, and later allowed to choose two challenge messages, after which she is given a challenge ciphertext (which is the encryption of one of the challenge messages). We say a public key encryption scheme is secure under CPA if it is hard for an adversary to relate the challenge ciphertext to its plaintext.
Known Signature Attack (KSA): In the signature scheme, adversary knows the public key of the signer and has list of message/signature pairs, not of her choice.
Key-Only Attack: In the signature scheme, adversary knows only the public key of the signer and therefore she can only check the validity of signatures of the messages given to her.
Selective Forgery: Adversary succeeds in breaking the underlying signature scheme if she is able to forge the signature of some message selected prior to the attack.
Universal Forgery: Adversary succeeds in breaking the underlying signature scheme only if she is able to forge the signature of any given message.
Provable Security: Provable security in cryptosystem is formally proving the security of the underline cryptosystem.