where e(·,·) is a bilinear map. To verify whether was computed correctly or not, one can check if and . 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-Helman inversion assumption", which states that no algorithm given can compute , and the "q-decisional bilinear Diffie-Helman inversion assumption", which states that it is impossible for an efficient algorithm given as input to distinguish from random, in the group . 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. 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. In protocol design VRFs have been used to make: Resettable zero-knowledge proofs (i.e. one that remains zero-knowledge even if a malicious verifier is allowed to reset the honest prover and query it again) with three rounds in the bare model Non-interactive lottery systems Verifiable transaction escrow schemes Updatable zero-knowledge databases E-cash VRFs can also be used to implement random oracles. In Internet security DNSSEC is a system that prevents attackers from tampering with Domain Name System messages, but it also suffers from the vulnerability of zone enumeration. The proposed NSEC5 system, which uses VRFs, provably prevents this type of attack. In cryptocurrency Cardano and Polkadot implement VRFs for block production. The Internet Computer cryptocurrency uses a VRF to produce a decentralized random beacon whose output is unpredictable to anyone until they become available to everyone. More precisely, its protocol allows clients to agree on a VRF (i.e. a commitment to a deterministic