For example we have asymmetric signature scheme(RSA or ECC based) and VRF(also can be RSA/ECC based), both of them can be verified using public key of the signer/hasher and also are unique for each message. So what is the difference?


First, you need more than just a signature, because a VRF produces both an output and a proof. To an observer, the output is uniformly distributed unless the observer also has the proof, which can be used to verify the output.

With a signature scheme and a random oracle $H$, you could use a signature $s$ on a message $m$ as a proof and $h = H(s)$ as an output: then the output $h$ is uniformly distributed if you don't know the proof, but knowing the proof $s$ you can (a) verify that $s$ is a signature on $m$, and (b) verify that $h = H(s)$.

However, that's not enough, because signature schemes do not usually guarantee uniqueness of the signature. ECDSA signatures are malleable: if $(x(R), s)$ is an ECDSA signature, then so is $(x(-R), -s) = (x(R), -s)$. EdDSA signatures, of the form $(R, s)$ instead, hash $R$ together with the message so it can't be changed any more than the message can, but $(R, s + \ell)$ makes another valid signature if encodable, where $\ell$ is the order of the standard base point.

Further, ECDSA and EdDSA are necessarily randomized, and the signer can choose any per-signature secret nonce they want without the verifier noticing. Standard EdDSA prescribes a particular nonce so that the signer doesn't accidentally leak the private key when signing two different messages, but verifiers can't tell if a signer uses a different nonce. Similarly, the widely deployed RSASSA-PSS signature scheme is randomized, so it doesn't provide uniqueness either.

That said, we can still use the RSA primitive to make a VRF if we pick a deterministic RSA signature scheme such as RSA-FDH with a fixed full-domain hash. This is what the IETF Internet-Draft draft-goldbe-vrf, currently under discussion at the CFRG, does for RSA-FDH-VRF.

We can also adapt elliptic curve signatures such as EdDSA to make a VRF, with a little more work. I won't go into the details, but draft-goldbe-vrf has one construction called EC-VRF, and Open Whisper Systems (creators of Signal) developed another called VXEdDSA.

Further reading:

P.S. Fun fact: RSA signatures aren't uniformly distributed even if you don't know the public key. Since every signature will involve an integer below the modulus $n$, with enough signatures one can solve the German tank problem to deanonymize signers in practice. Of course, you could do rejection sampling to force them below $2^{\lfloor\lg n\rfloor}$.


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.