Welcome to the resource topic for 2014/306
Title:
Publicly Evaluable Pseudorandom Functions and Their Applications
Authors: Yu Chen, Zongyang Zhang
Abstract:We put forth the notion of \emph{publicly evaluable} pseudorandom functions (PEPRFs), which can be viewed as a counterpart of standard pseudorandom functions (PRFs) in the public-key setting. Briefly, PEPRFs are defined over domain X containing a language L associated with a hard relation \mathsf{R}_L, 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 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 a PEPRF cannot be distinguished from a real random function on uniformly random chosen inputs. The strengthened one is adaptive weak pseudorandomness which requires a PEPRF remains weak pseudorandom even when an 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 (PKE) schemes 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 constructions from injective trapdoor functions, hash proof systems, extractable hash proof systems, as well as a construction from puncturable PRFs with program obfuscation. We introduce the notion of publicly sampleable PRFs (PSPRFs), which is a relaxation of PEPRFs, but nonetheless imply PKE. We show (adaptive) PSPRFs are implied by (adaptive) trapdoor relations. This helps us to unify and clarify many PKE schemes from seemingly unrelated general assumptions and paradigms under the notion of PSPRFs. We explore similar extension on recently emerging constrained PRFs, and introduce the notion of publicly evaluable constrained PRFs, which, as an immediate application, implies attribute-based encryption. We propose a twist on 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 unpredictability. 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.
ePrint: https://eprint.iacr.org/2014/306
See all topics related to this paper.
Feel free to post resources that are related to this paper below.
Example resources include: implementations, explanation materials, talks, slides, links to previous discussions on other websites.
For more information, see the rules for Resource Topics .