Verifiable random function

In 1999, Micali, Rabin, and Vadhan introduced the concept of a VRF and proposed the first such one.[4] 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.[3][4] 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 ${\displaystyle (m,r,Q,coins)}$, where m is the product of two random primes, r is a number randomly selected from ${\displaystyle \mathbb {Z} _{r}^{*}}$, coins is a randomly selected set of bits, and Q a function selected randomly from all polynomials of degree ${\displaystyle 2k^{2}-1}$ over the field ${\displaystyle GF(2^{k})}$. The secret key is ${\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 ${\displaystyle p_{x}}$ (the generator requires auxiliary inputs Q and coins), and then computes and outputs ${\displaystyle r^{1/p_{x}}{\pmod {m}}}$, which is easily done by knowledge of ${\displaystyle \phi (m)}$.[4]

In 2005, an efficient and practical verifiable random function was proposed by Dodis and Yampolskiy.[3][6] When the input ${\displaystyle x}$ is from a small domain (the authors then extend it to a larger domain), the function can be defined as follows:

${\displaystyle 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 ${\displaystyle F_{SK}(x)}$ was computed correctly or not, one can check if ${\displaystyle e(g^{x}PK,p_{SK}(x))=e(g,g)}$ and ${\displaystyle e(g,p_{SK}(x))=F_{SK}(x)}$.[3][6] To extend this to a larger domain, the authors use a tree construction and a universal hash function.[3] This is secure if it is hard to break the "q-Diffie-Helman inversion assumption", which states that no algorithm given ${\displaystyle (g,g^{x},\dots ,g^{x^{q}})}$ can compute ${\displaystyle g^{1/x}}$, and the "q-decisional bilinear Diffie-Helman inversion assumption", which states that it is impossible for an efficient algorithm given ${\displaystyle (g,g^{x},\ldots ,g^{(x^{q})},R)}$ as input to distinguish ${\displaystyle R=e(g,g)^{1/x}}$ from random, in the group ${\displaystyle \mathbb {G} }$.[3][6]

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.[7] This is the first such VRF constructed that does not depend on a "Q-type complexity assumption".[7]

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[1][8]), 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[9]) also do.[1]

In 2020, Esgin et al. proposed a post-quantum secure VRF based on lattice-based cryptography.[10]

VRFs provide deterministic pre-commitments for low entropy inputs which must be resistant to brute-force pre-image attacks.[11] VRFs can be used for defense against offline enumeration attacks (such as dictionary attacks) on data stored in hash-based data structures.[2]