Constructions And Security Proofs Of Public-Key Encryption Under Selective Opening Attacks

The definitions of selective opening security(SOA security) for public-key encryption(PKE) schemes were formalized by Bellare, Hofheinz and Yilek in Eurocrypt2009. These definitions, which focus on data security in multiuser environment, capture a situation that a large number of senders encrypt their own messages with the public key of a single receiver. Assume that, besides seeing the ciphertexts, the adversary can also corrupt some of the senders, obtaining their messages and randomness consumed during the encryption. SOA security requires that the messages of the uncorrupted senders are still confidential.So far there are mainly two kinds of SOA security notions: simulation-based SOA(SIM-SOA) security and indistinguishability-based SOA(IND-SOA) security. For a security notion, it is necessary to specify the corresponding attack model. According to ascending security strength, the common attack models are chosen-plaintext attack(CPA), non-adaptive chosen-ciphertext attack(CCA1), and adaptive chosen-ciphertext attack(CCA2). Correspondingly, SIM-SOA(resp. IND-SOA) security notions include SIM-SO-CPA security, SIM-SO-CCA1 security, and SIM-SO-CCA2 security(resp.IND-SO-CPA security, IND-SO-CCA1 security, and IND-SO-CCA2 security).A lot of research has been done on SOA security for PKE since its formalization.The research mainly focuses on achieving SOA security, and exploring the relations among the known SOA security notions. For achieving SOA security, up to now there are mainly two methods: one is via a lossy encryption scheme, proposed by Bellare,Hofheinz and Yilek in Eurocrypt 2009, and the other is via a non-committing encryption scheme, proposed by Fehr, Hofheinz, Kiltz and Wee in Eurocrypt 2010. With respect to the relations among the known SOA security notions, so far there are some important conclusions, such as that SIM-SO-CPA security implies IND-SO-CPA security, and that no binding committing encryption scheme is SIM-SO-CPA secure.Generally speaking, progress has been made on SOA security in the past few years.However, there are still many open questions left. For example, the constructions of all-but-many lossy trapdoor function(Eurocrypt 2012), which is relevant to achieving SOA security, are based on non-classical assumptions, and their security reductions are not tight. Another example is non-malleability for PKE. According to Pass, Shelat and Vaikuntanathan(Asiacrypt 2007), the relations among the known non-malleability notions are complicated. No research on non-malleability for PKE under selective opening attacks has been done yet.Our research focuses on SOA security. Our contributions are as follows.1. We propose two constructions of SIM-SO-CCA2 secure PKE schemes. Our constructions are based on the non-committing encryption scheme(the FHKW scheme) proposed by Fehr, Hofheinz, Kiltz and Wee in Eurocrypt 2010. In this paper, we provide an analysis of security proof of the FHKW scheme, and show that the proof of sender-equivocability under adaptive chosen-ciphertext attacks(NC-CCA2 security) in Fehr et al.’s work is flawed. More specifically,in the original security proof, Fehr et al. constructed a simulator and “proved”that the ideal experiment, provided by the simulator, and the real experiment are computationally indistinguishable. However, we present an adversary, which can distinguish those two experiments with overwhelming advantage. In order to solve the problem existing in the security proof proposed by Fehr et al., we present the following two schemes:We proposed a refined version of the FHKW scheme. Our refined scheme is limited to encryption of a single bit, but it does not employ any crossauthentication code, which is indispensable for the original FHKW scheme,and can be proved to be NC-CCA2 secure. According to Fehr et al.’s conclusion, it is also SIM-SO-CCA2 secure.We introduce the notion of strong cross-authentication code, and utilize it to construct the FHKW scheme, obtaining a new version of the FHKW scheme. Our new scheme can be used to encrypt multi-bit messages and,more importantly, can be proved to be NC-CCA2 secure. Hence, it is also SIM-SO-CCA2 secure.2. We propose a new primitive called n-evasive all-but-many lossy trapdoor functions(n-evasive ABM-LTFs), provide two constructions of this function, and employ it to construct an IND-SO-CCA2 secure PKE scheme. Specifically, the notion of n-evasive ABM-LTFs is a special version of that of all-but-many lossy trapdoor functions(ABM-LTFs), and is also an extended abstraction of that of all-but-n lossy trapdoor functions(ABN-LTFs). With respect to the constructions of n-evasive ABM-LTFs, we show two approaches: the first one is based on Paillier’s cryptosystem, and its security is under the decisional composite residuosity(DCR) assumption; the second one is based on a collection of ABNLTFs and a collection of chameleon hash functions, and its security is under the securities of the two building blocks. With n-evasive ABM-LTFs, lossy trapdoor functions and hash functions as building blocks, we propose a generic IND-SOCCA2 secure PKE construction.3. We propose the formal definitions of non-malleability under selective opening attacks(NM-SO security), and explore the relations among these notions and the common standard security notions in depth. More specifically, we formalize NM-SO security in two approaches: the simulation-based approach(denoted by SIM-NM-SO security) and the indistinguishability-based approach(denoted by IND-NM-SO security). We explore the relations between NM-SO security notions and the known selective opening security notions, the relations between NM-SO security notions and the standard non-malleability notions, and the relations between SIM-NM-SO security notions and IND-NM-SO security notions.Based on the relations that we obtain, we point out that the FHKW scheme that we fixed is SIM-NM-SO-CCA2 secure, and that any IND-SO-CCA2 secure PKE scheme is IND-NM-SO-CCA2 secure.