In cryptography, the concept of a verifiable random function was introduced by Micali, Rabin, and Vadhan. It is a pseudo-random function that provides publicly verifiable proofs of its outputs' correctness. Given an input value x, the owner of the secret key SK can compute the function value y = FSK(x) and the proof pSK(x). Using the proof and the public key
The original construction was rather inefficient. Later, an efficient and practical verifiable random function was proposed by Yevgeniy Dodis and Aleksandr Yampolskiy. In their construction,
where e(·,·) is a bilinear map. To verify whether
The proof of security relies on a new decisional bilinear Diffie-Hellman inversion assumption, which asks given