signature – Why is it vital that nonces when signing not be associated?

I will use the Schnorr equation right here (s = okay + H(R||P||m)*d for signature (R,s), pubkey P = d*G, message m), however every little thing equally applies to ECDSA (which makes use of s = (H(m) + R.x*d) / okay), and even to mixes between the 2. All equations are modulo n, the group order.

The identical nonce

Think about you’ve got two signatures with the identical non-public key and the similar nonce, on two completely different messages. Meaning you’ve got:

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

Subtracting these two equations from one another yields:

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

Which may be solved for d:

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

Nonces with recognized offset

So, we all know you should not use the identical nonce for a number of signatures. However what if you happen to use nonces k1 and k2 the place k1 is random, however 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 once more provides us:

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

In different phrases:

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

Nonces with recognized issue

Okay, so the attacker can’t know the distinction between the 2 two nonces. What in the event that they solely know an element 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 provides:

• 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 an issue.

Arbitrary recognized relation between the nonces

If the relation between the nonces is extra advanced than a linear relation of the shape k2 = u*k1 + f, on the whole, there is not going to be a easy components that allows you to readily compute the non-public key from the signatures. Nonetheless, the dearth of a recognized components doesn’t indicate none exists, and does not represent a safety proof.

The query we concern ourselves with, is beneath what circumstances the relation between the nonces is sufficiently advanced that attackers can’t exploit it. It turns on the market are a number of methods which have a proof:

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

Then again, we all know of plenty of methods that are actively damaged:

• Nonces which have a recognized linear relation with one another (as demonstrated above)
• Nonces that are drawn from a small vary of numbers.

However in between these two, there’s a enormous hole of methods that are neither recognized to be damaged, nor confirmed safe. A lot of them would possibly properly be safe, however we do not know. So sadly, meaning there may be truly no reply to the query “what property is required”; all we all know is a few methods that work.