Paper 2017/021
A Generic Approach to Constructing and Proving Verifiable Random Functions
Rishab Goyal, Susan Hohenberger, Venkata Koppula, and Brent Waters
Abstract
Verifiable Random Functions (VRFs) as introduced by Micali, Rabin and
Vadhan are a special form of Pseudo Random Functions (PRFs) wherein a
secret key holder can also prove validity of the function evaluation
relative to a statistically binding commitment.
Prior works have approached the problem of constructing VRFs by
proposing a candidate under specific number theoretic setting ---
mostly in bilinear groups --- and then grapple with the challenges of
proving security in the VRF environments. These constructions achieved
different results and tradeoffs in practical efficiency, tightness of
reductions and cryptographic assumptions.
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
Note: Added an RSA based as well as phi-hiding based constrained UF/ PRF schemes. Addressed concurrent works.
Metadata
- Available format(s)
-
PDF
- Publication info
- Published by the IACR in TCC 2017
- Keywords
- Verifiable Random Functions
- Contact author(s)
- goyal @ utexas edu
- History
- 2017-10-08: last of 5 revisions
- 2017-01-11: received
- See all versions
- Short URL
- https://ia.cr/2017/021
- License
-
CC BY
BibTeX
@misc{cryptoeprint:2017/021, author = {Rishab Goyal and Susan Hohenberger and Venkata Koppula and Brent Waters}, title = {A Generic Approach to Constructing and Proving Verifiable Random Functions}, howpublished = {Cryptology {ePrint} Archive, Paper 2017/021}, year = {2017}, url = {https://eprint.iacr.org/2017/021} }