Verifiable Random Functions (VRFs)
1. Introduction
The concept of Verifiable Random Functions (VRFs) is a powerful cryptographic tool that
combines pseudorandomness and verifiability in a single construction. Traditional
pseudorandom functions (PRFs) provide outputs that appear random but cannot be verified
without knowledge of the secret key. In contrast, a VRF enables the computation of a
pseudorandom value along with a publicly verifiable proof that the value was correctly generated
from a given input.
The idea extends the Goldreich–Goldwasser–Micali (GGM) pseudorandom function model
(1986). GGM proved that one can simulate a random oracle using a function derived from a
secret seed. However, the limitation of pseudorandom functions is that, without the seed, one
cannot confirm whether an output is genuine. This means the owner of the secret seed can cheat
by giving false outputs.
VRFs solve this by introducing proofs of correctness, ensuring anyone can verify the
legitimacy of an output without learning the secret seed.
2. Motivation
The need for verifiable pseudorandomness arises in scenarios where the evaluator (holder of the
secret key) should be accountable for the outputs. In pseudorandom oracles, if the seed owner
lies about an output, there is no way to detect it. Revealing the seed allows verification but
destroys secrecy, making the function predictable.
Hence, the paper proposes a new type of function — a verifiable pseudorandom function —
where:
1. The seed owner can compute the function output and a proof of its correctness.
2. The proof can be verified publicly without revealing the seed.
3. Outputs at other points remain unpredictable.
VRFs are therefore ideal for decentralized systems, cryptographic lotteries, blockchain consensus
mechanisms, and secure randomness generation — places where public verifiability and
unpredictability must coexist.
3. Concept and Definition of VRF
A Verifiable Random Function (VRF) is defined as a function that takes an input x and
produces an output v = f(x) along with a proof π.
Anyone with the public key (PK) can verify that v was correctly computed from x using the
proof, without being able to compute the function for other inputs.
The system is built around three algorithms:
1. G (Key Generation):
Produces a key pair — a secret key (SK) and a public key (PK).
The public key acts as a commitment to the function.
2. F (Evaluation):
Using SK, computes both the function value and a proof:
F(SK, x) → (v, π).
3. V (Verification):
Using PK, verifies correctness:
V(PK, x, v, π) → {YES, NO}.
4. Properties of a Secure VRF
For a function to qualify as a valid VRF, it must satisfy three critical properties:
1. Domain-Range Correctness:
For any valid input, the function always produces outputs in the expected range.
2. Unique Provability:
For every input x, there is only one valid output that can be proven correct.
This prevents ambiguity or multiple valid results.
3. Residual Pseudorandomness:
Even after revealing many input-output pairs with proofs, the outputs at unqueried inputs
must still appear random to any efficient adversary.
These properties ensure that the function is both secure and verifiable, combining features of
digital signatures and pseudorandom generators.
5. Relation to Signatures and Unpredictability
A digital signature scheme also allows verification of correctness, but it differs from a VRF in
two main aspects:
1. Uniqueness:
Most digital signature schemes are probabilistic, meaning a message may have multiple
valid signatures. A VRF enforces a single unique output per input.
2. Pseudorandomness:
Digital signatures are only unpredictable, not random-looking. A VRF ensures that
outputs appear uniformly random unless proven otherwise.
Thus, the authors introduce a related primitive called a Verifiable Unpredictable Function
(VUF) — a function that guarantees unique, verifiable outputs but focuses on unpredictability
instead of pseudorandomness. The paper then demonstrates how a VUF can be converted into a
VRF using the Goldreich–Levin hard-core bit theorem, which transforms unpredictability into
pseudorandomness.
6. Construction of the VRF
The authors construct the first practical VRF using RSA-based cryptography under a modified
assumption called the RSA with large prime exponents. The design proceeds in three steps:
1. Step 1 – Constructing a Verifiable Unpredictable Function (VUF):
o Based on Adi Shamir’s unpredictable number generator.
o Defines the function f(i) = r^(1/e_i) mod m, where:
§ r and m are public values,
§ e_i are large distinct prime exponents,
§ v = r^(1/e_i) mod m is the computed output.
o Verification simply checks whether v^(e_i) ≡ r (mod m).
1. Step 2 – Converting the VUF to a VRF:
o Uses the Goldreich–Levin technique to extract a pseudorandom bit from an
unpredictable function.
o Ensures that the VRF outputs are indistinguishable from random values.
1. Step 3 – Extending the Input Length:
o Implements a tree-based construction to allow the VRF to handle inputs of
arbitrary size.
o Each node in the tree represents a bit of the input, and proofs are formed along the
computation path.
7. Security Assumptions and Theorem
The construction relies on the RSA Hardness Assumption — that is, given an integer m
(product of two large primes) and an exponent e, it is computationally infeasible to compute the
e-th root modulo m.
The main theorem of the paper states:
If the RSA function with large prime exponents cannot be inverted in polynomial time,
then a VRF with unrestricted input length and pseudorandom outputs exists.
Formally, under this assumption, the proposed VRF construction achieves:
· Unpredictability for unqueried inputs.
· Verifiability for all computed outputs.
· Uniqueness of valid proofs.
· Security proportional to that of RSA.
8. Applications of VRFs
Verifiable Random Functions have numerous applications in cryptography and distributed
systems, including:
· Blockchain and Consensus Protocols: To select leaders or committee members fairly
and verifiably.
· Public Randomness Beacons: To generate randomness that can be publicly verified.
· Non-Interactive Cryptographic Proofs: To ensure data integrity without repeated
communication.
· Secure Lotteries and Elections: To generate and verify random selections transparently.
VRFs have since become fundamental to modern cryptographic protocols like Algorand
(blockchain consensus), DNSSEC, and secure multiparty computations.
9. Conclusion
The paper by Micali, Rabin, and Vadhan established a groundbreaking framework for combining
verifiability and pseudorandomness efficiently. The construction of VRFs under RSA
assumptions provided the first non-interactive and practical method to produce publicly
verifiable random outputs.
By ensuring that every output is both unpredictable and provably correct, VRFs eliminate the
need for trust in the seed owner. This innovation has deeply influenced the design of secure
systems that require both randomness and accountability, forming the foundation of many
modern cryptographic and blockchain technologies.