A Generic Approach to Constructing and Proving Verifiable Random Functions
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
- PDF / 440,768 Bytes
- 30 Pages / 439.37 x 666.142 pts Page_size
- 4 Downloads / 214 Views
University of Texas at Austin, Austin, USA {rgoyal,kvenkata,bwaters}@cs.utexas.edu 2 Johns Hopkins University, Baltimore, USA [email protected]
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 a specific number theoretic setting — mostly in bilinear groups — and then grappling 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) 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 two new constructions of 1-bounded constrained PRFs for admissible hash friendly constructions. Our first construction is from the n-powerDDH assumption. The next is from the φ hiding assumption.
1
Introduction
Verifiable Random Functions (VRFs) as introduced by Micali et al. [30] are a special form of Pseudo Random Functions (PRFs) [20] wherein a secret key holder can also prove validity of the function evaluation relative to a statistically c International Association for Cryptologic Research 2017 Y. Kalai and L. Reyzin (Eds.): TCC 2017, Part II, LNCS 10678, pp. 537–566, 2017. https://doi.org/10.1007/978-3-319-70503-3_18
538
R. Goyal et al.
binding commitment. The caveat being that the pseudorandomness of the function on other points should not be sacrificed even after providing polynomially many proofs. The VRF definition forbids interactivity or any setup assumption, thereby disallowing trivial extensions of PRFs making the problem more challenging and interesting. Prior works [13,14,22,24,25,29] have approached the problem of constructing VRFs by proposing a candidate under a specific number theoretic setting — mostly in b
Data Loading...
