<p>The construction you're suggesting will likely work as long as you don't sign more than one message. By effectively choosing the R points ahead of time, you've constructed a single-show signature.</p>

<p>However, the derivation you're using for the different R values is pointless. It's not enough that you don't reuse R values; you can't use multiple <em>related</em> R values either. All the R values you are constructing are related through a single linear equation. That is sufficient for an attacker (who knows about the relation) to derive the private key from seeing two signatures.</p>

CC BY-SA 4.0
2018-12-16T10:21:12.390Z
Technically linear relations can be okay so long as there are more unknowns than equations.  E.g. if you agree on a 3000 degree polynomial, you can use messages hashes to pick locations to interpolate, and make up to 2999 signatures.  But critically all of this stuff is SUPER hard to get right and super hard to verify. Most cryptographic constructions are broken.  I would really caution anyone against being too clever with this stuff.
G. Maxwell
CC BY-SA 4.0
2018-12-15T20:17:20.840Z
2018-12-15T23:12:31.513Z
2018-12-15T23:12:31.513Z
Pieter Wuille
<p>I am wondering if the first two roundtrips of pre-committing and then revealing R/r in MuSig signing can be moved to the keygen phase and made deterministic. That reduces the amount of messages that need to be exchanged; since keygen is done only once, we want to expand that phase. This would be especially useful for HD wallets: at the expense of making wallet creation more complicated, signing would need fewer interactions.</p>

<p>The <a href="https://eprint.iacr.org/2018/068.pdf" rel="nofollow noreferrer">musig paper</a> on page 10-11, specifies the following (from perspective of signer 1):</p>

<h2>MuSig scheme</h2>

<p><strong>Key generation</strong></p>

<ol>
<li>generates private key x<sub>1</sub> and corresponding public key X<sub>1</sub></li>
<li>sends X<sub>1</sub></li>
<li>receives X<sub>i</sub></li>
</ol>

<p><strong>Signing (specifically the part about agreeing on R<sub>i</sub>)</strong></p>

<ol>
<li>sends t<sub>1</sub>=H<sub>com</sub>(R<sub>1</sub>)</li>
<li>receives t<sub>i</sub> </li>
<li>sends R<sub>1</sub></li>
<li>receives R<sub>i</sub></li>
<li>checks that H<sub>com</sub>(R<sub>i</sub>)==t<sub>i</sub></li>
</ol>

<p>r<sub>1</sub> is specified to be random.
Signing includes three rounds of interaction, two of which is used for the above steps (agreeing on R<sub>i</sub>).
I want to move these steps to the keygen phase.</p>

<hr>

<p>A HD wallet would presumably use BIP32 to generate X<sub>1</sub>.
Can we use BIP32 for deriving R<sub>i</sub>/r<sub>i</sub> too?</p>

<p>Consider the following scheme instead.
(from cosigners 1's perspective)</p>

<h2>Proposed HD scheme</h2>

<p><strong>HD wallet setup phase</strong></p>

<ol>
<li>generates xprv y<sub>1</sub> and corresponding xpub Y<sub>1</sub></li>
<li>generates xprv k<sub>1</sub> and corresponding xpub K<sub>1</sub></li>
<li>sends xpub Y<sub>1</sub></li>
<li>sends u<sub>1</sub>=H(K<sub>1</sub>)</li>
<li>receives xpub Y<sub>i</sub></li>
<li>receives u<sub>i</sub></li>
<li>sends xpub K<sub>1</sub></li>
<li>receives xpub K<sub>i</sub></li>
<li>checks that H(K<sub>i</sub>)==u<sub>i</sub></li>
</ol>

<p><strong>Key generation</strong></p>

<ol>
<li>from xprv y<sub>1</sub> along some BIP32 path p, derive private key x<sub>1</sub> and public key X<sub>1</sub></li>
<li>from xpub Y<sub>i</sub> along same BIP32 path p, derive public key X<sub>i</sub></li>
<li>from xprv K<sub>1</sub> along same BIP32 path p, derive private key j<sub>1</sub> and public key J<sub>1</sub></li>
<li>from xpub K<sub>i</sub> along same BIP32 path p, derive public key J<sub>i</sub>. </li>
</ol>

<p><strong>Signing (specifically the part about agreeing on R<sub>i</sub>)</strong></p>

<ol>
<li>compute r<sub>1</sub>=j<sub>1</sub>+hash(m) and R<sub>1</sub>=J<sub>1</sub>+hash(m)*G</li>
<li>compute R<sub>i</sub>=J<sub>i</sub>+hash(m)*G</li>
</ol>

<p>This approach only has one round of interaction during signing (sending s<sub>i</sub>, omitted as its not changed from what is described in the paper).</p>

<p>I have read the derandomization section, but the explanation for why it doesn't work requires R<sub>i</sub> to be chosen by the attacker. If we make it deterministically derived, and BIP32 is safe, then this attack does not apply. The paper states "each signer must ensure that whenever any R<sub>j</sub> sent by other cosigners or the message m changes, his r<sub>i</sub> value changes unpredictably. As long as f is deterministic, this implies a circular dependency in the choice of random values."</p>

<p>Where is this circular dependency? The f from RFC 6979 only depends on key and m.</p>

CC BY-SA 4.0
2018-12-14T20:09:16.317Z
I can't comment about the interaction with Musig, but I'll add my intuition here in a comment.  If by your design, the signature's nonce is chosen by the signer by way of *public* key derivation, and this is disclosed to another party who learns the public derivable path between private key and nonce, then they now have a function of the nonce as the public key.  This most likely will leak the private key when a valid signature over some message is published by the signer.
arubi
CC BY-SA 4.0
2018-12-15T02:08:34.807Z
The circular dependency only appears when there are multiple parties. In order for a deterministic algorithm to be secure, it must require every party's nonce to depend on every other nonce (because as long as anyone's nonce changes between two runs, yours must also - or you leak your private keys). You can't have k1=F(x1,m,k2*G) and simultaneously k2=F(x2,m,k1*G).
Pieter Wuille
CC BY-SA 4.0
2018-12-15T02:13:22.867Z
This circular dependency only appears of the nonce isn't provably deterministic. If everyone would be able to prove to everyone else that their nonce was computed from just their private key, the message, and everyone's public key, there wouldn't be a problem either. The circular dependency is only when one party could choose to use a different algorithm.
Pieter Wuille
<schnorr-signatures><musig>
Can R/r in Musig be derived from only seeds and message hashes?
Janus Troelsen
# Can R/r in Musig be derived from only seeds and message hashes?

(Asked by: username_0 on 2018-12-14)

I am wondering if the first two roundtrips of pre-committing and then revealing R/r in MuSig signing can be moved to the keygen phase and made deterministic. That reduces the amount of messages that need to be exchanged; since keygen is done only once, we want to expand that phase. This would be especially useful for HD wallets: at the expense of making wallet creation more complicated, signing would need fewer interactions.

The [musig paper](https://eprint.iacr.org/2018/068.pdf) on page 10-11, specifies the following (from perspective of signer 1):

## MuSig scheme

**Key generation**

1. generates private key x1 and corresponding public key X1
2. sends X1
3. receives Xi

**Signing (specifically the part about agreeing on Ri)**

1. sends t1=Hcom(R1)
2. receives ti
3. sends R1
4. receives Ri
5. checks that Hcom(Ri)==ti

r1 is specified to be random.
Signing includes three rounds of interaction, two of which is used for the above steps (agreeing on Ri).
I want to move these steps to the keygen phase.

---

A HD wallet would presumably use BIP32 to generate X1.
Can we use BIP32 for deriving Ri/ri too?

Consider the following scheme instead.
(from cosigners 1's perspective)

## Proposed HD scheme

**HD wallet setup phase**

1. generates xprv y1 and corresponding xpub Y1
2. generates xprv k1 and corresponding xpub K1
3. sends xpub Y1
4. sends u1=H(K1)
5. receives xpub Yi
6. receives ui
7. sends xpub K1
8. receives xpub Ki
9. checks that H(Ki)==ui

**Key generation**

1. from xprv y1 along some BIP32 path p, derive private key x1 and public key X1
2. from xpub Yi along same BIP32 path p, derive public key Xi
3. from xprv K1 along same BIP32 path p, derive private key j1 and public key J1
4. from xpub Ki along same BIP32 path p, derive public key Ji.

**Signing (specifically the part about agreeing on Ri)**

1. compute r1=j1+hash(m) and R1=J1+hash(m)\*G
2. compute Ri=Ji+hash(m)\*G

This approach only has one round of interaction during signing (sending si, omitted as its not changed from what is described in the paper).

I have read the derandomization section, but the explanation for why it doesn't work requires Ri to be chosen by the attacker. If we make it deterministically derived, and BIP32 is safe, then this attack does not apply. The paper states "each signer must ensure that whenever any Rj sent by other cosigners or the message m changes, his ri value changes unpredictably. As long as f is deterministic, this implies a circular dependency in the choice of random values."

Where is this circular dependency? The f from RFC 6979 only depends on key and m.

**Tags:** schnorr-signatures, musig

> **Comments:**
> **username_1**: I can't comment about the interaction with Musig, but I'll add my intuition here in a comment.  If by your design, the signature's nonce is chosen by the signer by way of *public* key derivation, and this is disclosed to another party who learns the public derivable path between private key and nonce, then they now have a function of the nonce as the public key.  This most likely will leak the private key when a valid signature over some message is published by the signer.  
> **username_2**: The circular dependency only appears when there are multiple parties. In order for a deterministic algorithm to be secure, it must require every party's nonce to depend on every other nonce (because as long as anyone's nonce changes between two runs, yours must also - or you leak your private keys). You can't have k1=F(x1,m,k2*G) and simultaneously k2=F(x2,m,k1*G).  
> **username_2**: This circular dependency only appears of the nonce isn't provably deterministic. If everyone would be able to prove to everyone else that their nonce was computed from just their private key, the message, and everyone's public key, there wouldn't be a problem either. The circular dependency is only when one party could choose to use a different algorithm.  

---

## 1 answers

### Answer by username_2 on 2018-12-15. Score: 5 | Accepted answer

The construction you're suggesting will likely work as long as you don't sign more than one message. By effectively choosing the R points ahead of time, you've constructed a single-show signature.

However, the derivation you're using for the different R values is pointless. It's not enough that you don't reuse R values; you can't use multiple *related* R values either. All the R values you are constructing are related through a single linear equation. That is sufficient for an attacker (who knows about the relation) to derive the private key from seeing two signatures.

> **Comments:**
> **username_3**: Technically linear relations can be okay so long as there are more unknowns than equations.  E.g. if you agree on a 3000 degree polynomial, you can use messages hashes to pick locations to interpolate, and make up to 2999 signatures.  But critically all of this stuff is SUPER hard to get right and super hard to verify. Most cryptographic constructions are broken.  I would really caution anyone against being too clever with this stuff.  

---

