Constrained Verifiable Random Functions

Georg Fuchsbauer

Abstract

We extend the notion of verifiable random functions (VRF) to constrained VRFs, which generalize the concept of constrained pseudorandom functions, put forward by Boneh and Waters (Asiacrypt'13), and independently by Kiayias et al. (CCS'13) and Boyle et al. (PKC'14), who call them delegatable PRFs and functional PRFs, respectively. In a standard VRF the secret key $\sk$ allows one to evaluate a pseudorandom function at any point of its domain; in addition, it enables computation of a non-interactive proof that the function value was computed correctly. In a constrained VRF from the key $\sk$ one can derive constrained keys $\sk_S$ for subsets $S$ of the domain, which allow computation of function values and proofs only at points in $S$. After formally defining constrained VRFs, we derive instantiations from the multilinear-maps-based constrained PRFs by Boneh and Waters, yielding a VRF with constrained keys for any set that can be decided by a polynomial-size circuit. Our VRFs have the same function values as the Boneh-Waters PRFs and are proved secure under the same hardness assumption, showing that verifiability comes at no cost. Constrained (functional) VRFs were stated as an open problem by Boyle et al.

Available format(s)
Category
Public-key cryptography
Publication info
Published elsewhere. MAJOR revision.SCN 2014, Springer LNCS 8642
Keywords
Verifiable random functionsconstrained pseudorandom functions
Contact author(s)
georg fuchsbauer @ ist ac at
History
Short URL
https://ia.cr/2014/537

CC BY

BibTeX

@misc{cryptoeprint:2014/537,
author = {Georg Fuchsbauer},
title = {Constrained Verifiable Random Functions},
howpublished = {Cryptology ePrint Archive, Paper 2014/537},
year = {2014},
note = {\url{https://eprint.iacr.org/2014/537}},
url = {https://eprint.iacr.org/2014/537}
}

Note: In order to protect the privacy of readers, eprint.iacr.org does not use cookies or embedded third party content.