Research On KDM Secure And Other Related Cryptographic Schemes

With the further applications of information technology, the problem of information security becomes increasingly serious. As a core tool of information security, cryptography has attracted many attentions in the literatures. It is generally considered that the most basic task in this field is to construct cryptographic schemes satisfing certain security definitions. Provable security is a formal method for designing and analyzing the security of cryptographic schemes, in which the hardness of breaking a particular scheme is formally related to that of solving a well-known hard problem in mathemathics. Generally, it is assumed that the encrypted messages should be independent of the secret key in the process of security reduction. However, the encrypted messages does depend on the secret key in certain complicated scene, such as bootstrapping in the construction of fully homomorphic encryption schemes. It is a significant challenge to present new schemes that can be proven secure in this special case. The notation of key-dependent message (KDM) security is proposed to analyze and solve this problem. In this paper, several concerned problems on KDM security have been investigated. The main results are as follows.1. We propose a new symmetric encryption scheme in the the ideal cipher model (ICM), and prove it to be KDM secure against active attacks with respect to arbitrary polynomial time challenge functions. Compared with other related results, the advantages of our scheme are that of simplicity in constrcution, large set of challenge functions, and security against active attacks. The theoretical contribution of this scheme is that of a novel method of KDM secure symmetric encryption schemes.2. Through analyzing the primitive of lossy trapdoor function, we know that all existing lossy trapdoor functions might not be provably secure when the adversary previously gets the related information on the trapdoor. It will be of great significance to develop new lossy trapdoor functions provably secure under this circumstance. Thus we first present a new lossy trapdoor function based on the d-linear assumption, and prove it to be auxiliary-input secure by using an extended version of the Goldreich-Levin theorem. Then we show that a slight variant of Peikert’s LWE-based lossy trapdoor function is also auxiliary-input secure. Finally, we analyze both of lossy trapdoor functions in efficiency and security.3. We present a new method of constructing a KDM secure asymmetric encryption scheme with the notation of hybrid encryption in the standard model. Our result can also be seen as a partial instantiation for a previously well-known KDM secure asymmetric encryption scheme based on random oracle. As we know, this has never been carried out before. Throughout the paper, our main idea is to archive KDM security by making use of both leakage-resilience and auxiliary-input security properties.4. We present an efficient universal hash proof system based on the LWE assumption. It is clearly that this new system can be also used to construct a new IND-CCA2 secure public-key encryption scheme based on the LWE assumption and the ISIS assumption. Through analyzing properties of the above IND-CCA2 secure scheme, we find it can be proven to be KDM secure against adaptive chosen ciphertext attacks with respect to a special family of chanllege functions.