verifiable random function

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 $\backslash 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,\; \backslash 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\}\; \backslash pmod\{m\}$, which is easily done by knowledge of $\backslash phi(m)$.

In 2005, an efficient and practical verifiable random function was proposed by Dodis and Yampolskiy.{{cite conference|last1=Dodis|first1=Yevgeniy|last2=Yampolskiy|first2=Aleksandr|author-link2=Aleksandr Yampolskiy|date=16 November 2004|title=A Verifiable Random Function With Short Proofs and Keys|url=https://eprint.iacr.org/2004/310.pdf|conference=International Workshop on Public Key Cryptography|publisher=Springer, Berlin, Heidelberg|publication-date=2005|pages=416–431|isbn=978-3-540-30580-4|access-date=26 August 2021|book-title=8th International Workshop on Theory and Practice in Public Key Cryptography}}{{Cite thesis|last=Nountu|first=Thierry Mefenza|title=Pseudo-Random Generators and Pseudo-Random Functions: Cryptanalysis and Complexity Measures|date=28 November 2017|degree=Thèse de doctorat|url=https://hal.inria.fr/tel-01667124v1/document}} 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)\}\; \backslash quad\backslash mbox\{and\}\backslash 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-Helman inversion assumption", which states that no algorithm given $(g,\; g^x,\; \backslash dots,\; g^\{x^q\})$ can compute $g^\{1/x\}$, and the "q-decisional bilinear Diffie-Helman inversion assumption", which states that it is impossible for an efficient algorithm given $(g,\; g^\{x\},\; \backslash ldots,\; g^\{(x^q)\},\; R)$ as input to distinguish $R=e(g,g)^\{1/x\}$ from random, in the group $\backslash 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.{{Cite conference|last1=Hofheinz|first1=Dennis|last2=Jager|first2=Tibor|date=30 October 2015|title=Verifiable Random Functions from Standard Assumptions|url=http://citeseerx.ist.psu.edu/viewdoc/download?doi=10.1.1.738.9975&rep=rep1&type=pdf|conference=Theory of Cryptography Conference|publication-date=19 December 2015|pages=336–362|doi=10.1007/978-3-662-49096-9_14|citeseerx=10.1.1.738.9975 |isbn=978-3-662-49096-9}} 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{{Cite journal|last1=Barak|first1=Boaz|last2=Ong|first2=Shien Jin|last3=Vadhan|first3=Salil|date=2007-01-01|title=Derandomization in Cryptography|url=https://dash.harvard.edu/bitstream/handle/1/41467486/86374%2010.1.1.91.2701.pdf|journal=SIAM Journal on Computing|volume=37|issue=2|pages=380–400|doi=10.1137/050641958|issn=0097-5397|access-date=2 September 2021}}), 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{{Cite book|last1=Boneh|first1=Dan|last2=Waters|first2=Brent|title=Advances in Cryptology - ASIACRYPT 2013 |chapter=Constrained Pseudorandom Functions and Their Applications |date=2013|editor-last=Sako|editor-first=Kazue|editor2-last=Sarkar|editor2-first=Palash|chapter-url=https://eprint.iacr.org/2013/352|series=Lecture Notes in Computer Science|volume=8270 |language=en|location=Berlin, Heidelberg|publisher=Springer|pages=280–300|doi=10.1007/978-3-642-42045-0_15|isbn=978-3-642-42045-0|access-date=2 September 2021|doi-access=free}}) also do.{{Cite journal|last=Bitansky|first=Nir|date=2020-04-01|title=Verifiable Random Functions from Non-interactive Witness-Indistinguishable Proofs|url=https://doi.org/10.1007/s00145-019-09331-1|journal=Journal of Cryptology|language=en|volume=33|issue=2|pages=459–493|doi=10.1007/s00145-019-09331-1|s2cid=253636177 |issn=1432-1378|url-access=subscription}}

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.{{Cite journal|last1=Esgin|first1=Muhammed F.|last2=Kuchta|first2=Veronika|last3=Sakzad|first3=Amin|last4=Steinfeld|first4=Ron|last5=Zhang|first5=Zhenfei|last6=Sun|first6=Shifeng|last7=Chu|first7=Shumo|date=24 March 2021|title=Practical Post-Quantum Few-Time Verifiable Random Function with Applications to Algorand|url=https://eprint.iacr.org/2020/1222|journal=Cryptology ePrint Archive|access-date=26 August 2021}}

VRFs provide deterministic pre-commitments for low entropy inputs which must be resistant to brute-force pre-image attacks.{{Cite web|last=Schorn|first=Eric|date=2020-02-24|title=Reviewing Verifiable Random Functions|url=https://research.nccgroup.com/2020/02/24/reviewing-verifiable-random-functions/|access-date=2021-09-04|website=NCC Group Research|language=en-US}}{{Better source needed|date=September 2021}} VRFs can be used for defense against offline enumeration attacks (such as dictionary attacks) on data stored in hash-based data structures.

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{{Cite book|last1=Micali|first1=Silvio|last2=Reyzin|first2=Leonid|title=Advances in Cryptology — CRYPTO 2001 |chapter=Soundness in the Public-Key Model |date=2001|editor-last=Kilian|editor-first=Joe|series=Lecture Notes in Computer Science|volume=2139 |language=en|location=Berlin, Heidelberg|publisher=Springer|pages=542–565|doi=10.1007/3-540-44647-8_32|isbn=978-3-540-44647-7|doi-access=free}}) 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.{{Cite book|last=Dodis|first=Yevgeniy|title=Public Key Cryptography — PKC 2003 |chapter=Efficient Construction of (Distributed) Verifiable Random Functions |date=2002|editor-last=Desmedt|editor-first=Yvo G.|series=Lecture Notes in Computer Science|volume=2567 |language=en|location=Berlin, Heidelberg|publisher=Springer|pages=1–17|doi=10.1007/3-540-36288-6_1|isbn=978-3-540-36288-3|doi-access=free}}

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{{How|date=August 2021}}, provably prevents this type of attack.{{Cite web|last=Goldberg|first=Sharon|title=NSEC5: Provably Preventing DNSSEC Zone Enumeration|url=https://www.cs.bu.edu/~goldbe/papers/nsec5.html|access-date=2021-08-26|website=www.cs.bu.edu}}{{Importance inline|date=August 2021|reason=Has NSEC5 been used in any notable instance?}}

Category:Cryptographic algorithms

Category:Cryptographic primitives

Category:Pseudorandomness