Paper 2010/648

Uniqueness is a Different Story: Impossibility of Verifiable Random Functions from Trapdoor Permutations

Dario Fiore and Dominique Schröder


Verifiable random functions (VRFs), firstly proposed by Micali, Rabin, and Vadhan (FOCS 99), are pseudorandom functions with the additional property that the owner of the seed $\vsk$ can issue publicly-verifiable proofs for the statements ``$f({\vsk},x)=y$'', for any input $x$. Moreover, the output of VRFs is guaranteed to be unique, which means that $y=f({\vsk},x)$ is the only image that can be proven to map to $x$. Due to their properties, VRFs are a fascinating primitive that have found several theoretical and practical applications. However, despite their popularity, constructing VRFs seems to be a challenging task. Indeed only a few constructions based on specific number-theoretic problems are known and basing a scheme on a general assumption is still an open problem. Towards this direction, Brakerski, Goldwasser, Rothblum, and Vaikuntanathan (TCC 2009) recently showed that verifiable random functions cannot be constructed from one-way permutations in a black-box way. In this paper we put forward the study of the relationship between VRFs and well-established cryptographic primitives. As our main result, we prove that VRFs cannot be based on the existence of trapdoor permutations (TDPs) in a black-box manner. Our result sheds light on the nature of VRFs and can be considered interesting for at least two reasons: - First, given the separation result of Brakerski \emph{et al.}, one may think as though VRFs would naturally belong to the ``public-key world'', and thus it is interesting to figure out their relationship with other public-key primitives. In this sense, our result shows that VRFs are much stronger because we imply separations of VRFs from most of the primitives in this world: basically everything that is implied by TDPs is strictly weaker. These primitives include e.g., public-key encryption (even CCA secure), oblivious transfer, and key-agreement. - Second, the notion of VRFs is closely related to other two primitives: weak verifiable random functions (weak-VRFs) and verifiable pseudorandom generators (VPRGs). Weak-VRFs, defined by Brakerski \emph{et al.}, are a relaxation of VRFs in which the pseudorandomness holds only with respect to random inputs. VPRGs, introduced by Dwork and Naor (FOCS 2000), are pseudorandom generators that allow the owner of the seed to prove the correctness of subsets of the generated bits. It is well known that ``regular'' PRFs can be constructed from pseudorandom generators and from weak-PRFs in a black-box way. It was thus an open problem (already recognized by Dwork and Naor in their paper) whether similar approaches could be applicable to the ``verifiable'' analogous of such primitives. Since weak-VRFs and VPRGs are implied by TDPs, we give a negative answer to this problem showing that the case of verifiable random functions is essentially different.

Available format(s)
Publication info
Published elsewhere. Unknown where it was published
verifiable random functionstrapdoor permutationsblack-box separations
Contact author(s)
dario fiore @ ens fr
2011-09-15: last of 5 revisions
2010-12-21: received
See all versions
Short URL
Creative Commons Attribution


      author = {Dario Fiore and Dominique Schröder},
      title = {Uniqueness is a Different Story: Impossibility of Verifiable Random Functions from Trapdoor Permutations},
      howpublished = {Cryptology ePrint Archive, Paper 2010/648},
      year = {2010},
      note = {\url{}},
      url = {}
Note: In order to protect the privacy of readers, does not use cookies or embedded third party content.