Signing – Why is it important that there is no nonce involved when signing?

Here we will use the Schnorr equation (s = k + H(R||P||m)*d for signature (R,s)public key P = d*Gmessage m), but everything applies equally to ECDSA (using: s = (H(m) + R.x*d) / k) or sometimes a combination of the two. All equations are modulo nThis is a group order.

same nonce

There are two signatures with the same private key same The nonce applies to two different messages. This means:

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

Subtracting these two equations from each other gives us the following result:

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

What can be solved d:

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

Nonce with known offset

So we know that we should not use the same nonce for multiple signatures. But what happens if you use a nonce? k1 and k2 where k1 Although it’s random k2 = k1 + fIf the attacker has a known offset f.

Now you can 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 the following result:

• 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)

Nonce with known elements

great. An attacker cannot tell the difference between the two nonces. What if they only knew the elements 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 We now offer:

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

thus:

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

If so, that is also a problem.

Arbitrary known relationships between nonces

When the relationship between nonces is more complex than a linear relationship of the form k2 = u*k1 + fIn general, there is no simple formula that allows you to easily calculate the private key from a signature. However, the absence of a known formula does not mean that the formula does not exist and is not security proof.

The question we are interested in is under what circumstances are the relationships between nonces sufficiently complex that an attacker cannot exploit them? It turns out there are a few ways to do it that have evidence.

• All nonces are generated uniformly and randomly.
• The nonce is computed as the output of a pseudo-random function (PRF). This roughly matches what RFC6979 does (seed the PRF with the signer key).
• MuSig-DN’s deterministic nonce function

On the other hand, we know many ways to be actively disrupted.

• Nonces with a known linear relationship to each other, as described above.
• A Nonce taken from a small range of numbers.

However, there is a huge technology gap between the two that has neither been broken nor proven to be safe. Many of them may be safe, but we don’t know. Unfortunately, this means that there isn’t really an answer to the question “which properties are needed?” All we know is a few technologies that work.