Verifiable random function

In cryptography, the concept of a verifiable random function was introduced by Micali, Rabin, and Vadhan. [cite conference | first = Silvio | last = Micali | coauthors = Rabin, Michael O.; Vadhan, Salil P. | title = Verifiable random functions | booktitle = Proceedings of the 40th IEEE Symposium on Foundations of Computer Science | pages = 120–130 | date = 1999 ] 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, 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)\}\; quadmbox\{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 checkif $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.

References