Verifiable random function

The concept of a verifiable random function was introduced by Micali, Rabin, and Vadhan. It is a pseudo-random function that provides publically verifiable proofs of its outputs' correctness. Given an input value x, the owner of the secret key SK can compute the function value y=F_{SK}(x) and the proof p_{SK}(x). This proof convinces everyone that the value y=F_{SK}(x) was indeed computed correctly. The original construction was rather inefficient. Recently, an efficient and practical VRF was proposed by Dodis and Yampolskiy. In their construction,

F_{SK}(x) = e(g,g)^{1/(x+SK)} and p_{SK}(x) = g^{1/(x+SK}), where e(.,.) is a bilinear map.