Research On Security Proof For Public-key Cryptosystems

In 1976, Diffie and Hellman published their paper"New directions in cryptography". It is regarded as a milestone for the research and development of cryptography. In their paper they first introduced public-key cryptography, also named asymmetric cryptography. Since then, public-key cryptography has been widely applied in encryption, digital signature, key exchange, and so on. Consequently, more and more attentions have being focused on the securities of public-key cryptosystems. It is desired that there is an approach which can be used to evaluate the security of the public-key cryptosystems before they are deployed. This approach is called"provable security". At the heart of any public-key cryptosystem is a"one-way function"—a function that is easy to evaluate but for which it is computationally infeasible to find the inverse. This one-way function is constructed from some well-studied problem that is thought to be difficult, such as factoring integers or calculating discrete logarithm. The provable security approach can be described as follows:"This approach is to provide evidence of security by reducing the security of the public-key cryptosystem to some well-studied problem that is though to be difficult." Public-key cryptosystems are desired to be as secure as the underlying one-way functions or the difficult problems. Unfortunately, a large proportion of the available public-key cryptosystems can not reach this objective. Some famous public-key cryptosystems were improved to provide provable securities. For example, Bellare and Rogaway proposed OAEP (Optimal Asymmetric Encryption Padding) for RSA function. Cramer and Shoup proposed Cramer-Shoup public-key cryptosystem from ElGamal public-key cryptosystem. They proved that their improved schemes, both RSA-OAEP public-key cryptosystem and Cramer-Shoup public-key cryptosystem, are as secure as the difficulties of computing the underlying one-way functions.This dissertation focuses on the security proofs and the proving methods for public-key cryptosystems. The main contents are as follows:Firstly, we study the mathematical definitions of the securities for public-key cryptosystems, along with a well research on proving models and proving methods. We mostly study the reduction to contradiction method under random oracle model and standard model. An attack on a public-key cryptosystem can be reduced into a solution for the underlying difficult problem. Since we know that the difficult problem is computationally infeasible, that means the attack does not exist. Namely, the public-key cryptosystem is secure against the attack. In a security proof under standard model, we only need the one-wayness of the underlying function. However, in a security proof under random oracle model, besides the one-wayness of the underlying function, we also need to assume that the cryptographic hash functions used in the cryptosystem have security attributes of random oracle.Secondly, we improve the proving methods raised by Bellare and Rogaway for public-key cryptosystem f-OAEP and fix the flaw found by Shoup. We study Bellare and Rogaway's security proof carefully and analyze the flaw Shoup found in their proof. Compared with the original security proof and existent improvements, the revised proof is complete and applicable for the underlying one-way function being a general case. We also make a cryptanalysis on a series of improvements on OAEP. Using hybrid cryptosystem method, we modify OAEP conversion a little and present OAEP++. We also prove in random oracle model, that the public-key cryptosystem f-OAEP++ is secure against adaptive chosen-ciphertext attack.Thirdly, we design a novel key exchange protocol based on RSA-OAEP cryptosystem. We study a series of Diffie-Hellman key exchange protocol which are integrated into Digital Signature Algorithm (DSA) to achieve mutual authentication of the established keys. To securely establish some session keys, two parties need to select and exchange some random parameters in a secret manner, which are going to be used to calculate session keys and authenticate each other. The key exchange protocol also should provide some standard security attributes, such as forward secrecy and key freshness. RSA-OAEP public-key cryptosystem can do this easily. In our protocol, two parties respectively select two random numbers as the input of OAEP transformation. Then encrypt the transformed result using the other's public key through RSA function. So the two parties can exchange two random numbers securely and can authenticate each other when the opposing party decrypt the message using his private key and continue the protocol. Our protocol can provide mutual authentication without using pre-shared information or integrating digital signature. It also can provide forward secrecy and key freshness. Contrast to those key exchange protocols based on discrete logarithm, we give a secure and efficient option when negotiating session keys in RSA public-key cryptosystems.Finally, we study the security proof for public-key cryptosystem under standard model. In this regard, we study the Cramer-Shoup public-key cryptosystem, the first practical cryptosystem that offers a mathematical guarantee of security against adaptive chosen-ciphertext attack under standard model. We find that cryptographic hash functions could be replaced by discrete logarithm functions in some scenarios, such as mixing-transformation and message integrity verification. Secure discrete logarithm functions also have collision resistance and pre-image resistance, which are some security attributes that cryptographic hash functions should have. To achieve security against adaptive chosen-message attack, Cramer and Shoup integrated DDH problem into ElGamal public-key cryptosystem to implement message integrity verification. We do a similar job to Chang's digital signature scheme. We also integrated discrete logarithm function into Chang's scheme to check the message integrity. Under standard model, we prove that our improved scheme is unforgeable against chosen-message attack as ElGamal triplet signatures.