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$
External Links
External links referenced by this document: