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