Verifiable random function

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, coins), where m is the product of two random primes, r is a number randomly selected from \mathbb{Z}_m^*, coins is a randomly selected set of bits, and Q a function selected randomly from all polynomials of degree 2k^2 - 1 over the field GF(2^k). The secret key is (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 (the generator requires auxiliary inputs Q and coins), and then computes and outputs r^{1/p_x} \pmod{m}, which is easily done by knowledge of \phi(m).

In 2005, an efficient and practical verifiable random function was proposed by Dodis and Yampolskiy. When the input x is from a small domain (the authors then extend it to a larger domain), the function can be defined as follows: : 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.

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.

References

References

1. Goldberg, Sharon. (5 March 2018). "Verifiable Random Functions (VRFs)".
2. (1999). "Verifiable random functions".
3. Potter, John. (9 September 2021). "How Can Value Investors Profit in the Crypto Ecosystem?".
4. (16 November 2004). "A Verifiable Random Function With Short Proofs and Keys". Springer, Berlin, Heidelberg.
5. Nountu, Thierry Mefenza. (28 November 2017). "Pseudo-Random Generators and Pseudo-Random Functions: Cryptanalysis and Complexity Measures".
6. (30 October 2015). "Verifiable Random Functions from Standard Assumptions".
7. (2007-01-01). "Derandomization in Cryptography". SIAM Journal on Computing.
8. (2013). "Advances in Cryptology - ASIACRYPT 2013". Springer.
9. Bitansky, Nir. (2020-04-01). "Verifiable Random Functions from Non-interactive Witness-Indistinguishable Proofs". Journal of Cryptology.
10. (24 March 2021). "Practical Post-Quantum Few-Time Verifiable Random Function with Applications to Algorand". Cryptology ePrint Archive.
11. Schorn, Eric. (2020-02-24). "Reviewing Verifiable Random Functions".
12. (2001). "Advances in Cryptology — CRYPTO 2001". Springer.
13. Dodis, Yevgeniy. (2002). "Public Key Cryptography — PKC 2003". Springer.
14. Goldberg, Sharon. "NSEC5: Provably Preventing DNSSEC Zone Enumeration".