If you have an Ed25519-signature and the signed message, can you derive the corresponding public-key or is the signature anonymous (except if you already know the public-key of course)?


From Wikipedia, an EdDSA signature is a pair $(R, s)$ of a point $R \in E(k)$ and scalar $s \in \mathbb Z$ satisfying the verification equation $$[2^c s] B = [2^c] R + [2^c H(R, A, M)] A,$$ where $E/k$ is the underlying curve over a field $k$, $B \in E(k)$ is the standard $k$-rational base point of large prime order and cofactor $2^c$, and $A \in E(k)$ is the public key.

It is tempting to say that if you had $h = H(R, A, M)$, then you could simply compute an inverse $k$ of $h$ modulo $\ell$ and compute $A = [k] ([s] B - R)$, and hope that complications with the the covfefe $2^c$ won't eat your lunch. But, by design, the only way to compute $h$ is in fact to know $A$ a priori to feed it into $H$. And unless you break the preimage resistance of $H(R, A, M)$, which is SHA-512 in the case of Ed25519, you won't get very far doing this.

However, that only answers the question you asked literally: Can I derive $A$ from an Ed25519 signature? You also mentioned anonymity, which is a slightly different kettle of fish. The question for anonymity should be the key privacy property: Given two signatures $(R, s)$ and $(R', s')$, can I tell with nonnegligible probability whether they were made by the same key pair or not?

In the case of most RSA-based signature schemes, the answer is yes (to both questions), thanks to a problem of counting German tanks well-known in the anglophone empirical inference literature—that is, most RSA-based signature schemes do not provide key-privacy. What about Ed25519?

The answer may be a little trickier, because we don't demand recovery of the public key as the standard approach to breaking RSA-based key privacy works. The literature does not seem to be rife with references about key privacy for signature schemes, but there is a simpler sufficient criterion for key privacy of encryption schemes which could likely be adapted to signature schemes.

I leave it as an exercise for the reader to adapt this into a sufficient criterion for key privacy of signature schemes, demonstrate that Ed25519 satisfies the criterion, and publish it all to fame and glory in the cryptology literature.

| improve this answer | |
  • 1
    $\begingroup$ The references in this post are not very good. There are better references, and a clearer breakdown of the related notions of key privacy for encryption, anonymity for signature, and key indistinguishability for an exotic kind of signature, in this answer: crypto.stackexchange.com/a/67918 $\endgroup$ – Squeamish Ossifrage Mar 16 '19 at 20:10

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.