Why is it important that nonces when signing not be related?

Question

I understand that if nonces (usually denoted k in the signature algorithm) are related signing with the same public key that this reveals information about the private key. I would like to get a better conceptual understanding of why this is.

Answer 1

I'm going to use the Schnorr equation here (s = k + H(R||P||m)*d for signature (R,s), pubkey P = d*G, message m), but everything equally applies to ECDSA (which uses s = (H(m) + R.x*d) / k), or even to mixes between the two. All equations are modulo n, the group order.

The same nonce

Imagine you have two signatures with the same private key and the same nonce, on two different messages. That means you have:

• s1 = k + H(R||P||m1)*d
• s2 = k + H(R||P||m2)*d

Subtracting these two equations from each other yields:

• s2 - s1 = (H(R||P||m2) - H(R||P||m1))*d

Which can be solved for d:

• d = (s2 - s1) / (H(R||P||m2) - H(R||P||m1)

Nonces with known offset

So, we know you shouldn't use the same nonce for multiple signatures. But what if you use nonces k1 and k2 where k1 is random, but k2 = k1 + f, for attacker-known offset f.

Now you get:

• s1 = k1 + H(R||P||m1)*d
• s2 = k2 + H(R||P||m2)*d = k1 + f + H(R||P||m2)*d

Subtracting again gives us:

• s2 - s1 = f + (H(R||P||m2) - H(R||P||m1)*d

In other words:

• d = (s2 - s1 - f) / (H(R||P||m2) - H(R||P||m1)

Nonces with known factor

Ok, so the attacker cannot know the difference between the two two nonces. What if they only know a factor between them? k2 = k1*u.

• s1 = k1 + H(R||P||m1)*d
• s2 = k2 + H(R||P||m2)*d = k1*u + H(R||P||m2)*d

Computing s2 - u*s1 now gives:

• s2 - u*s1 = H(R||P||m2)*d - H(R||P||m1)*d*u

And thus:

• d = (s2 - u*s1) / (H(R||P||m2) - H(R||P||m1)*u)

So, that too is a problem.

Arbitrary known relation between the nonces

If the relation between the nonces is more complex than a linear relation of the form k2 = u*k1 + f, in general, there will not be a simple formula that lets you readily compute the private key from the signatures. However, the lack of a known formula does not imply none exists, and doesn't constitute a security proof.

The question we concern ourselves with, is under what circumstances the relation between the nonces is sufficiently complex that attackers cannot exploit it. It turns out there are a few ways which have a proof:

• All nonces are uniformly randomly generated
• Nonces are computed as output of a PRF (pseudorandom function); which roughly corresponds to what RFC6979 does (seeding the PRF with the signer key).
• MuSig-DN's deterministic nonce function

On the other hand, we know of a number of ways which are actively broken:

• Nonces which have a known linear relation with each other (as demonstrated above)
• Nonces which are drawn from a small range of numbers.

But in between those two, there is a huge gap of techniques which are neither known to be broken, nor proven secure. Many of them might well be secure, but we don't know. So unfortunately, that means there is actually no answer to the question "what property is needed"; all we know is some techniques that work.