2
$\begingroup$

Background

MuSig is an extension of/derivation from Schnorr signatures using cyclic groups on elliptic curves. In the original paper, the authors point out that naive multi-Schnorr is vulnerable to a rogue key attack:

Given $\Bbb G$ is a cyclic group of prime order; $g$ is the generator point; $H$ is a hash function; $m$ is the message to sign; and there are $n$ participants:

Let $L = \{ X_1 = g^{x_1},..., X_n = g^{x_n} \}$ be the multiset of participant keys.

Let each nonce share be $R_i = g^{r_i}$.

Compute the aggregate nonce: $R = \prod_{i=1}^nR_i$

Compute the aggregate key: $\tilde X = \prod_{i=1}^nX_i$

Compute the challenge: $c = H(\tilde X, R, m)$

Compute each partial signature: $s_i = r_i + cx_i$

Compute the aggregate signature: $s = \sum_{i=1}^ns_i$

The signature for aggregate key $\tilde X$ and message $m$ is now $(R, s)$ and can be verified: $g^s = R\tilde X^c$

If one participant is a bad actor and waits to gather all other participant keys before sending his own, he can compute a key pair that allows him to sign for the group by inverting the partial product: $X_1 = g^{x_1} * {(\prod_{i=2}^nX_i)}^{-1}$

The primary contribution of the MuSig paper is a scheme that prevents the rogue key attack by transforming each participant key after key exchange in a way that allows for key aggregation in the plain public-key model:

Let $\langle L \rangle$ be a deterministic ordering of $L$.

Let $a_i = H(\langle L \rangle, X_i)$

Compute $\tilde X = \prod_{i=1}^n{X_i}^{a_i}$

One well-known problem with exchanging nonces is that under concurrent sessions with pre-shared nonces, an attacker can use Wagner's generalized birthday attack to bias the hash output and thus efficiently forge a signature. The solution to this problem is to have all participants commit to a nonce value and pre-share the commitment rather than the nonce; when the time comes to create a group signature, nonces are exchanged, and the protocol aborts if a received nonce does not map to a commitment.

Question

Can the rogue key attack be solved by committing to a public key before exchanging those keys? This would allow all participants to detect if any other participant is attempting to manipulate his public key to allow single signatures for the group. The session could then be discarded and the fraudulent aggregate key ignored.

Is this adequate to mitigate the rogue key attack, or does it lack security assurances in certain circumstances?

$\endgroup$
2
  • $\begingroup$ It's difficult to read large code blocks for things that aren't code. This site also supports $\LaTeX$ markup. Could you edit your question to make it more readable? $\endgroup$ Aug 31 at 17:14
  • $\begingroup$ @AmanGrewal I was unaware of latex markup and was wondering how other posts accomplished it. I will update posthaste. $\endgroup$ Aug 31 at 18:21

Your Answer

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

Browse other questions tagged or ask your own question.