Verifiable random function

In cryptography, a verifiable random function (VRF) is a public-key pseudorandom function that provides proofs that its outputs were calculated correctly. The owner of the secret key can compute the function value as well as an associated proof for any input value. Everyone else, using the proof and the associated public key (or verification key ), can check that this value was indeed calculated correctly, yet this information cannot be used to find the secret key. A verifiable random function can be viewed as a public-key analogue of a keyed cryptographic hash and as a cryptographic commitment to an exponentially large number of seemingly random bits. The concept of a verifiable random function is closely related to that of a verifiable unpredictable function (VUF), whose outputs are hard to predict but do not necessarily seem random. The concept of a VRF was introduced by Micali, Rabin, and Vadhan in 1999. Since then, verifiable random functions have found widespread use in cryptocurrencies, as well as in proposals for protocol design and cybersecurity.

In cryptography, a verifiable random function (VRF) is a public-key pseudorandom function that provides proofs that its outputs were calculated correctly. The owner of the secret key can compute the function value as well as an associated proof for any input value. Everyone else, using the proof and the associated public key (or verification key ), can check that this value was indeed calculated correctly, yet this information cannot be used to find the secret key. A verifiable random function can be viewed as a public-key analogue of a keyed cryptographic hash and as a cryptographic commitment to an exponentially large number of seemingly random bits. The concept of a verifiable random function is closely related to that of a verifiable unpredictable function (VUF), whose outputs are hard to predict but do not necessarily seem random. The concept of a VRF was introduced by Micali, Rabin, and Vadhan in 1999. Since then, verifiable random functions have found widespread use in cryptocurrencies, as well as in proposals for protocol design and cybersecurity. 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) and e(g, p_{SK}(x))=F_{SK}(x) . To extend this to a larger domain, the authors use a tree construction and a universal hash function. This is secure if it is hard to break the "q-Diffie–Hellman inversion assumption", which states that no algorithm given (g, g^x, \dots, g^{x^q}) can compute g^{1/x} , and the "q-decisional bilinear Diffie–Hellman inversion assumption", which states that it is impossible for an efficient algorithm given (g, g^{x}, \ldots, g^{(x^q)}, R) as input to distinguish R=e(g,g)^{1/x} from random, in the group \mathbb{G} . In 2015, Hofheinz and Jager constructed a VRF which is provably secure given any member of the "(n − 1)-linear assumption family", which includes the decision linear assumption. This is the first such VRF constructed that does not depend on a "Q-type complexity assumption". In 2019, Bitansky showed that VRFs exist if non-interactive witness-indistinguishable proofs (that is, weaker versions of non-interactive zero-knowledge proofs for NP problems that only hide the witness that the prover uses ), non-interactive cryptographic commitments, and single-key constrained pseudorandom functions (that is, pseudorandom functions that only allow the user to evaluate the function with a preset constrained subset of possible inputs ) also do. When an Oblivious Pseudorandom Function is based on asymmetric cryptography, possession of the public key can allow the client to verify the output of the function, by checking a digital signature or a zero-knowledge proof. In 2020, Esgin et al. proposed a post-quantum secure VRF based on lattice-based cryptography. ==Uses and applications== VRFs provide deterministic pre-commitments for low entropy inputs which must be resistant to brute-force pre-image attacks. VRFs can be used for defense against offline enumeration attacks (such as dictionary attacks) on data stored in hash-based data structures. ==References==

Text derived from https://en.wikipedia.org/w/index.php?oldid=1366452107 under CC BY-SA 4.0; modifications have been made.