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 personal 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 will 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 for those who 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 offers 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 offers:

• 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, generally, there won’t be a easy components that permits you to readily compute the personal key from the signatures. Nonetheless, the shortage of a recognized components doesn’t indicate none exists, and does not represent a safety proof.

The query we concern ourselves with, is below 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

Alternatively, we all know of various 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 big hole of methods that are neither recognized to be damaged, nor confirmed safe. Lots of them may effectively be safe, however we do not know. So sadly, which means there may be really no reply to the query “what property is required”; all we all know is a few methods that work.