We show how to construct chosen-plaintext secure (CPA) and chosen-ciphertext secure (CCA) public-key encryption scheme (PKE) from (adaptive) PEPRFs. The construction is simple, black-box, and admits a direct proof of security. We provide evidence that (adaptive) PEPRFs exist by showing the constructions from both hash proof system and extractable hash proof system.
We introduce the notion of publicly samplable PRFs (PSPRFs), which is a relaxation of PEPRFs, but nonetheless imply PKE. We show (adaptive) PSPRFs are implied by (adaptive) trapdoor relations, yet the latter are further implied by (adaptive) trapdoor functions. This helps us to unify and clarify many PKE schemes from different paradigms and general assumptions under the notion of PSPRFs. We also view adaptive PSPRFs as a candidate of the weakest general assumption for CCA-secure PKE.
We explore similar extension on recently emerging predicate PRFs, and introduce the notion of publicly evaluable predicate PRFs, which, as an immediate application, implies predicate encryption.
We propose a variant of PEPRFs, which we call publicly evaluable and verifiable functions (PEVFs). Compared to PEPRFs, PEVFs have an additional promising property named public verifiability while the best possible security degrades to being hard to compute on average. We justify the applicability of PEVFs by presenting a simple construction of ``hash-and-sign'' signatures, both in the random oracle model and the standard model.Category / Keywords: public-key cryptography/PRFs, publicly evaluable, HPS, EHPS, TDF Original Publication (with major differences): SCN 2014 Date: received 30 Apr 2014, last revised 1 Jul 2014 Contact author: yuchen prc at gmail com Available format(s): PDF | BibTeX Citation Note: An extended abstract of this paper appeared in SCN 2014. This is the full version. Version: 20140701:093029 (All versions of this report) Discussion forum: Show discussion | Start new discussion