You are looking at a specific version 20141201:080332 of this paper. See the latest version.

Paper 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.

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.

Metadata
Available format(s)
PDF
Publication info
Published elsewhere. Major revision. SCN 2014
Keywords
publicly evaluablePRFHPSEHPSTDF
Contact author(s)
yuchen prc @ gmail com
History
2016-02-27: last of 3 revisions
2014-04-30: received
See all versions
Short URL
https://ia.cr/2014/306
License
Creative Commons Attribution
CC BY
Note: In order to protect the privacy of readers, eprint.iacr.org does not use cookies or embedded third party content.