2
$\begingroup$

Intuitively, it seems that the hash of a BLS signature could be used as a VRF as well. In a nutshell, BLS-Signature is the VRF output and the verification first checks the signature is valid, and then compute the hash over it to provide the VRF output. (Or similarly, one can provide H(BLS-Signature) as the VRF output and BLS-Signature as the VRF proof.)

  1. Is this scheme a VRF ? Given a collision resistant hash function of course.
  2. How would one would go about proving it ?
Improve this question
$\endgroup$
2
$\begingroup$

Yes, in the random oracle model, the hash of a BLS signature makes a VRF essentially as secure as the BLS signature scheme (provided the verifier accepts only the unique canonical encoding of each signature).

This works because BLS signatures are unique. Fix a pairing $e\colon G_1 \times G_2 \to G_T$ on groups $G_1$ and $G_2$ of prime order. For any fixed $A \in G_2$, the homomorphism $\phi_A\colon \sigma \to e(\sigma, A)$ is an injection (or the system is trivially insecure) because $G_1$ has prime order. Let $B \in G_2$ be the standard base point. A putative signature $\sigma \in G_1$ under public key $P \in G_2$ on a message $m$ satisfies the signature equation $$e(H(m),P) = e(\sigma,B) = \phi_B(\sigma).$$ Since $\phi_B$ is an injection, there is at most one possible signature $\sigma$ for any public key $P$ and any message $m$.

Improve this answer
$\endgroup$
8
  • $\begingroup$ Does that fullfill the guarantees of a VRF though ? From the first VRF paper from Micali, uniqueness and pseudo randomness are not the same thing. BLS is a VUF but not a VRF. Furthermore, it does not seem to be resistant against malicious key generation attack (to fulfill pseudo randomness). $\endgroup$ – Nikkolasg Oct 18 '19 at 12:09
  • $\begingroup$ @Nikkolasg BLS brings unpredictability and uniqueness; the random oracle brings uniformity of the output. No matter what public key you choose (as long as it is a valid public key in $G_2$), there is at most one signature $\sigma$ for each message $m$, and $H(\sigma)$ is an independent uniform random bit string for each $\sigma$. (Maybe use $H(\text{‘message’} \mathbin\| m)$ and $H(\text{‘output’} \mathbin\| \sigma)$ if you're using the same hash function $H$ for the signature's message hash and the VRF's output hash.) $\endgroup$ – Squeamish Ossifrage Oct 18 '19 at 13:42
  • $\begingroup$ (It may also be prudent to hash the public key in too: $H(\text{‘message’} \mathbin\| P \mathbin\| m)$, $H(\text{‘output’} \mathbin\| P \mathbin\| \sigma)$. This is a cheap measure that may be helpful to mitigate the impact of multi-target attacks and perhaps more exotic scenarios where the adversary knows a relation between two public keys but not what the two public keys are a priori.) $\endgroup$ – Squeamish Ossifrage Oct 18 '19 at 13:48
  • $\begingroup$ Imagine I would be using a signature scheme that produce a biased distribution of signature. If I hash the signature, the output will loose its algebraic structure but the distribution will still be biased no ? My worry is (1) that pseudo-randomness is not proven for BLS and (2) even if it is, is it as well for malicious key generation ? $\endgroup$ – Nikkolasg Oct 18 '19 at 21:41
  • $\begingroup$ The output of a random oracle on inputs that an adversary cannot predict (like a signature on a message) is uniformly distributed, and consequently indistinguishable from uniform random—that's the really easy part that works for any signature scheme! Uniqueness, which has to be proven specifically for BLS since the standard notion of security doesn't entail uniqueness, holds for any public key in $G_2$. That is, there is no public key in $G_2$ for which uniqueness fails to hold. $\endgroup$ – Squeamish Ossifrage Oct 18 '19 at 21:45

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.