DLOG ⇒ MuSig

Fully-black-box reduction · random oracle model · MPSW19

Statement

MuSig is the three-round Schnorr multi-signature with key aggregation. Each signer computes $a_i=H_{\mathrm{agg}}(L,X_i)$ and $\tilde{X}={\prod }_i{X}_i^{a_i}$, the signers run a commitment round on their nonces $R_i$, and with $R={\prod }_i{R}_i$ and $c=H_{\mathrm{sig}}(\tilde{X},R,m)$ each signer replies $s_i=r_i+c{a}_i{x}_i$. The scheme is unforgeable in the plain public-key model in the random-oracle model if DLOG is hard in the group — MPSW19.

Notes

• A MuSig signature $(R,{\sum }_i{s}_i)$ verifies as a Schnorr signature under the aggregate key $\tilde{X}$, with the key included in the hash — MPSW19.
• Without the commitment round (two-round MuSig), no algebraic reduction proves the scheme secure under DLOG or OMDL if OMDL is hard (barrier) — DEF+19. MuSig2 restores two rounds with several nonces per signer, under OMDL (OMDL ⇒ MuSig2) — NRS21.