Indistinguishability against Chosen Ciphertext Verification Attack Revisited: The Complete Picture

摘要

The knowledge that whether a purported ciphertext is valid or not may leak sufficient information to mount practical attacks on public key cryptosystem, e.g., Bleichenbacher's attack on RSA-PKCS#1, Hall-Goldberg-Schneier's "reaction attack" on both McEliece and Ajtai-Dwork cryptosystems. A notion called indistinguishability against chosen ciphertext verification attack (IND-CCVA) has been introduced in the literature, where the adversary has access to a chosen ciphertext verification oracle (not the full decryption oracle), to address those cryptographic functionalities where IND-CPA security is not sufficient and IND-CCA security is more than necessary. Some of the implications and separations between CPA, CCA and CCVA notions are known, while the rest are still open. In this paper we provide non-trivial constructions of schemes (existing/ new) to resolve all the open issues, thus providing a complete picture. We also introduce a slightly stronger attack, called Adaptive Chosen Ciphertext Decryption/Verification Attack (CCA 1.5), where the adversary gets an access to a decryption oracle in the first query phase and a ciphertext verification oracle in the second query phase. We argue that this attack is more realistic than usual CCA2 attack. In fact, it lies between CCA1 and CCA2 security as well as between CCVA2 and CCA2 security. In this regard, inter-relationships between the proposed CCA 1.5 notion with existing notions are established. Moreover, it is shown that any group homomorphic cryptosystem is CCA 1.5 under some reasonable assumption, thereby providing another motivation for studying this particular type of attack scenario.