A signature scheme has the following two functions for a key pair $(k, K)$:
- $\sigma = \operatorname{Sign}_k(m)$
- $\mathit{valid?} = \operatorname{Verify}_K(m, \sigma)$
A VRF has slightly more:
- $(\sigma, x) = \operatorname{VRF}_k(m)$
- $\mathit{valid?} = \operatorname{Verify}_K(m, \sigma, x)$
Without knowledge of the public key $K$ and the signature $\sigma$, the VRF output $x$ appears to be an independent uniform random bit string for each distinct $m$. That is why it is a verifiably pseudorandom function: except for verifiability, it appears to have independent uniform random outputs.
In contrast, for example, RSA-based signatures typically have a per-key distribution that is distinctive enough to deanonymize signers in practice (popular exposition; actually this was RSA-based ciphertexts but the principle is the same). While EdDSA signatures do not have a distinctive per-key distribution, they easily distinguished from uniform random bit strings because they encode $(R, s)$ where $R$ is a point on the curve (only about half of such bit strings will be so) and $s$ is an integer below the order of the curve (which is often substantially less than the number of bit strings of the same length).
If there is exactly one $\sigma$ for each $m$ under any particular public key $K$, then we can devise a VRF with the help of a uniform random function $H$ as follows:
- $\operatorname{VRF}_k(m) := (\sigma, H(\sigma))$, where $\sigma = \operatorname{Sign}_k(m)$
- $\operatorname{Verify}_K(m, \sigma, x) := (\operatorname{Verify}_K(m, \sigma) \mathrel{\text{and}} x \stackrel?= H(\sigma))$
Choosing, e.g., $H = \operatorname{SHA-256}$ makes a practical VRF that is secure against $H$-generic adversaries, or ‘secure in the random oracle model’, because without knowledge of the unique $\sigma$ for any particular $m$, $H(\sigma)$ is a uniform random bit string independent of anything else you can compute.
(More on signatures vs. VRFs with references.)
