3
$\begingroup$

The output of VRF contains two parts, the first is the output of the VRF hashing and the second is the proof of correctness. In a unique signature scheme, the signature also contains two parts which are similar to the VRF.

The previous works pointed out the VRF can be obtained via a unique signature, but in general, they have the same outputs, so I am confusing what are the main differences between them? Is there a generic framework of how to construct a VRF from the unique signature? Or we can say, once obtained a unique signature, then we can say it is a VRF?

$\endgroup$
2
$\begingroup$

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.)

| improve this answer | |
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.