**Verifiable Random Functions from Weaker Assumptions**

*Tibor Jager*

**Abstract: **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.

**Category / Keywords: **public-key cryptography / Verifiable random functions, q-type assumptions

**Original Publication**** (with minor differences): **IACR-TCC-2015
**DOI: **10.1007/978-3-662-46497-7_5

**Date: **received 6 Oct 2014, last revised 16 Mar 2015

**Contact author: **tibor jager at rub de

**Available format(s): **PDF | BibTeX Citation

**Version: **20150316:104440 (All versions of this report)

**Short URL: **ia.cr/2014/799

**Discussion forum: **Show discussion | Start new discussion

[ Cryptology ePrint archive ]