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.


1 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.

  • 4
    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
  • 2
    This is a very informative answer, thank you.
    – Jimmy Song
    Nov 18, 2021 at 15:29

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

Not the answer you're looking for? Browse other questions tagged or ask your own question.