Is it safe to reuse a ECDSA nonce for two signatures if the public keys are different? We denote the s value of an ECDSA signature $(r, s)$ on a message $m$ as:
$s=\frac{H(m)+xr}{k}$

Assume two ECDSA signatures sharing the same nonce $(r, s_1) , (r, s_2)$ on two messages $m_1, m_2$, that verify under two pubkeys $x_1G, x_2G$.  

If the two public keys are equal then the secret keys should be equal $x_1 = x_2$ and we can easily recover the $k$ using the standard attack on nonce reuse. Once we know $k$ we can recover the secret key.

$\frac{H(m_1)-H(m_2)}{(s_1 - s_2)} =\frac{k(H(m_1)-H(m_2))}{H(m_1)-H(m_2)+x_1r - x_2r}$

$x_1 = x_2 \rightarrow x_1r - x_2r = 0$

$\frac{H(m_1)-H(m_2)}{(s_1 - s_2)} =\frac{k(H(m_1)-H(m_2))}{H(m_1)-H(m_2)} = k$

My question is can this attack be made to work if the secret keys are not equal i.e. $x_1 \ne x_2$:

$\frac{H(m_1)-H(m_2)}{(s_1 - s_2)} =\frac{k(H(m_1)-H(m_2))}{H(m_1)-H(m_2)+x_1r - x_2r} = \frac{k(H(m_1)-H(m_2))}{H(m_1)-H(m_2)+ (x_1 - x_2)r}$

If you know either $x_1 - x2$ or $\frac{x_1}{x_2}$  you should be able to compute $k$ as long as $s_1 \ne s_2$.

You can calculate $x_1 - x_2 = \frac{H(m_2) - H(m_1)}{r}$ in case where $s_1 - s_2 = 0$. However this case seems to reduce to the hardness of ECDSA since anyone can compute the pubkey for a new message $m_2$ that verifies under first signature $(s, r)$ using public key recovery.

If $s_1 \ne s_2$ you can compute $\frac{x_1 - x_2}{k}$ which allows you to convert $s_1$ into $s_2$ and vice versa.
Suppose you have two message signature pairs and following values are then public i.e. known to you -


The public keys: $Q_1 (= x_1G)$, $Q_2 (= x_2G)$
The messages and their hashes: $m_1$, $m_2$, $H(m_1)$, $H(m_2)$
The signatures: $(r_1, s_1)$, ($r_2, s_2$)


The following are unknown -


The private keys: $x_1$, $x_2$
The nonce: $k$


The following relations are known as well -


$s_1 = k^{-1}(H(m_1) + r_1x_1)$
$s_2 = k^{-1}(H(m_2) + r_2x_2)$


Note that we have two equations in three unknowns. In order to solve these we'll need to eliminate at least one unknown so that we can write one equation in terms of only one unknown and substitute that into the other equation (resulting in an equation with one unknown which can be solved via basic algebra).

The trick employed when $k$ is used with the same $x$ (i.e. $x_1 = x_2$) is that it eliminate two unknowns ($x_1$ and $x_2$) which yields an equation that is easily solved.

So how do we approach this when $x_1 \ne x_2$? The only way I see is to try to divide $s_1$ by $s_2$ to eliminate $k^{-1}$. Eliminating $x_1$ or $x_2$ seems like it would require index calculus, and that would mean solving ECDLP, which would violate the security assumptions ECDSA is predicated on.

So let's see what $\frac{s_1}{s_2}$ yields -

$$\frac{s_1}{s_2} = \frac{k^{-1}(H(m_1) + r_1x_1)}{k^{-1}(H(m_2) + r_2x_2)}$$
$$\frac{s_1}{s_2} = \frac{H(m_1) + r_1x_1}{H(m_2) + r_2x_2}$$
$$\frac{s_1(H(m_2) + r_2x_2)}{s_2} = H(m_1) + r_1x_1$$
$$\frac{s_1(H(m_2) + r_2x_2) - s_2H(m_1)}{s_2}  = r_1x_1$$
$$\frac{s_1(H(m_2) + r_2x_2) - s_2H(m_1)}{r_1s_2} = x_1$$

Note that we can now remove $x_1$ from the equation defining $s_1$ and we are left with a system of two equations in two variables, which can be solved via linear algebra as long as they are not linearly dependent.

(From here on I'll be using $h_n = H(m_n)$ for the sake of brevity)

$$s_1 = k^{-1}(h_1 + r_1\frac{s_1(h_2 + r_2x_2) - s_2h_1}{r_1s_2})$$
$$k = s_1^{-1}(h_1 + \frac{s_1(h_2 + r_2x_2) - s_2h_1}{s_2})$$

Then doing some more substitution -

$$s_2 = k^{-1}(h_2 + r_2x_2)$$
$$k = s_2^{-1}(h_2 + r_2x_2)$$
$$s_1^{-1}(h_1 + \frac{s_1(h_2 + r_2x_2) - s_2h_1}{s_2}) = s_2^{-1}(h_2 + r_2x_2)$$
$$s_2(h_1 + \frac{s_1(h_2 + r_2x_2) - s_2h_1}{s_2}) = s_1(h_2 + r_2x_2)$$
$$s_2(\frac{h_1s_2 + s_1(h_2 + r_2x_2) - s_2h_1}{s_2}) = s_1(h_2 + r_2x_2)$$
$$(h_1s_2 + s_1(h_2 + r_2x_2) - s_2h_1) = s_1(h_2 + r_2x_2)$$
$$s_1(h_2 + r_2x_2) = s_1(h_2 + r_2x_2)$$

So we're left with a tautology... why? Because substituting for $x_1$ into the first equation essentially left us with two instances of the same equation, just with some extra terms and terms on different sides of the equation. This means we can't solve the system. Or more precisely, that the system we have has infinitely many solutions. A simple way to see this is to consider a simpler system -

$$x = 2y$$
$$2x = 4y$$

You could substitute for $x$ in the second equation but it won't do you any good.



In conclusion, it would appear that nonce reuse with different key pairs does not allow recovery of any secret material. While far from a full or rigorous proof the above should convince you that it at least does not fall victim to an attack that uses the same approach as the nonce reused with the same key setting. In any case, if you have the choice I would advise to avoid this scenario, there are plenty of good ways to generate nonces out there. RFC 6979 is a good place to start.