---
# System prepended metadata

title: Threshold Signatures

---

## Introduction
A $(t-n)$ threshold signature protocol allows distributed signing among $n$ participants  such that any group of $t+1$ participants can produce a valid signature, while any group of fewer that $t$ participants cannot.

A threshold signature consists of two protocols **KeyGen**, **Sign** and an algorithm **Verify** as follow: 

**Keygen:** 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 secret key $sk_i$. In addition, all participants output a common public key $pk$. 

## Gennaro's Protocol
### Introduction
In this section we briefly describe the threshold ECDSA protocol of Gennaro etal in. This is the protocol that provide the best security and efficiency so far. As the title suggest, the protocol provide the following features:

### Technical Overview

### Actual Construction

For simplitity, we divide the **Sign** protocol into two sub protocols: **Presign** and **Sign** as the authors did in their paper.

**Public Parameter:**

**KeyGen:**
- Each $P_i$ sample $sk_i$ and sets $pk_i=g^{sk_i}$
- 
- The public key $pk$ is set to $pk=\prod_{i=1}^npk_i$

**Pre-sign:**
- Set $\delta=\sum_i\delta_i$, then check if $g^\delta=\prod_i\Delta_i$ and set $\rho=\Gamma^{\delta^{-1}}$.

**Sign($msg,\rho,\{\sigma_i\}_{i=1}^{t+1}$):** Used to product the final signature. Each $P_i$ do the following:
- **Round 1:**
--  Sample $k_i$ and $\gamma_i$ uniformly in $\mathbb{Z}_q$.
- **Round 3:**
--  Compute $\delta_i=\gamma_ik_i$
- **Round 4:**
-- Set $\sigma=\sum_{i}\sigma_i$ check if 
($\rho,\sigma$) is a valid signature using **Verify** alorithm.
-- Output $(\rho,\sigma)$.


**Verify($msg,(\rho,\sigma),pk$):** This is just the standard ECDSA verify algorithm. It works as follow: 

- Compute $m=\mathsf{H}(msg)$.
- Check $\rho=(g^m\cdot pk^{\rho})^{\sigma^{-1}}$.
## Our Intended Implementation
In this section, we are going to specify our intended implementation.  

First, we need to specify what curve are we going to use. Recall that the security lies in the discrete log assumption, hence it sufficies to choose any curve where the discrete log assumption is hard. The three most promising curves are **secp256k1**, **edd25519**

The protocol also require a hash function in step. We choose the **keccak** function as our hash function.