[](https://)---reuf
tags: research

---

# Multi-sigs against BLS signatures

For simplicity , a multi-signature scheme MS = (Pg, Kg, Sign , Vf) consists of

- Parameter generation (system wide , runs by central authority , does it have to ?)
- Key generation (Kg -> (pk,sk) , non-interactive process)
- Signing
- Verification ( ($L={pk_1...pk_n}$, m ,$\sigma$) -> 1)

## Operational Assumptions
- key verification model
asks the MS verifiers to verify the proof of possession or proof of well-definedness of public keys , as a variant of POP model .
- knowledge of secret key (KOSK)
asks a user to provide its private key in order for its public key to get certified or follow a interactive pre-processing protocol.
- proof of possession model
asks a user to show a proof of possesion of private key or to pass a certain registration procedure when registering its public key at CA(authority).

- plain public-key model
CA only signs the public keys , does not have to prove any well-definedness of public keys.

Below we use Asp_i to imply the ith assumption .

## Non-interactive musig with preprocessing
In the settings of non-interactive multisignatures , each signer only contributes a single partial signature without interacting with each other. Individual signers can prepare their partial signatures off-line and independently.

## Multisignatures schemes
Formally a multi-signature scheme consists of four algorithms , i.e. MS = (Pg,Kg,Sign,Vf). Note that a non-interactive process can be performed by any party at any given time.

In terms of the system-wide parameters , a central authority (trusted party) runs the parameter generation algorithm $Pg$ to generate global paramters $par$ , i.e. (G,p,g) where p as prime order of cyclic group G, $g←G$.Each signer independently generates its own public and private key pair via $(pk,sk)←Kg(pr)$. We call the two-step process the $Setup$.

Conceptually we describe the non-interactive multi-signature as follows:

$Setup(1^{\lambda})$ : This is a randomized algorithms such that security parameter $\lambda$ as input and produces global public parameter $par$. (In the context of non-interactive musig , $par$ can be viewed as a common reference string)

$Gen(par)$ : take as input of $par$ , outputs signer i's private/public key pair $(sk_i,pk_i)$.

$Sign(par, {sk_i}, M , L)$ : given $par$, message $M$ and set of public key $L= (pk_1,...,pk_l)$ . And broadcasts $\sigma_i=H_m(M||L)^{c_i*x_i}$ where $c_i := H(pk_i||L)$. Given partial signatures $\sigma_1,...,\sigma_l$ , anyone can compute the multisignature without coorperating with other cosigners .

$Vf(par,M,\sigma,L)$ : given all paramters above, this deterministic algorithm outputs 0(reject) or 1(accept). Moreover for the aggregated signature $\sigma$ , we explore the non-interactive aggregation(i.e. general aggregated signatures) process below.

### General aggregate signatures
In a general signature aggregation scheme , each user $i$ signs messages $M_i$ to obtain signature $\sigma_i$ . Anyone is able to use a public aggregation algorithm to take the set of signatures $\sigma_1,...,\sigma_n$ in order to compress them into a single signature $\sigma$.This can be done by any party and without the cooperation of the signers , which in other words provides non-interactivity.