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.
Constructions In 1999, Micali, Rabin, and Vadhan introduced the concept of a VRF and proposed the first such one. The original construction was rather inefficient: it first produces a verifiable unpredictable function, then uses a hard-core bit to transform it into a VRF; moreover, the inputs have to be mapped to primes in a complicated manner: namely, by using a prime sequence generator that generates primes with overwhelming probability using a probabilistic primality test. The verifiable unpredictable function thus proposed, which is provably secure if a variant of the RSA problem is hard, is defined as follows: The public key PK is ( m , r , Q , c o i n s ) {\displaystyle (m,r,Q,coins)} , where m is the product of two random primes, r is a number randomly selected from Z m ∗ {\displaystyle \mathbb {Z} _{m}^{*}} , coins is a randomly selected set of bits, and Q a function selected randomly from all polynomials of degree 2 k 2 − 1 {\displaystyle 2k^{2}-1} over the field G F ( 2 k ) {\displaystyle GF(2^{k})} . The secret key is ( P K , ϕ ( m ) ) {\displaystyle (PK,\phi (m))} . Given an input x and a secret key SK, the VUF uses the prime sequence generator to pick a corresponding prime p x {\displaystyle p_{x}} (the generator requires auxiliary inputs Q and coins), and then computes and outputs r 1 / p x ( mod m ) {\displaystyle r^{1/p_{x}}{\pmod {m}}} , which is easily done by knowledge of ϕ ( m ) {\displaystyle \phi (m)} . In 2005, an efficient and practical verifiable random function was proposed by Dodis and Yampolskiy. When the input x {\displaystyle x} is from a small domain (the authors then extend it to a larger domain), the function can be defined as follows:
F S K ( x ) = e ( g , g ) 1 / ( x + S K ) and p S K ( x ) = g 1 / ( x + S K ) , {\displaystyle F_{SK}(x)=e(g,g)^{1/(x+SK)}\quad {\mbox{and}}\quad p_{SK}(x)=g^{1/(x+SK)},}
… excerpt ends here. Continue reading the full article.
