Cryptography
elliptic-curves signature probability eddsa
Updated Fri, 20 May 2022 20:40:43 GMT

Likelihood of signature collision with EdDSA


Taking EdDSA as an example, given the length of a signature is 512-bits for a given data payload, what is the probability of a collision where there is another 512-bit value that is also a valid signature?

With symmetric crypto we know there is only one single key in the entire space that will validly decrypt data encrypted with the same key.

Can we provably state that for a given payload and given private key, there is only one valid signature in the 512-bit signature space? That is, no other signature exists that could be validated with the public key counterpart to the private key that created the signature.




Solution

Can we provably state that for a given payload and given private key, there is only one valid signature in the 512-bit signature space?

No. If you consider EdDSA verification a legitimate signer can generate more than one signature of a given message, and all will pass EdDSA verification. However, only the signature generated with the EdDSA signing procedure will pass cofactorless verification.

More details about how to generate alternative valid signatures are provided in this answer.

Regarding the more broader question:

Taking EdDSA as an example, given the length of a signature is 512-bits for a given data payload, what is the probability of a collision where there is another 512-bit value that is also a valid signature?

Requiring specifically to pass cofactorless verification only (to avoid the other valid signatures generated by the above technique), there should be a valid $S$ for each possible value of $r$. Since $R$ depends fully on $r$, and $0 \le r < L$, there are at least $L$ possible valid signatures, where $L$ is the order of the large prime subgroup. For ed25519, $L = 2^{252}+27742317777372353535851937790883648493$





Comments (2)

  • +0 – Ah great, thanks @Ruggero, so it's at least unique within the finite cyclic group for Ed25519, but not in the 2^512 signature space, would that be a fair summation? — Jul 06, 2020 at 14:07  
  • +0 – @Woodstock this is what I think for cofactorless verification. — Jul 06, 2020 at 19:29  


External Links

External links referenced by this document: