Studies On Provably Secure Public-Key Encryption In The Standard Model

Indistinguishability against adaptive chosen-ciphertext attack(IND-CCA) has been widely accepted as the right notion of security for public-key encryption. It essentially requires that the adversary can observe the input/output behavior to a scheme, but gets no further information about the internal states of the scheme. That is, beside the public key, the secret key is both leakage-proof and tamper-proof to the adversary and the message involved in a ciphertext is independent of the secret key. In a real life,however, it may be far from this case. For example, through side-channel attacks, an adversary may obtain partial information of the secret key and/or tamper with the internal states. In addition, the harddisk encryption technique i.e., Bit Locker, used in Windows Vista operation system may encrypt the secret key along with the disk contents. Indeed, many schemes(like the Cramer-Shoup encryption scheme), which were proved secure in the IND-CCA security model, are not immune to these new types of attacks at all. In this paper, we will study how to design PKE schemes that are provably secure(i.e., IND-CCA secure) in these new scenarios in the standard model. Our results are summarized as follows:1. We made an improved Hofheinz-Kiltz CCA secure key-encapsulation mechanism from Eurocrypt’09, under the intractability of factoring in the standard model. Compared with the original HK09 encryption scheme, the efficiency of decapsulation is improved by 23.6%.2. In the presence of key leakage, efficient BKL-CCA secure PKE schemes are mainly constructed via hash proof system(HPS). However, HPS-based approaches usually suffer from low leakage-rate. We proposed a new and general method to improve the leakage-rate in HPS-based constructions. Particularly, we proposed a new primitive namely tag-based HPS. Applying unversal2tag-based HPS, we obtained a DDH-based(resp. DLIN-based) PKE scheme where the leakage-rate can be made to 1/4- o(1)(resp. 1/6- o(1)). The DDH-based scheme achieves the best leakage-rate among all known DDH-based Cramer-Shoup-type(based on HPS) schemes. The DLIN-based scheme is the first one that can achieve leakage rate of 1/6- o(1) without pairing.3. Theoretically, the leakage-rate in HPS-based schemes is at most 1/2-o(1). However, practical approaches can only achieve 1/4- o(1). To overcome this issue,we proposed a new construction of BKL-CCA secure PKE scheme from universal HPS and a new cryptographic primitive, namely one-time lossy filter. Instantiations from the DDH and DCR assumptions result in practical BKL-CCA secure PKE schemes with leakage-rate of 1/2- o(1). Through the same technique, we also proposed the first CCA secure PKE scheme with flexible leakagerate(i.e., 1- o(1)) even without pairing.4. Related-key attacks(RKAs) allow an adversary to observe the outcomes of a cryptographic primitive under not only its original secret key, but also a sequence of modified keys. We proposed a framework for constructing RKA-secure PKE and IBE schemes from a new cryptographic primitive, namely continuous nonmalleable key-derivation function. We realized the new primitive for any polynomial tampering functions of bounded degree. All the primitives used in our framework can be instantiated under standard assumptions, and hence solved the problem that relies on non-standard assumptions in previous RKA-secure schemes for polynomial tampering functions.5. Key-dependent message(KDM) encryption can be viewed as a special key-leakage function. However, designing KDM-CCA secure encryption schemes are more challenging. When the message is the difference between any two secret keys, we showed that the traditional Cramer-Shoup scheme tailored for encryption of secret key is KDM-CCA secure in the standard model. The tailored Cramer-Shoup cryptosystem is very efficient and applicable in anonymous credential systems.