Verifiable random function

From Wikipedia, the free encyclopedia

Some information in this article or section is not attributed to sources and may not be reliable.
Please check for inaccuracies, and modify and cite sources as needed.

In cryptography, the concept of a verifiable random function was introduced by Micali, Rabin, and Vadhan.[1] 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, everyone can check that the value y = FSK(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 FSK(x) was computed correctly or not, one can check if e(gxPK,pSK(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.

[edit] References

  1. ^ Micali, Silvio; Rabin, Michael O.; Vadhan, Salil P. (1999). "Verifiable random functions". Proceedings of the 40th IEEE Symposium on Foundations of Computer Science: 120–130. 
 This cryptography-related article is a stub. You can help Wikipedia by expanding it.
Retrieved from "http://en.wikipedia.org../../../v/e/r/Verifiable_random_function.html"