Multi-signature

A multi-signature scheme lets $n$ signers, each holding its own key pair, jointly produce one short signature on a message that verifies against their set of public keys, or, with key aggregation, against a single aggregate public key.

Syntax

A multi-signature scheme with key aggregation is a tuple $(\mathsf{Setup},\mathsf{KeyGen},\mathsf{KeyAgg},\mathsf{Sign},\mathsf{Vrfy})$:

• $\mathsf{Setup}(1^{\lambda })\to \mathsf{pp}$, public parameters (a group and hash functions),
• $\mathsf{KeyGen}(\mathsf{pp})\to (\mathsf{sk},\mathsf{pk})$, run independently by each signer,
• $\mathsf{KeyAgg}(L)\to \tilde{X}$, a deterministic algorithm mapping a multiset $L=\{{\mathsf{pk}}_1,\dots ,{\mathsf{pk}}_n\}$ of public keys to an aggregate key,
• $\mathsf{Sign}$, an interactive protocol among the $n$ signers, signer $i$ on input $({\mathsf{sk}}_i,L,m)$, at the end of which each outputs a signature $\sigma$,
• $\mathsf{Vrfy}(\tilde{X},m,\sigma )\to b$, a deterministic algorithm outputting a bit $b\in \{0,1\}$.

Properties

Correctness

The scheme is perfectly correct if whenever every signer runs $\mathsf{Sign}$ honestly on $({\mathsf{sk}}_i,L,m)$, the output $\sigma$ satisfies $\mathsf{Vrfy}(\mathsf{KeyAgg}(L),m,\sigma )=1$.

Unforgeability in the plain public-key model

There is one honest signer. The adversary chooses every other public key, with no proof that it knows the matching secret key, plays all other signers in signing sessions with the honest signer that it may interleave arbitrarily, and wins by outputting a valid signature, for a multiset of keys containing the honest key, on a message on which it never opened a signing session with the honest signer — MPSW19. Excluding only the pair of multiset and message would give a stronger notion, which BLS-based multi-signatures do not meet: in Boldyreva’s scheme the honest share $H(m{)}^{{\mathsf{sk}}^{\ast }}$ does not depend on the multiset, so a share obtained for one multiset completes a signature on $m$ for another — standard.

\begin{algorithm}
\algname{Game}
\caption{$\Game^{\text{ms-uf}}_{\Pi,\calA}(\secpar)$}
\begin{algorithmic}
\State $\pp \gets \Setup(1^\secpar)$ ; $(\sk^*, \pk^*) \gets \KeyGen(\pp)$ ; $\calQ \gets \{\}$
\State $(L^*, m^*, \sigma^*) \gets \calA^{\calO_{\Sign}}(1^\secpar, \pp, \pk^*)$
\If{$\pk^* \notin L^*$ or $m^* \in \calQ$}
\Return $0$
\EndIf
\Return $[\Vrfy(\KeyAgg(L^*), m^*, \sigma^*)]$
\end{algorithmic}
\end{algorithm}

\begin{algorithm}
\algname{Oracle}
\caption{$\calO_{\Sign}(j, L, m, M)$}
\begin{algorithmic}
\If{session $j$ is new and $\pk^* \in L$}
\State $\calQ \gets \calQ \cup \{m\}$
\State start the honest signer on $(\sk^*, L, m)$ as session $j$
\EndIf
\State feed $M$ to session $j$; let $M'$ be its next message
\Return $M'$
\end{algorithmic}
\end{algorithm}

The scheme is unforgeable if for all efficient $\mathcal{A}$,

$${\mathbf{Adv}}_{\Pi ,\mathcal{A}}^{\text{ms-uf}}(\lambda ):=\mathrm{Pr}\left[{\mathbf{G}}_{\Pi ,\mathcal{A}}^{\text{ms-uf}}(\lambda )=1\right]$$

is negligible.

Knowledge-of-secret-key model

Unforgeability as in the plain public-key model, except that the adversary may use a public key other than ${\mathsf{pk}}^{\ast }$, in a signing session or in its output, only after registering it with the coins of $\mathsf{KeyGen}$ that produce it, so that the challenger knows the matching secret key. The requirement that every adversarial key be registered together with its secret key is the knowledge-of-secret-key (KOSK) assumption of RY07, under which Bol03 proves its multisignature secure.

\begin{algorithm}
\algname{Game}
\caption{$\Game^{\text{ms-kosk}}_{\Pi,\calA}(\secpar)$}
\begin{algorithmic}
\State $\pp \gets \Setup(1^\secpar)$ ; $(\sk^*, \pk^*) \gets \KeyGen(\pp)$ ; $\calQ \gets \{\}$ ; $\calR \gets \{\pk^*\}$
\State $(L^*, m^*, \sigma^*) \gets \calA^{\calO_{\Sign}, \calO_{\mathrm{Reg}}}(1^\secpar, \pp, \pk^*)$
\Comment{$\calO_{\Sign}$ as in the plain game, on key multisets $L \subseteq \calR$ only}
\If{$\pk^* \notin L^*$ or $L^* \not\subseteq \calR$ or $m^* \in \calQ$}
\Return $0$
\EndIf
\Return $[\Vrfy(\KeyAgg(L^*), m^*, \sigma^*)]$
\end{algorithmic}
\end{algorithm}

\begin{algorithm}
\algname{Oracle}
\caption{$\calO_{\mathrm{Reg}}(\rho)$}
\begin{algorithmic}
\State $(\sk, \pk) \gets \KeyGen(\pp; \rho)$
\State $\calR \gets \calR \cup \{\pk\}$
\Return $\pk$
\end{algorithmic}
\end{algorithm}

The scheme is unforgeable in the KOSK model if for all efficient $\mathcal{A}$, ${\mathbf{Adv}}_{\Pi ,\mathcal{A}}^{\text{ms-kosk}}(\lambda ):=\mathrm{Pr}\left[{\mathbf{G}}_{\Pi ,\mathcal{A}}^{\text{ms-kosk}}(\lambda )=1\right]$ is negligible.

Proof-of-possession model

The scheme has two further algorithms, $\mathsf{PopProve}(\mathsf{pp},\mathsf{sk},\mathsf{pk})\to \pi$ and a deterministic $\mathsf{PopVrfy}(\mathsf{pp},\mathsf{pk},\pi )\to b$, with $\mathsf{PopVrfy}(\mathsf{pp},\mathsf{pk},\mathsf{PopProve}(\mathsf{pp},\mathsf{sk},\mathsf{pk}))=1$ for every key pair $\mathsf{KeyGen}$ outputs. Unforgeability is as in the KOSK game, except that the adversary also receives ${\pi }^{\ast }\leftarrow \mathsf{PopProve}(\mathsf{pp},{\mathsf{sk}}^{\ast },{\mathsf{pk}}^{\ast })$ and registers a key by presenting a proof of possession (POP) for it, which the challenger checks with $\mathsf{PopVrfy}$. This is the registered-key model of RY07 instantiated with a POP.

\begin{algorithm}
\algname{Oracle}
\caption{$\calO_{\mathrm{Reg}}(\pk, \pi)$}
\begin{algorithmic}
\If{$\PopVrfy(\pp, \pk, \pi) = 1$}
\State $\calR \gets \calR \cup \{\pk\}$
\EndIf
\end{algorithmic}
\end{algorithm}

The scheme is unforgeable in the POP model if for all efficient $\mathcal{A}$, the probability that it wins this game is negligible.

Variations

The schemes below work in a group of prime order $p$ with generator $g$, with signer $i$ holding $(x_i,X_i=g^{x_i})$, and hash functions $H_{\mathrm{agg}},H_{\mathrm{com}},H_{\mathrm{non}},H_{\mathrm{sig}}$ modeled as random oracles. Each aggregates keys as $a_i=H_{\mathrm{agg}}(L,X_i)$ and $\mathsf{KeyAgg}(L)=\tilde{X}={\prod }_i{X}_i^{a_i}$, and outputs $\sigma =(R,s)$ that verifies as a Schnorr signature under $\tilde{X}$ with the key included in the hash: $g^s=R{\tilde{X}}^c$ with $c=H_{\mathrm{sig}}(\tilde{X},R,m)$.

MuSig

Signing takes three rounds. Signer $i$ samples $r_i\stackrel{\$}{\leftarrow }{\mathbb{Z}}_p$, sets $R_i=g^{r_i}$, and sends $t_i=H_{\mathrm{com}}(R_i)$; once all commitments have arrived, it sends $R_i$ and checks every $R_j$ against $t_j$; with $R={\prod }_i{R}_i$ and $c=H_{\mathrm{sig}}(\tilde{X},R,m)$ it sends $s_i=r_i+c{a}_i{x}_i\mathrm{mod}p$, and $s={\sum }_i{s}_i$ — MPSW19.

Two-round MuSig

MuSig without the commitment round: signer $i$ sends $R_i$ directly and then $s_i$, as first proposed in the preprint version of MPSW19; its security proof is flawed — DEF+19.

MuSig2

Signing takes two rounds, and the first can run before the message is known. Signer $i$ samples $r_{i,1},\dots ,r_{i,\nu }\stackrel{\$}{\leftarrow }{\mathbb{Z}}_p$ and sends $R_{i,j}=g^{r_{i,j}}$ for $j\in [\nu ]$. With $R_j={\prod }_i{R}_{i,j}$, $b=H_{\mathrm{non}}(\tilde{X},(R_1,\dots ,R_{\nu }),m)$, $R={\prod }_j{R}_j^{b^{j-1}}$ and $c=H_{\mathrm{sig}}(\tilde{X},R,m)$, it sends $s_i={\sum }_j{r}_{i,j}{b}^{j-1}+c{a}_i{x}_i\mathrm{mod}p$, and $s={\sum }_i{s}_i$ — NRS21. With $\nu =1$ this is two-round MuSig. The scheme is proved secure in the random-oracle model with $\nu =4$, and in the combination of the algebraic group model and the random-oracle model with $\nu =2$ — NRS21. As an object, MuSig2 denotes the scheme with $\nu =4$.

Participates in

Builds on Multi-signature

• Multi-signatures with proofs of possession ⇒ Multi-signatures in the KOSK model (via Proof-of-possession model)
• Multi-signatures in the plain public-key model ⇒ Multi-signatures in the KOSK model

Produces Multi-signature

• co-CDH ⇒ BLS multi-signatures with public-key aggregation
• Multi-signatures with proofs of possession ⇒ Multi-signatures in the KOSK model (via Knowledge-of-secret-key model)
• Multi-signatures in the plain public-key model ⇒ Multi-signatures in the KOSK model (via Knowledge-of-secret-key model)
• OMDL ⇒ MuSig2 (via MuSig2)
• DLOG ⇒ MuSig (via MuSig)
• Type 1 pairing + CDH ⇒ Multi-signatures in the KOSK model (Boldyreva) (via Knowledge-of-secret-key model)
• Type 1 pairing + CDH ⇒ Multi-signatures with proofs of possession (via Proof-of-possession model)

Barriers

• No algebraic reduction from OMDL to two-round MuSig (via Two-round MuSig)