imported>OAbot: Open access bot: url-access updated in citation with #oabot.

2025-05-26T13:21:01Z

Open access bot: url-access updated in citation with #oabot.

New page

{{Short description|Public-key cryptographic pseudorandom function}}
In [[cryptography]], a '''verifiable random function''' (VRF) is a public-key [[pseudo-random function|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''<ref name=":9" />), can check that this value was indeed calculated correctly, yet this information cannot be used to find the secret key.<ref name=":0">{{Cite tech report|last=Goldberg|first=Sharon|last2=Vcelak|first2=Jan|last3=Papadopoulos|first3=Dimitrios|last4=Reyzin|first4=Leonid|date=5 March 2018|title=Verifiable Random Functions (VRFs)|url=https://open.bu.edu/bitstream/handle/2144/29225/draft-irtf-cfrg-vrf-01.pdf?sequence=2&isAllowed=y|journal=|language=en|access-date=15 August 2021}}</ref>

A verifiable random function can be viewed as a public-key analogue of a [[Hash function|keyed cryptographic hash]]<ref name=":0" /> and as a [[cryptographic commitment]] to an exponentially large number of seemingly random bits.<ref name=":7" /> 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.<ref name=":7" /><ref name=":8">{{cite conference|last1=Micali|first1=Silvio|author-link=Silvio Micali|last2=Rabin|first2=Michael O.|author-link2=Michael Rabin|last3=Vadhan|first3=Salil P.|author-link3=Salil Vadhan|year=1999|title=Verifiable random functions|url=https://dash.harvard.edu/bitstream/handle/1/5028196/Vadhan_VerifRandomFunction.pdf|conference=40th Annual Symposium on Foundations of Computer Science|pages=120–130|doi=10.1109/SFFCS.1999.814584|isbn=0-7695-0409-4|book-title=Proceedings of the 40th IEEE Symposium on Foundations of Computer Science}}</ref>

The concept of a VRF was introduced by [[Silvio Micali|Micali]], [[Michael O. Rabin|Rabin]], and [[Salil Vadhan|Vadhan]] in 1999.<ref name=":8" /><ref name=":11">{{Cite web|last=Potter|first=John|date=9 September 2021|title=How Can Value Investors Profit in the Crypto Ecosystem?|url=https://finance.yahoo.com/news/value-investors-profit-crypto-ecosystem-121413276.html|access-date=19 September 2021|website=finance.yahoo.com|language=en-US}}</ref> 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.<ref name=":8" /> 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 [[Primality test|probabilistic primality test]].<ref name=":7" /><ref name=":8" /> The verifiable unpredictable function thus proposed, which is provably secure if a variant of the [[RSA (cryptosystem)|RSA problem]] is hard, is defined as follows: The public key ''PK'' is <math>(m, r, Q, coins)</math>, where ''m'' is the product of two random primes, ''r'' is a number randomly selected from <math>\mathbb{Z}_m^*</math>, ''coins'' is a randomly selected set of bits, and ''Q'' a function selected randomly from all polynomials of degree <math>2k^2 - 1</math> over the field <math>GF(2^k)</math>. The secret key is <math>(PK, \phi(m))</math>. Given an input ''x'' and a secret key ''SK'', the VUF uses the prime sequence generator to pick a corresponding prime <math>p_x</math> (the generator requires auxiliary inputs ''Q'' and ''coins''), and then computes and outputs <math>r^{1/p_x} \pmod{m}</math>, which is easily done by knowledge of <math>\phi(m)</math>.<ref name=":8" />

In 2005, an efficient and practical verifiable random function was proposed by Dodis and Yampolskiy.<ref name=":7">{{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}}</ref><ref name=":1">{{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}}</ref> When the input <math>x</math> is from a small domain (the authors then extend it to a larger domain), the function can be defined as follows:
:<math> F_{SK}(x) = e(g, g)^{1/(x+SK)} \quad\mbox{and}\quad p_{SK}(x) = g^{1/(x+SK)}, </math>
where ''e''(·,·) is a [[bilinear map]]. To verify whether <math>F_{SK}(x)</math> was computed correctly or not, one can check
if <math>e(g^x PK, p_{SK}(x))=e(g,g)</math> and <math>e(g, p_{SK}(x))=F_{SK}(x)</math>.<ref name=":7" /><ref name=":1" /> To extend this to a larger domain, the authors use a tree construction and a [[universal hash function]].<ref name=":7" /> This is secure if it is hard to break the "q-Diffie-Helman inversion assumption", which states that no algorithm given <math>(g, g^x, \dots, g^{x^q})</math> can compute <math>g^{1/x}</math>, and the "[[q-decisional bilinear Diffie-Helman inversion assumption]]", which states that it is impossible for an efficient algorithm given <math>(g, g^{x}, \ldots, g^{(x^q)}, R)</math> as input to distinguish <math>R=e(g,g)^{1/x}</math> from random, in the group <math>\mathbb{G}</math>.<ref name=":7" /><ref name=":1" />

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|decision linear assumption]].<ref name=":2">{{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}}</ref> This is the first such VRF constructed that does not depend on a "Q-type complexity assumption".<ref name=":2" />

In 2019, Bitansky showed that VRFs exist if non-interactive witness-indistinguishable proofs (that is, weaker versions of [[non-interactive zero-knowledge proof]]s for [[NP (complexity)|NP problems]] that only hide the witness that the prover uses<ref name=":9" /><ref>{{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}}</ref>), 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<ref>{{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}}</ref>) also do.<ref name=":9">{{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}}</ref>

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 cryptography|post-quantum secure]] VRF based on [[lattice-based cryptography]].<ref name=":10">{{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}}</ref>

==Uses and applications==

VRFs provide deterministic pre-commitments for low entropy inputs which must be resistant to brute-force [[Preimage attack|pre-image attacks]].<ref>{{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}}</ref>{{Better source needed|date=September 2021}} VRFs can be used for defense against offline enumeration attacks (such as [[dictionary attack]]s) on data stored in hash-based data structures.<ref name=":0" />

=== 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<ref>{{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}}</ref>) with three rounds in the bare model<ref name=":7" /><ref name=":2" />
* Non-interactive lottery systems<ref name=":7" /><ref name=":2" />
* Verifiable transaction escrow schemes<ref name=":7" /><ref name=":2" />
*Updatable zero-knowledge databases<ref name=":2" />
*E-cash<ref name=":2" />
VRFs can also be used to implement [[random oracle]]s.<ref>{{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}}</ref>

=== 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{{How|date=August 2021}}, provably prevents this type of attack.<ref>{{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}}</ref>{{Importance inline|date=August 2021|reason=Has NSEC5 been used in any notable instance?}}

==References==
<references/>

[[Category:Cryptographic algorithms]]
[[Category:Cryptographic primitives]]
[[Category:Pseudorandomness]]

Verifiable random function - Revision history

imported>OAbot: Open access bot: url-access updated in citation with #oabot.