On Several Verifiable Random Functions and the q-decisional Bilinear Diffie-Hellman Inversion Assumption

Sebastian Lauer

The 5th ACM ASIA Public-Key Cryptography Workshop (APKC 2018)


In 1999, Micali, Rabin and Vadhan introduced the notion of Verifiable Random Functions (VRF)[26].VRFs compute for a given input x and a secret key sk a unique function value y = Vsk (x), and additionally a publicly verifiable proof π. Each owner of the corresponding public key pk can use the proof to non-interactivly verify that the function value was computed correctly. Furthermore, the function value provides the property of pseudorandomness. Most constructions in the past are based on q-type assumptions. Since these assumptions get stronger for a large factor q, it is desirable to show the existence of VRFs under static or general assumptions. In this work we will show for the constructions presented in [14][6] the equivalence of breaking the VRF and solving the underlying q-type assumption.