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 constrained PRFs, and introduce the notion of publicly evaluable constrained 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 show how to construct PEVFs from EHPS for publicly verifiable relation. Moreover, 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: publicly evaluable, PRF, HPS, EHPS, TDF Original Publication (with major differences): SCN 2014 Date: received 30 Apr 2014, last revised 1 Dec 2014 Contact author: yuchen prc at gmail com Available format(s): PDF | BibTeX Citation Note: In this version, we show how to construct adaptively weak-pseudorandom PEPRFs from universal_1 HPS. We also show how to construct PEVFs from EHPS for efficiently verifiable relations. Version: 20141201:080332 (All versions of this report) Discussion forum: Show discussion | Start new discussion