Publicly Evaluable Pseudorandom Functions and Their Applications

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

 ∈ 

L

, in addition to evaluate

F

sk

(

x

) using

sk

as in the standard PRFs, one is also able to evaluate

F

sk

(

x

) with

pk

,

x

and a witness

w

for

x

 ∈ 

L

. We conduct a formal study of PEPRFs, focusing on applications, constructions, and extensions. In more details:

We show how to construct public-key encryption scheme (PKE) from PEPRFs. The construction is simple, black-box, and admits a direct proof of security. We provide evidence that PEPRFs exist by showing generic constructions from both hash proof systems and extractable hash proof systems.

We introduce the notion of publicly samplable PRFs (PSPRFs), which is a relaxation of PEPRFs, but nonetheless implies PKE. We show PSPRFs are implied by trapdoor relations, yet the latter are further implied by trapdoor functions. This helps us to unify and clarify many PKE schemes from different paradigms and general assumptions under the notion of PSPRFs.

We propose two variants of PEPRFs. One is publicly evaluable predicate PRFs, which admit a direct construction of predicate encryption. The other is publicly evaluable and verifiable functions (PEVFs), which admit a simple construction of “hash-and-sign” signatures.