## Definition and Security

In this section, we describe the syntax and security properties of a threshold signature scheme.

### Definition

We describe the syntax of a threshold signature scheme. A $$(n,t)$$ threshold signature consists of two interactive protocols KeyGen, Sign and an algorithm Verify as follows:

Keygen $$(1^\lambda)\langle \{P_i\}_{i=1}^n\rangle$$: This is an interactive protocol between $$n$$ participants $$P_1,P_2,\dots,P_n$$. If the interaction suceeds, each participant $$P_i$$ receives a partial secret key $$sk_i$$. In addition, all participants output a common public key $$pk$$.

Sign$$(M,\mathcal{S})\langle \{P_i(sk_i)\}_{i \in \mathcal{S}}\rangle$$: This is an interactive protocol with common input $$M$$ between a set $$\mathcal{S}$$ of $$t+1$$ participants $$\{P_i\}_{i \in \mathcal{S}}$$, where each participant $$P_i$$ holds a partial secret key $$sk_i$$ only known to him. If the interaction suceeds, the protocol outputs a signature $$\sigma$$.

Verify$$(M,\sigma,pk)$$: This is an algorithm run by an external verifier to check the correctness of the signature. On input a message $$M$$, a signature $$\sigma$$, a common public key $$pk$$, it outputs a bit $$b$$ indicating the validity of the signature.

### Security Properties

A threshold signature scheme should satisfy the following properties:

Correctness: For any set $$\mathcal{S} \subset \{1,\dots,n\}$$ with $$|\mathcal{S}|=t+1$$, if $$P_i$$ follows the protocol for all $$i \in \mathcal{S}$$ and $$\sigma \leftarrow$$ Sign$$(M,\mathcal{S})\langle \{P_i(sk_i)\}_{i \in \mathcal{S}}\rangle$$, then it holds that Verify$$((M,\sigma,pk)=1$$.

Unforgability: A $$(t-n)$$ threshold signature scheme is unforgeable if for any adversary $$\mathcal{A}$$ who corrupts up to $$t$$ participants and given previous signatures $$\sigma_1,\dots,\sigma_k$$ of previous messages $$M_1,\dots,M_k$$, the probability that $$\mathcal{A}$$ can produce a signature $$\sigma$$ on an unsigned message $$M$$ such that Verify$$((M,\sigma,pk)=1$$ is negligible.