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

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.

• – Murch
Nov 18, 2021 at 21:30

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.

• In particular, there is no known method which enables a signer to send a "master public nonce" such that verifiers can derive many actual public nonces `R` from it, e.g., using the message as an input to the derivation. I'm not aware of a proof that such a method cannot exist but finding one will be a major academic breakthrough. I've seen more than one attempt to invent such a method as an optimization to MuSig(2) or ordinary Schnorr signatures. Be assured that if such a method existed, cryptographers would have added it to schemes and standards and not leave this trick to implementers. Nov 18, 2021 at 10:00
• This is a very informative answer, thank you. Nov 18, 2021 at 15:29