International Association
for Cryptologic Research

We introduce and study a new notion of enhanced chosen-ciphertext security (ECCA) for public- key encryption. Loosely speaking, in ECCA, when the decryption oracle returns a plaintext to the adversary, it also provides coins under which the returned plaintext encrypts to the queried ciphertext (when they exist). Our results mainly concern the case where such coins can also be recovered efficiently. We provide constructions of ECCA encryption from adaptive trapdoor functions as defined by Kiltz et al. (EUROCRYPT 2010), resulting in ECCA encryption from standard number-theoretic assumptions. We then give two applications of ECCA encryption: (1) We use it as a unifying concept in showing equivalence of adaptive trapdoor functions and tag-based adaptive trapdoor functions (namely, we show that both primitives are equivalent to ECCA encryption), resolving a main open question of Kiltz et al. (2) We show that ECCA encryption can be used to securely realize an approach to public-key encryption with non-interactive opening (PKENO) suggested by Damg{\\aa}rd and Thorbek (EUROCRYPT 2007), resulting in new and practical PKENO schemes quite different from those in prior work. We believe our results indicate that ECCA is an intriguing notion that may prove useful in further work.