Verifiable random function

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 = F_SK(x) and the proof p_SK(x). Using the proof and the public key $PK=g^{SK}$, everyone can check that the value y = F_SK(x) was indeed computed correctly, yet this information cannot be used to find the secret key.

The original construction was rather inefficient. Recently, an efficient and practical verifiable random function was proposed by Yevgeniy Dodis and Aleksandr Yampolskiy. In their construction,

$F_{SK}(x)=e(g,g)^{1/(x+SK)}\quad {\mbox{and}}\quad p_{SK}(x)=g^{1/(x+SK)},$

where e(·,·) is a bilinear map. To verify whether $F_{SK}(x)$ was computed correctly or not, one can check if $e(g^{x}PK,p_{SK}(x))=e(g,g)$.

The proof of security relies on a new decisional bilinear Diffie-Hellman inversion assumption, which asks given $(g,g^{x},\ldots ,g^{(x^{q})},R)$ as input to distinguish $R=e(g,g)^{1/x}$ from random.