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 Fsk(x) using sk as in the standard PRFs, one is also able to evaluate Fsk(x) with pk, x and a witness w for x ∈ 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 adap-tively 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 construc-tion is simple, black-box, and admits a direct proof of security. We provide evidenc