We introduce the notion of adaptive trapdoor functions (ATDFs); roughly, ATDFs remain one-way even when the adversary is given access to an inversion oracle. Our main application is the black-box construction of chosen-ciphertext secure public-key encryption (CCA-secure PKE). Namely, we give a black-box construction of CCA-Secure PKE from ATDFs, as well as a construction of ATDFs from correlation-secure TDFs introduced by Rosen and Segev (TCC ’09). Moreover, by an extension of a recent result of Vahlis (TCC ’10), we show that ATDFs are strictly weaker than the latter (in a black-box sense). Thus, adaptivity appears to be the weakest condition on a TDF currently known to yield the first implication.#R##N##R##N#We also give a black-box construction of CCA-secure PKE from a natural extension of ATDFs we call tag-based ATDFs that, when applied to our constructions of the latter from either correlation-secure TDFs, or lossy TDFs introduced by Peikert and Waters (STOC ’08), yield precisely the CCA-secure PKE schemes in these works. This helps to unify and clarify their schemes. Finally, we show how to realize tag-based ATDFs from an assumption on RSA inversion not known to yield correlation-secure TDFs.
['Eike Kiltz', 'Payman Mohassel', 'Adam O’Neill']
Adaptive trapdoor functions and chosen-ciphertext security