This paper introduces simulatable verifiable random functions (sVRF). VRFs are similar to pseudorandom functions, except that
they are also verifiable: corresponding to each seed
SK, there is a public key
PK, and for
, it is possible to prove that
y is indeed the value of the function seeded by
SK. A
simulatable VRF is a VRF for which this proof can be simulated, so a simulator can pretend that the value of
is any
y.
Our contributions are as follows. We introduce the notion of sVRF. We give two constructions: one from general assumptions
(based on NIZK), but inefficient, just as a proof of concept; the other construction is practical and based on a special assumption
about composite-order groups with bilinear maps. We then use an sVRF to get a direct transformation from a single-theorem
non-interactive zero-knowledge proof system for a language L to a multi-theorem non-interactive proof system for the same language L.