Is it possible to derive an Ed25519-public-key from an Ed25519-signature?

Question

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)?

Answer 1

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.