In this work we take a different approach. Instead of tackling the VRF problem as a whole we demonstrate a simple and generic way of building Verifiable Random Functions from more basic and narrow cryptographic primitives. Then we can turn to exploring solutions to these primitives with a more focused mindset. In particular, we show that VRFs can be constructed generically from the ingredients of: (1) a 1-bounded constrained pseudo random function for a functionality that is ``admissible hash friendly" , (2) a non-interactive statistically binding commitment scheme (without trusted setup) and (3) a non-interactive witness indistinguishable proofs or NIWIs. The first primitive can be replaced with a more basic puncturable PRF constraint if one is willing to settle for selective security or assume sub-exponential hardness of assumptions.
In the second half of our work we support our generic approach by giving new constructions of the underlying primitives. We first provide new constructions of perfectly binding commitments from the Learning with Errors (LWE) and Learning Parity with Noise (LPN) assumptions. Second, we give give two new constructions of 1-bounded constrained PRFs for admissible hash friendly constructions. Our first construction is from the $\nddh$ assumption. The next is from the $\phi$ hiding assumption.Category / Keywords: Verifiable Random Functions Date: received 11 Jan 2017, last revised 1 Feb 2017 Contact author: goyal at utexas edu Available format(s): PDF | BibTeX Citation Note: Added an RSA based as well as phi-hiding based constrained UF/ PRF schemes. Addressed concurrent works. Version: 20170201:231447 (All versions of this report) Short URL: ia.cr/2017/021 Discussion forum: Show discussion | Start new discussion