1

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

  • 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 Dec 14 '18 at 20:09
  • 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 Dec 15 '18 at 2:08
  • 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 Dec 15 '18 at 2:13
4

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.

  • 2
    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 Dec 16 '18 at 10:21

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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