Verifiable Random Functions from Non-interactive Witness-Indistinguishable Proofs
Verifiable random functions (VRFs) are pseudorandom functions where the owner of the seed, in addition to computing the function’s value y at any point x, can also generate a non-interactive proof \(\pi \) that y is correct, without compromising pseudoran
- PDF / 428,487 Bytes
- 28 Pages / 439.37 x 666.142 pts Page_size
- 18 Downloads / 183 Views
Abstract. Verifiable random functions (VRFs) are pseudorandom functions where the owner of the seed, in addition to computing the function’s value y at any point x, can also generate a non-interactive proof π that y is correct, without compromising pseudorandomness at other points. Being a natural primitive with a wide range of applications, considerable efforts have been directed towards the construction of such VRFs. While these efforts have resulted in a variety of algebraic constructions (from bilinear maps or the RSA problem), the relation between VRFs and other general primitives is still not well understood. We present new constructions of VRFs from general primitives, the main one being non-interactive witness-indistinguishable proofs (NIWIs). This includes: – A selectively-secure VRF assuming NIWIs and non-interactive commitments. As usual, the VRF can be made adaptively-secure assuming subexponential hardness of the underlying primitives. – An adaptively-secure VRF assuming (polynomially-hard) NIWIs, noninteractive commitments, and (single-key) constrained pseudorandom functions for a restricted class of constraints. The above primitives can be instantiated under various standard assumptions, which yields corresponding VRF instantiations, under different assumptions than were known so far. One notable example is a nonuniform construction of VRFs from subexponentially-hard trapdoor permutations, or more generally, from verifiable pseudorandom generators (the construction can be made uniform under a standard derandomization assumption). This partially answers an open question by Dwork and Naor (FOCS ’00). The construction and its analysis are quite simple. Both draw from ideas commonly used in the context of indistinguishability obfuscation.
1
Introduction
Verifiable random functions (VRFs), introduced by Micali et al. [39], are pseudorandom functions (PRFs) [27] where it is possible to verify that a given output y corresponds to a correct evaluation of the function on any given input x. Such a VRF is associated with a secret key SK and a corresponding public c International Association for Cryptologic Research 2017 Y. Kalai and L. Reyzin (Eds.): TCC 2017, Part II, LNCS 10678, pp. 567–594, 2017. https://doi.org/10.1007/978-3-319-70503-3_19
568
N. Bitansky
verification key V K. The secret key allows anyone to compute the function y = VRF.EvalSK (x) at any point x, and also to compute a proof πx,y that y was computed correctly. Here, by “computed correctly”, we mean that any verification key V K ∗ , even a maliciously chosen one, is a commitment to the entire function—it uniquely determines the value y of the function at any point x, and accepting proofs only exist for this value y. The pseudorandomness requirement generalizes that of plain PRFs—the value y of the function at any point x should be pseudorandom, even after evaluating the function and obtaining proofs of correctness for an arbitrary polynomial number of points {xi = x}. The standard definition is adaptive, allowing the point x to be chosen a
Data Loading...
