Design Of Adaptive Chosen Ciphertext Secure Public Key Encryption Scheme

Adaptive chosen ciphertext security (IND-CCA2) is now commonly accepted as the standard notion for public key encryption schemes, yet there has been no systematic principle for the design of IND-CCA2 secure schemes. As a result it has been considered as an art rather than a science. This thesis deals with the principle of IND-CCA2 secure public key encryption design, the assessment of IND-CCA2 security, improvement of IND-CCA2 secure ElGamal family schemes and the security notion for hybrid encryption scheme.The design principle of IND-CCA2 secure schemes is systematically described from the view of forward and backward. From the forward perspective, the information leaks of the decryption oracle are classified and the ways to prevent them are analyzed. From the backward perspective, the contradiction between decryption simulation and the basic design idea of public key encryption scheme is pointed out and the way to solve it is analyzed. Finally, from the view of information theory, the gaps between intractable problems and IND-CCA2 security and the methods to bridge them are analyzed. Consequently, the thesis comes to a systematic description of the design principle of IND-CCA2 secure schemes, and also an intuition about the difficulty of designing IND-CCA2 secure public key encryption schemes based on different types of assumptions.The reduction proof of IND-CCA2 security for public key encryption scheme is very complex, and a public key encryption scheme that is not reduction provable secure may not necessarily be insecure. To assess the IND-CCA2 security of public key encryption schemes, the gray-box analysis of IND-CCA2 security is proposed in which a detailed classification of the information leaks of the decryption oracle is presented. Compared with the reduction proof, gray-box analysis is much simpler and easier to understand, and more suitable to be used as an assessment of the public key encryption scheme's IND-CCA2 security. Most importantly, through the analysis of the decryption oracle's information leaks, the cause of the insecurity can be found, which give suggestions on the design and improvement of IND-CCA2 schemes.A new efficient variant of the ElGamal public key encryption scheme is proposed and proved to be adaptive chosen ciphertext secure under a new assumption-the Restricted Oracle Diffie-Hellman (RODH) assumption-in the standard model. A variant of ODH assumption, the Constrained Oracle Diffie-Hellman assumption (CODH), is proposed which is weaker than the ODH assumption. Under the CODH assumption, the DHIES scheme is proved to be secure against adaptive chosen ciphertext attacks. A variant of Kiltz07-KEM is proposed with improved efficiency in encryption. The new scheme can be proved IND-CCA2 secure under the same hardness assumption. This makes the most efficient KEM provably IND-CCA2 secure in the standard model until today.In light of the feature of hybrid encryption scheme, a new security definition, secure against weak adaptive chosen ciphertext attacks (IND-WCCA2), is proposed. The definition of IND-WCCA2 is similar to that of IND-CCA2 (adaptive chosen ciphertext attacks), while the only difference lies in that the adversary is not allowed to query ciphertexts whose KEM part remains the same as that of the challenge ciphertext. In situations that the KEM part is not reused, IND-WCCA2 security is as suitable as the IND-CCA2 security, while the resulting scheme is more efficient.