Nir Bitansky: Verifiable Random Functions from Non-Interactive Witness-Indistinguishable Proofs
Friday, April 14, 2017 - 10:30am to 12:00pm
Location:
Hewlett G882
Speaker:
Nir Bitansky, MIT
Seminar group:
Abstract: Verifiable random functions (VRFs), introduced by Micali, Rabin, and Vadhan (FOCS 99), are pseudorandom functions where the owner of the seed, in addition to computing the function's value at any point, can also generate a non-interactive proof that the value 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 the RSA problem or bilinear maps), 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 {\em (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 non-uniform construction of VRFs from subexponentially-hard trapdoor permutations, or more generally, from verifiable pseudorandom generators. 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.