<p>I'm going to use the Schnorr equation here (<code>s = k + H(R||P||m)*d</code> for signature <code>(R,s)</code>, pubkey <code>P = d*G</code>, message <code>m</code>), but everything equally applies to ECDSA (which uses <code>s = (H(m) + R.x*d) / k</code>), or even to mixes between the two. All equations are modulo <code>n</code>, the group order.</p>
<h3>The same nonce</h3>
<p>Imagine you have two signatures with the same private key and the <strong>same</strong> nonce, on two different messages. That means you have:</p>
<ul>
<li><code>s1 = k + H(R||P||m1)*d</code></li>
<li><code>s2 = k + H(R||P||m2)*d</code></li>
</ul>
<p>Subtracting these two equations from each other yields:</p>
<ul>
<li><code>s2 - s1 = (H(R||P||m2) - H(R||P||m1))*d</code></li>
</ul>
<p>Which can be solved for <code>d</code>:</p>
<ul>
<li><code>d = (s2 - s1) / (H(R||P||m2) - H(R||P||m1)</code></li>
</ul>
<h3>Nonces with known offset</h3>
<p>So, we know you shouldn't use the same nonce for multiple signatures. But what if you use nonces <code>k1</code> and <code>k2</code> where <code>k1</code> is random, but <code>k2 = k1 + f</code>, for attacker-known offset <code>f</code>.</p>
<p>Now you get:</p>
<ul>
<li><code>s1 = k1 + H(R||P||m1)*d</code></li>
<li><code>s2 = k2 + H(R||P||m2)*d = k1 + f + H(R||P||m2)*d</code></li>
</ul>
<p>Subtracting again gives us:</p>
<ul>
<li><code>s2 - s1 = f + (H(R||P||m2) - H(R||P||m1)*d</code></li>
</ul>
<p>In other words:</p>
<ul>
<li><code>d = (s2 - s1 - f) / (H(R||P||m2) - H(R||P||m1)</code></li>
</ul>
<h3>Nonces with known factor</h3>
<p>Ok, so the attacker cannot know the difference between the two two nonces. What if they only know a factor between them? <code>k2 = k1*u</code>.</p>
<ul>
<li><code>s1 = k1 + H(R||P||m1)*d</code></li>
<li><code>s2 = k2 + H(R||P||m2)*d = k1*u + H(R||P||m2)*d</code></li>
</ul>
<p>Computing <code>s2 - u*s1</code> now gives:</p>
<ul>
<li><code>s2 - u*s1 = H(R||P||m2)*d - H(R||P||m1)*d*u</code></li>
</ul>
<p>And thus:</p>
<ul>
<li><code>d = (s2 - u*s1) / (H(R||P||m2) - H(R||P||m1)*u)</code></li>
</ul>
<p>So, that too is a problem.</p>
<h3>Arbitrary known relation between the nonces</h3>
<p>If the relation between the nonces is more complex than a linear relation of the form <code>k2 = u*k1 + f</code>, 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.</p>
<p>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:</p>
<ul>
<li>All nonces are uniformly randomly generated</li>
<li>Nonces are computed as output of a PRF (pseudorandom function); which roughly corresponds to what RFC6979 does (seeding the PRF with the signer key).</li>
<li>MuSig-DN's deterministic nonce function</li>
</ul>
<p>On the other hand, we know of a number of ways which are actively broken:</p>
<ul>
<li>Nonces which have a known linear relation with each other (as demonstrated above)</li>
<li>Nonces which are drawn from a small range of numbers.</li>
</ul>
<p>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 &quot;what property is needed&quot;; all we know is some techniques that work.</p>

CC BY-SA 4.0
2021-11-18T10:00:35.500Z
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.
real-or-random
CC BY-SA 4.0
2021-11-18T15:29:34.297Z
This is a very informative answer, thank you.
Jimmy Song
CC BY-SA 4.0
2024-03-08T12:44:26.463Z
how and where do you calculate the formulas you mentioned here? I couldn't find any source.
glhn
CC BY-SA 4.0
2024-03-08T15:08:06.753Z
I derived them myself.
Pieter Wuille
CC BY-SA 4.0
2021-11-17T22:10:22.940Z
2021-11-18T21:33:51.873Z
2021-11-18T21:33:51.873Z
Pieter Wuille
<p>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.</p>

CC BY-SA 4.0
2021-11-18T21:30:29.123Z
Related: https://bitcoin.stackexchange.com/q/73622/5406, https://bitcoin.stackexchange.com/q/35848/5406
Murch
<signature><nonce>
Why is it important that nonces when signing not be related?
Jimmy Song
# Why is it important that nonces when signing not be related?

(Asked by: username_0 on 2021-11-17)

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.

**Tags:** signature, nonce

> **Comments:**
> **username_1**: Related: https://bitcoin.stackexchange.com/q/73622/5406, https://bitcoin.stackexchange.com/q/35848/5406  

---

## 1 answers

### Answer by username_2 on 2021-11-17. Score: 10 | Accepted answer

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.

> **Comments:**
> **username_3**: 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.  
> **username_0**: This is a very informative answer, thank you.  
> **username_4**: how and where do you calculate the formulas you mentioned here? I couldn't find any source.  
> **username_2**: I derived them myself.  

---

