Security of MuSig in ROM

Theorem 1. Assume that there exists a  -forger  against the multi-signature scheme MuSig with group parameters  where  is  -bit long and hash functions  are modeled as random oracles. Then, there exists an algorithm  which  -solves the  problem for  with  where  is the time of an exponentiation in  and

Security Game of Multi-Signature Schemes

The security game involving an adversary (forger)  proceeds as follows:

• A key pair for the honest signer  KeyGen() is generated at random and the public key  is given as input to .
• The forger can engage arbitrary signing protocols with the honest user. Formally, it has access to a signature oracle which must be called on input a multiset of public keys  where  occurs at least once and a message . The oracle implements the signing algorithm corresponding to the honest user's secret key , while the forger plays the role of all other signers in  (potentially deviating from the protocol). Note that  might appear  times in  in which case the forger plays the role of  instances of , but since the signing algorithm only depends on the multiset  there is no need to specify which instances are associated with the honest oracle and the forger. The forger can interact concurrently with as many independent instances of the honest signature oracle as it wishes.
• At the end of its execution, the forger returns a multiset of public keys  a message  and a signature  The forger wins if  the forgery is valid, i.e.,  and  never initiated a signature protocol for multiset  and message .

In addition, if we work in the Random Oracle model, the adversary can make arbitrary random oracle queries at any stage of the game.

Let  KeyGen, Sign, Ver  be a multi-signature scheme. We say that an adversary  is a  -forger in the random oracle model against the multi-signature scheme  if it runs in time at most  initiates at most  signature protocols with the honest signer, makes at most  random oracle queries, and wins the above security game with probability at least  the size of  in any signature query and in the forgery being at most .

The Double-Forking Technique

Group parameters  are fixed and a key pair  is generated for the honest signer. The target public key  is given as input to the forger . Then, the forger can engage in protocol executions with the honest signer by providing a message  to sign and a multiset  of public keys involved in the signing process where  occurs at least once, and simulating all signers except one instance of . More concretely, it has access to an interactive signature oracle working as follows: the forger sends a multiset  of public keys with  (we assume the oracle returns  if and a message  to sign; the signature oracle parses  as  draws a random  computes  and sends  to the forger which sends back commitments  the signature oracle then sends  to the forger which answers with  the signature oracle aborts the protocol if  for some  otherwise it computes

and returns  to the forger.

Note that the remaining steps of the protocol, where  sends  to the signature oracle which outputs  can be omitted since the signature oracle's behavior does not depend on  and can be perfectly simulated by the forger.

The crux of the proof is how to extract the discrete logarithm  of the challenge public key . The standard technique for this would be to "fork" two executions of the forger in order to obtain two valid forgeries  and  for the same multiset of public keys  with  and the same message  such that  was programmed in both executions to the same value  was programmed in both executions to the same value  for each  such that  and  was programmed to two distinct values  and  in the two executions, implying that

where  is the number of times  appears in  This would allow to compute the discrete logarithm of  by dividing the two equations above.

However, simply forking the executions with respect to the answer to the query  does not work: indeed, at this moment, the relevant query  might not have been made yet by the forger, and there is no guarantee that the forger will ever make this same query again in the second execution, let alone return a forgery corresponding to the same  query. In fact, it is easy to see that the forger can only guess the value of the aggregated public key  corresponding to  at random before making the relevant queries  for  so that the query  can only come after the relevant queries  except with negligible probability.

In order to remedy this situation, we fork the execution of the forger twice: once on the answer to the query  which allows us to retrieve the discrete logarithm of the aggregated public key with respect to which the adversary returns a forgery, and then on the answer to  which allows us to retrieve the discrete logarithm of .

Lemma 1: The Generalized Forking Lemma

• Deals with the outputs of an algorithm  run twice on related inputs.

Fix integers  and  Let  be a randomized algorithm which takes as input some main input  and  -bit strings  and returns either a distinguished failure symbol  or a pair  out  where  and out is some side output. The accepting probability of denoted  is defined as the probability, over the random draw of  (according to some well-understood distribution),  and the random coins of  that returns a non- output. Consider algorithm  taking as input . Let frk be the probability (over the draw of inp and the random coins of  ) that  returns a non-  output. Then

Security Proof

We first construct a "wrapping" algorithm  which essentially runs the forger, simulating and  uniformly at random and the signature oracle by programming , and returns a forgery together with some information about the forger execution, unless some bad events happen.

In particular, we must exclude the case where the adversary is able to find two distinct multisets of public keys  and  such that the corresponding aggregated public keys are equal, since when this happens the forger can make a signature query for  and return the resulting signature  as a forgery for . Jumping ahead, this will correspond to bad event KeyColl defined in the proof of Lemma 2 .

Then,we use  to construct an algorithm  which runs the forking algorithm  a (where the fork is w.r.t. the answer to the  query related to the forgery), allowing him to return a multiset of public keys  together with the discrete logarithm of the corresponding aggregated public key.

Finally, we use  to construct an algorithm  solving the DL problem by running  (where the fork is now w.r.t. the answer to the  query related to the forgery)

Lemma 2

Assume that there exists a  -forger  in the random oracle model against the multi-signature scheme MuSig with group parameters  and let  Then, there exists an algorithm  that takes as input a uniformly random group element  and uniformly random  -bit strings  and  and, with accepting probability at least

outputs  where  is a multiset of public keys such that  is a tuple of  -bit values such that  for any  such that and

Strings  resp.  will be used to answers queries to  resp.  We need  answers for each random oracle because one query to  and one query to  may be incurred by each signature query and by the final verification of the validity of the forgery.

:

We construct algorithm  as follows. It initializes three empty tables  and  for storing programmed values for respectively , and  and two counters ctr and ctr (initially zero) that will be incremented respectively each time an entry of the form  is assigned and each time an assignment is made in . It also initializes six flags BadCom, BadProg, BadOrder, and KeyColl (that will help keep track of bad events) and a special flag Alert to false. Then, it picks random coins  and runs the forger  on input the public key , answering its queries as follows.

• Hash query  If  is undefined, then  randomly assigns  then, it returns 

• Hash query  Recall that by assumption  and  If  is undefined,  increments ctr, assigns  and randomly assigns  for all  Then, it returns 

• Hash query  If  is undefined, then  increments  and assigns , Then, it returns 

• Signature query  If  then  returns  to the forger. Otherwise, it parses  as  If  is undefined, it makes an "internal" query to which ensures that  is defined for each  sets  and computes 

• Then,  increases  lets  draws  and computes . If  is already defined, it sets BadCom true and halts returning  Otherwise,  makes an internal query to  and sends  to the forger. Upon reception of commitments  from the forger,  looks for values  such that  for  Three cases may occur:
1. If more than one such value can be found for some  then  sets BadComtrue and halts returning .
2. If no such value can be found for some  then  sets Alert  true and sends to the forger.
3. If exactly one such value exists for each  then  computes  If  has already been defined, then  sets BadProg := true and halts returning Otherwise, it assigns  and sends  to the forger.

Upon reception of  from the forger,  checks that  for all (making internal call(s) to  if we were in case 2 above) and aborts the signature protocol if this is not the case. (Note that  does not halt returning  in this case since this is just the expected behavior of the honest signer.) If Alert  true and  for all  then  sets BadCom true and halts returning  Otherwise,  sends  to the forger, completing the simulation of the honest signature oracle.

If  returns  outputs  as well. Otherwise, the forger returns a purported forgery  for a public key multiset  such that  and a message . Then,  parses  as  and checks the validity of the forgery as follows. If  is undefined, it makes an internal query to  which ensures that  is defined for each  sets  and computes  If  is undefined, it makes an internal query to  and lets  If  i.e., the forgery is invalid,  outputs  otherwise it takes the following additional steps. Let  be the index such that  and  be the index such that  If the assignment  occurred after the assignment  sets BadOrder : = true and returns . If there exists another multiset of public keys  such that, at the end of the execution,  is defined for each  and the aggregated keys corresponding to  and  are equal,  sets KeyColl  true and returns Otherwise, it returns  where  By construction,  for each such that  and the validity of the forgery implies

Lemma 3

Assume that there exists a  -forger  in the random oracle model against the multi-signature scheme MuSig with group parameters  and let  Then, there exists an algorithm  that takes as input a uniformly random group element  and uniformly random  -bit strings  and, with accepting probability at least

outputs a tuple  where  is a multiset of public keys such that  is a tuple of  -bit values such that  for any  such that and  is the discrete logarithm of  in base 

: Algorithm  runs  with  as defined in Lemma 2 and takes a few additional steps described below. The mapping with notation of Lemma 1 is as follows:

•  and  play the role of inp,
•  play the role of 
•  plays the role of 
•  plays the role of out.

In more details,  picks random coins  and runs algorithm  on coins  group element  and  -bit strings  and  where  are drawn uniformly at random by (recall that  are part of the input of  and will be the same in both runs of . If  returns  returns  as well. Otherwise,  returns a tuple  where  and  Then,  runs  again with the same random coins on input  and  where 

are uniformly random. If  returns  in this second run,  returns  as well. If  returns another tuple  where  and   proceeds as follows. Let  and  denote the aggregated public keys corresponding to the two forgeries. If  or  and  then  returns  Otherwise, if  and , we will prove shortly that necessarily

which implies in particular that  By Lemma  the two outputs returned by  are such that

which allows  to compute the discrete logarithm of  as

Then  returns .

It is easy to see that  returns a non-  output iff  does, so that by Lemma 1 and Lemma  and letting