Cryptology ePrint Archive: Report 2014/306

Publicly Evaluable Pseudorandom Functions and Their Applications

Yu Chen and Zongyang Zhang

Abstract: We put forth the notion of publicly evaluable pseudorandom functions (PEPRFs), which is a non-trivial extension of the standard pseudorandom functions (PRFs). Briefly, PEPRFs are defined over domain $X$ containing an NP language $L$ in which the witness is hard to extract on average, and each secret key $sk$ is associated with a public key $pk$. For any $x \in L$, in addition to evaluate $\mathsf{F}_{sk}(x)$ using $sk$ as in the standard PRFs, one is also able to evaluate $\mathsf{F}_{sk}(x)$ with $pk$, $x$ and a witness $w$ for $x \in L$. We consider two security notions for PEPRFs. The basic one is weak-pseudorandomness which stipulates PEPRF cannot be distinguished from a uniform random function at randomly chosen inputs. The strengthened one is adaptively weak-pseudorandomness which requires PEPRF remains weak-pseudorandom even when the adversary is given adaptive access to an evaluation oracle. We conduct a formal study of PEPRFs, focusing on applications, constructions, and extensions.

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)

Short URL: ia.cr/2014/306

Discussion forum: Show discussion | Start new discussion