Paper 2014/799

Verifiable Random Functions from Weaker Assumptions

Tibor Jager


The construction of a verifiable random function (VRF) with large input space and full adaptive security from a static, non-interactive complexity assumption, like decisional Diffie-Hellman, has proven to be a challenging task. To date it is not even clear that such a VRF exists. Most known constructions either allow only a small input space of polynomially-bounded size, or do not achieve full adaptive security under a static, non-interactive complexity assumption. The only known constructions without these restrictions are based on non-static, so-called "q-type" assumptions, which are parametrized by an integer q. Since q-type assumptions get stronger with larger q, it is desirable to have q as small as possible. In current constructions, q is either a polynomial (e.g., Hohenberger and Waters, Eurocrypt 2010) or at least linear (e.g., Boneh et al., CCS 2010) in the security parameter. We show that it is possible to construct relatively simple and efficient verifiable random functions with full adaptive security and large input space from non-interactive q-type assumptions, where q is only logarithmic in the security parameter. Interestingly, our VRF is essentially identical to the verifiable unpredictable function (VUF) by Lysyanskaya (Crypto 2002), but very different from Lysyanskaya’s VRF from the same paper. Thus, our result can also be viewed as a new, direct VRF-security proof for Lysyanskaya’s VUF. As a technical tool, we introduce and construct balanced admissible hash functions.

Available format(s)
Public-key cryptography
Publication info
A minor revision of an IACR publication in TCC 2015
Verifiable random functionsq-type assumptions
Contact author(s)
tibor jager @ rub de
2015-03-16: last of 10 revisions
2014-10-10: received
See all versions
Short URL
Creative Commons Attribution


      author = {Tibor Jager},
      title = {Verifiable Random Functions from Weaker Assumptions},
      howpublished = {Cryptology ePrint Archive, Paper 2014/799},
      year = {2014},
      doi = {10.1007/978-3-662-46497-7_5},
      note = {\url{}},
      url = {}
Note: In order to protect the privacy of readers, does not use cookies or embedded third party content.