Paper 2017/018

Verifiable Random Functions from Non-Interactive Witness-Indistinguishable Proofs

Nir Bitansky

Abstract

{\em 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 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 {\em non-interactive witness-indistinguishable proofs} (NIWIs). This includes: \begin{itemize} \item 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. \item An adaptively-secure VRF assuming (polynomially-hard) NIWIs, non-interactive commitments, and {\em (single-key) constrained pseudorandom functions} for a restricted class of constraints. \end{itemize} 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 {\em 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 {\em indistinguishability obfuscation}.

Note: Added CPRF construction from DDH and fixed some typos.

Metadata
Available format(s)
PDF
Category
Foundations
Publication info
A minor revision of an IACR publication in TCC 2017
Keywords
verifiable-random-functions
Contact author(s)
nirbitan @ csail mit edu
History
2017-09-14: last of 4 revisions
2017-01-11: received
See all versions
Short URL
https://ia.cr/2017/018
License
Creative Commons Attribution
CC BY

BibTeX

@misc{cryptoeprint:2017/018,
      author = {Nir Bitansky},
      title = {Verifiable Random Functions from Non-Interactive Witness-Indistinguishable Proofs},
      howpublished = {Cryptology ePrint Archive, Paper 2017/018},
      year = {2017},
      note = {\url{https://eprint.iacr.org/2017/018}},
      url = {https://eprint.iacr.org/2017/018}
}
Note: In order to protect the privacy of readers, eprint.iacr.org does not use cookies or embedded third party content.