How can we prevent duplicate key attacks on digital signatures

A limitation digital signatures is that for a given signature σ of a message m corresponding to a public key pk, an adversary could generate a pk', sk' that produces a signature σ' for m, such that σ' = σ. How can we create a signing function and verification function that is resistant to this attack?

DSKS attacks belong to a class of attacks on signature schemes that break « exclusive ownership ». A property that is not guaranteed by standard EUF-CMA security.

One solution to this is the BUFF construction. It is very much similar to what Boneh-Shoup recommends. In short, given a signature key pair $(sk,pk)$ to sign $m$, first compute $h = H(m,pk)$, then $\sigma = Sig(sk,h)$. The signature is $(h, \sigma)$. Verification compares the hashes and validates the signature.

The BUFF construction offers more features than exclusive ownership; the paper talks about them.

I think that kind of attack is only possible when you have a "formula" for calculating signature from private key and message hash that can be inverted - choose a signature and a message and calculate the private key. Various variants of Schnoor's and ElGamel signature schemes has this property.

The easiest solution I can think of is to use a hash-based signature such as some variant of the XMSS, LMS, and SPHINCS signature scheme.