Threshold Signature

In this chapter, we give an overview of threshold signatures and describe the threshold ECDSA construction of Canetti et al in CGGMP21 and the FROST threshold signature scheme in KG20, which is a threshold version of Schnorr signature scheme, including its EdDSA (or ed25519) instatiation. The chapter is separated into $5$ major parts below:

• First, we give a brief introduction to threshold signatures and state its syntax and security properties in Introduction.

• Second, we state the syntax and security properties of threshold signatures in Definition and Security.

• Third, we describe the threshold ECDSA construction of CGGMP21 in Canetti's Construction to support the threshold ECDSA version for the curve secp256k1.

• Fourth, we describe the FROST threshold signature construction of KG20 in FROST Construction to support the threshold signature version of ed25519 and sr25519.

• Finally, we briefly specify our instatiation and analyse the security for the threshold ECDSA construction of Canetti et al using secp256k1 parameters and FROST threshold signature construction using ed25519 and sr25519 parameters as follows:

  • In Threhold signature for secp256k1, we discuss and analyse the security of the threshold ECDSA signature of Canneti et al. when instatiated using the parameters of secp256k1.

  • In Threhold signature for ed25519 we discuss and analyse the security of the FROST threshold signature when instatiated using the parameters of ed25519.

  • In Threhold signature for sr25519 we discuss and analyse the security of the FROST threshold signature when instatiated using the parameters of sr25519.

Author(s): phamnhatminh1292001

Introduction

A $(n,t)$ 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. The goal is to produce signatures that are compatible with an existing centralized signature scheme so that we can verify the signatures without any modification in the existing digital signature algorithms. Compared to an ordinary signature scheme, the setup and signing algorithms are replaced by interactive protocol between participants, while the verification algorithm remains identical to the verification of a signature issued by a centralized party.

With the advance of blockchain technology, threshold signature has received increasing attention from the community. This is because transactions in blockchain are made possible via digital signatures, and it is dangerous to trust the whole signing process in a single individual, who might be compromised, leading to single point of failure. Hence many stakeholders are looking to perform signature generation in a distributed way. In a threshold signature scheme, an adversary cannot learn the actual secret key if it does not control enough number of participants, and any $t+1$ participants will be able to deliver a valid signature, hence preventing the "single point of failure" attack above.

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.

Canneti et al's Construction

In this section we briefly describe the threshold ECDSA protocol of Canneti etal in CGGMP21, in which we assume that the readers have some familiarity to ECDSA signature scheme. Recall that the ordinary ECDSA signature scheme $\sigma=(r,s)$ of a message $M$ is generated as follow

$r=R.\mathsf{x},\ R=g^{k^{-1}},\ m=\mathsf{H}(M)\ \text{and}\ s=k(m+r\cdot sk),$

where $k \leftarrow \mathbb{Z}_p$ and $sk$ is the signer's secret key. Canneti's protocol aims to provide a valid ECDSA signature of $M$ above via a threshold manner. In addition, the protocol also provide the following features:

• Universal Composable Security: Canneti etal's protocol achieve security in the Universal Composable Security framework. The framework is better in realizing the security of protocol, compared to traditional game based definitions.

• Proactive Key Refresh: Canneti etal's protocol allow participants to refresh their partial secret keys after every epoch while not changing the grand secret key and public key. The goal of key refresh is to achieve security against proactive adversaries, who might corrupt participants for a certain period of time during the execution of the protocol.

• Non Interactive online phase: Canneti etal's protocol achieves non-interactive in the following sense: The signing protocol consists of a preprocessing phase before the message $M$ is known, followed by a non-interactive signing phase, where each participant can generate his own signature of $M$ using the preprocessed information.

• Identifiable Abort: The protocol contains additional mechanisms that allow participants to detect any signers who fail to participate in the signing process, or deviate from it. Identifying misbehaving signers can be crucial for some applications. In most applications, being able to identify rogue servers is a convenience, allowing reboot the whole system.

To see how the protocol achieve the abovementioned properties, we now move to the actual construction of Canneti and describe it.

Key Generation

In this section, we describe the key generation process in the construction of Canetti et al. The key generation process is divided into two sub protocols: the initial key generation process and the key refresh process. The initial key generation process is executed exactly once to produce a public-secret key pair $pk,sk$, while the key refresh process is executed whenever participants would like to change their partial secret keys in the way that $pk$ and $sk$ remains the same. Before moving to the protocol, we provide several notations that will be used in the protocol description below.

Notation: Let $\lambda$ to be the security parameter. Let $\mathbb{G}$ to be a cyclic group whose order is a prime number. Let $p \in (2^{\lambda-1},2^\lambda)$ to be the order of $\mathbb{G}$ and let $g,h$ to be two generators of $\mathbb{G}$. We denote $\mathsf{Com}$ to be a secure binding and information theoretic hiding commitment scheme and $\mathsf{H}$ to be a cryptographic hash function. For any set $\mathcal{S}$ and for any $i \in \mathcal{S}$ we denote $\lambda_{i,S}=\prod_{j\in \mathcal{S},j \neq i}\dfrac{j}{j-i}$ to be the Lagrange coefficient w.r.t $S$.

Now, the initial key generation and key-refresh process are as follows:

Keygen $(1^\lambda)\langle \{P_i\}_{i=1}^n\rangle$:

Initial Key Generation: The initial key generation is executed once at the beginning.

1. Each participant $P_i$ selects $s_i \in Z_p$ and compute $C_i=\mathsf{Com}(g^{s_i})$.

2. Each participant $P_i$ broadcasts $y_i=g^{s_i}$. The public key $pk$ is set to be $pk=\prod_{i=1}^ny_i$. $P_i$ then performs Feldman's Verifiable Secret Sharing scheme (see Supporting Protocols) to share $s_i$ to other participants. Each $P_j$ add the secret shares received as his secret key, i.e, $sk_j=\sum_i s_{ij}$. The values $sk_i$ are the shares of a $(t-n)$ Shamir secret sharing of the secret key $sk$.

3. Finally, each participant uses Schnorr's protocol S91 (see Supporting Protocols) to prove in zero knowledge that he knows the secret key $sk_i$,

Key Refresh: The key refreshment process is executed after a certain number of epochs whenever participants have to reset their partial secret keys.

1. Each participant $P_i$ samples $E_i=(N_i,h_{i1},h_{i2})$, the public key of Pallier Cryptosystem P91 satisfying $N_i>2^{8\lambda}$.

2. Each participant $P_i$ performs Feldman's Verifiable Secret Sharing scheme to distribute the shares $s_{ij}'$ of $0$ to other participants. Each participant $P_i$ set his new secret key to be $sk_i'=sk_i+\sum_i s_{ji}'$. The secret key $sk$ remains the same and are unknown to other participants and the values $sk_i'$ are still the shares of a $(t-n)$ Shamir secret sharing of the secret key $sk$

3. Finally, each participant does the following:

   1. Use Schnorr's protocol to prove in zero knowledge that he knows the new secret key $sk_i'$.

   2. Prove that $N_i$ is a product of two primes $p_i,q_i$ s.t $p_i \equiv q_i \equiv 3 \pmod {4}$ and $N_i$ admits no small factors (see Supporting Protocols)

   3. Prove that $(h_{i1},h_{i2})$ generates the same multiplicative group modulo $N_i$ using Schnorr protocol for Ring (see Supporting Protocols).

By the property of Feldman's VSS, it can be proven that the public key $pk$ is also equal to $g^{sk}$, hence the key pair $(pk,sk)$ generated using the key generation protocol above has the same form of a key pair in an ECDSA signature scheme.

Note: Note that after the key generation process, we see that each $P_i$ is now equipped with a Pallier encryption scheme with public key $E_i=(N_i,h_{i1},h_{i2})$, which we denote the encryption and decryption algorithm by $\mathsf{Enc}_i$ and $\mathsf{Dec}_i$ respectively. The encryption algorithm receives two inputs: the message $M$ and a randomness $\rho$. In most cases, for simplicity we will ignore the input randomness $\rho$ in our description. The encryption scheme will be used in the signing process.

Signing

In this section, we describe the signing process of the protocol. For any set $S \in \{1,\dots,n\}$ of $t+1$ participants who participate to sign a message $M$, let $w_i=\lambda_{i,S}\cdot sk_i \pmod{p}$. Note that by Feldman's VSS, $sk=\sum_{i \in S} w_i$. Note that since $pk_i=g^{sk_i}$ is public after the key generation process, hence the value $W_i=g^{w_i}=pk_i^{\lambda_{i,\mathcal{S}}}$ can also be publicly computed. The signing protocol follows a $6$ steps process below:

Sign$(M)\langle \{P_i(sk_i)\}_{i=1}^n\rangle$:

1. Each participant $P_i$ choose $k_i,\gamma_i \in \mathbb{Z}_p$ and does the following:

   1. Compute $K_i=\mathsf{Enc}_i(k_i), G_i=\mathsf{Enc}_i(\gamma_i)$

   2. Compute a proof $\pi_i$ certifying $k_i \in [1,2^{3\lambda}]$ (see Supporting Protocols).

   3. Send $(K_i,G_i,\pi_i)$ to all participants.

Define $k=\sum_i k_i$ and $\gamma=\sum_i \gamma_i$. We see that $k\gamma=\sum _{i,j} k_i \gamma_j \pmod{p}$ and $k\cdot sk=\sum _{i,j} k_i w_j \pmod{p}$.

2. For each $j \neq i$, each participant $P_i$ does the following:

   1. Verify the validity of $\pi_j$. If any check fails, the protocol aborts.

   2. Sample $\beta_{ij},v_{ij} \in [1,\dots,2^{7\lambda}]$

   3. Comute $C_{ji}=\mathsf{Enc_j}(\gamma_ik_j-\beta_{ij})=\gamma_i\cdot K_j-\mathsf{Enc_j}(\beta_{ij})$ and $C_{ji}'=\mathsf{Enc_j}(w_ik_j-v_{ij})=w_i\cdot K_j-\mathsf{Enc_j}(v_{ij})$

   4. Compute $F_{ji}=\mathsf{Enc_i}(\beta_{ij})$, $F_{ji}'=\mathsf{Enc_i}(v_{ij})$, $\Gamma_i=g^{\gamma_i}$ and a proof $\pi_i^1$ which proves that $G_i=\mathsf{Enc_j}(\gamma_i)$, $\Gamma_i=g^{\gamma_i}$ and $\gamma_i<2^{3\lambda}$. The generation of $\pi_1^i$ can be seen in Supporting Protocols

   5. Compute the proof $\pi_i^2$ which prove that $(C_{ji},W_i,K_j,F_{ji},\gamma_i,\beta_{ij})$ satisfy the following relations

      • $C_{ji}=\gamma_i\cdot K_j-\mathsf{Enc_j}(\beta_{ij})$
      • $\Gamma_i=g^{\gamma_i}$
      • $F_{ji}=\mathsf{Enc_2}(\beta_{ij})$
      • $\beta_{ij} \le 2^{7\lambda}$
      • $\gamma_i \le 2^{3\lambda}$

   The generation of $\pi_i^2$ can be seen in Supporting Protocols.

   6. Compute the proof $\pi_i^3$, which prove that $(C_{ji}',\Gamma_i,K_j,F_{ji}',w_i,v_{ij})$ satisfy the following relations
      • $C_{ji}'=w_i\cdot K_j-\mathsf{Enc_j}(v_{ij})$
      • $W_i=g^{w_i}$
      • $F_{ji}'=\mathsf{Enc_2}(v_{ij})$
      • $v_{ij}<2^{7\lambda}$
      • $w_i \le 2^{3\lambda}$

   The generation of $\pi_i^3$ can be seen in Supporting Protocols.

   7. Send $C_{ji},C_{ji}',F_{ji},F_{ji}',\Gamma_i,\pi_i^1,\pi_i^2, \pi_i^3$ to all participants.

3. For each $j \neq i$, each participant $P_i$ does the following:

   1. Verify the validity of $\pi_j^1,\pi_j^2,\pi_j^3$. If any check fails, then the protocol aborts.

   2. Compute $\alpha_{ij}=\mathsf{Dec_i}(C_{ij})$ and $u_{ij}=\mathsf{Dec_i}(C_{ij}')$. Note that $\alpha_{ij}+\beta_{ij}=\gamma_i k_j\pmod{p}$ and $u_{ij}+v_{ij}=w_i k_j \pmod{p}$.

   3. Set $\delta_i=k_i\gamma_i+\sum_{j \neq i}(\alpha_{ij}+\beta_{ij}) \pmod{p}$ and $\sigma_i=k_iw_i+\sum_{j \neq i}(u_{ij}+v_{ij})\pmod{p}$. Note that $k\gamma=\sum_i\delta_i \pmod{p}$ and $k\cdot sk=\sum_i \sigma_i \pmod{p}$.

4. Each participant $P_i$ computes $\Gamma=\prod_i \Gamma_i=g^\gamma$, $\Delta_i=\Gamma^{k_i}=g^{\gamma k_i}$ and send $\delta_i,\Delta_i$ to all participants.

5. Each participant $P_i$ sets $\delta=\sum_i\delta_i=k\gamma$ and verify that $g^{\delta}=\sum_i\Delta_i$. If any check fails, the protocol aborts. Otherwise, set $R=\Gamma^{\delta^{-1}}=g^{\gamma(k\gamma)^{-1}}=g^{k^{-1}}$ and $r=R.\mathsf{x}$.

6. Each participants $P_i$ computes $m=\mathsf{H}(M)$, then broadcasts $s_i=m k_i+r \sigma_i \pmod{p}$. and set $s=\sum_{i} s_i=k(m+r\cdot sk) \pmod{p}$. If Verify$((M,(r,s),pk)=1$ then $(r,s)$ is a valid signature of $M$, otherwise aborts.

Verification

Recall that the verification algorithm in threshold ECDSA remain identical to an ordinary ECDSA verification algorithm. Hence, it is sufficient to describe the Verify algorithm of the threshold ECDSA below.

Verify$(M,\sigma=(r,s),pk)$: This is just the standard ECDSA verify algorithm, which can be publicly run by anyone. It works as follows:

1. Compute $m=\mathsf{H}(M)$.

2. Compute $u_1=m\cdot s^{-1} \pmod{p}$ and $u_2=r\cdot s^{-1} \pmod{p}$.

3. Compute $R=g^{u_1}pk^{u_2}$.

4. Check if $r=R.\mathsf{x}$. If the check passes, return $1$, otherwise return $0$.

One can see that, if $(r,s)$ is a valid ECDSA signature scheme, which has the form $r=g^{k^{-1}}.\mathsf{x}$ and $s=k(m+r\cdot sk)$, then the verification algorithm above returns $1$ since $R=g^{u_1}pk^{u_2}=g^{s^{-1}(m+r\cdot sk)}=g^{k^{-1}}$. The converse direction also holds, i.e, if the verify algorithm above return $1$, then $(r,s)$ must be a valid ECDSA signature which have the form above.

Supporting Protocols

In this section, we specify the supporting protocols that support the signing protocol described in the previous section.

Feldman's VSS

Recall that in Step 2 of the key generation protocol, each participant $P$ has to perform Feldman's VSS to share his secret $s$ to other participants $P_i$. The process of Feldman's VSS is described as follow:

1. $P$ generate a random degree $t$ polynomial $f(x)=a_0+a_1x+\dots+a_tx^t$ such that $a_0=s$, then broadcast $A_i=g^{a_i}$ for $i \in \{0,1,\dots,t\}$. Finally $P$ secretly send the share $s_i=f(i)$ to the $i$-th participant $P_i$.

2. Each participant $P_i$ can verify the correctness of his share $s_i$ by checking $g^{s_i}=\prod_{j=0}^tA_j^{i^j}$. If the check fails, $P_i$ broadcasts a complaint to $P$. If $P$ receives a complaint he will be disqualified.

Zero Knowledge Proofs

Schnorr Protocol:

In Step 3 of the initial key generation process, a participant who broadcasts $pk_i=g^{sk_i}$ must prove the knowledge of $sk_i$ using Schnorr protocol. Schnorr protocol can be described as follow:

1. The prover chooses $a \in \mathbb{Z}_p$ and sends $\alpha=g^a$.

2. The verifier sends a challenge $c \in \mathbb{Z}_p$.

3. The prover sends $u=a+c\sigma$.

4. The verifier checks if $g^u=\alpha\cdot pk_i^c$.

Schnorr Protocol for Ring:

In Step 3.3 of the key refresh process, a participant who broadcasts $h_1,h_2$ must prove that there is a value $s$ such that $h_2=h_1^s \pmod{N}$ The protocol can be described as follow:

1. For each $i=1,\dots,\lambda$, the prover chooses $a_1 \in \mathbb{Z_{\phi(N)}}$ and sends $A_i=h_1^{a_i} \pmod{N}$ to the verifier.

2. The verifier sends a challenge $e_i \in {0,1}$ for each $i=1,\dots,\lambda$.

3. For each $i=1,\dots,\lambda$, the prover sends $z_i=a_i+e_i s \pmod{\phi(N)}$ and send $z_i$ to the verifier.

4. The verifier checks if $h_1^{z_i}=A_i\cdot h_2^c \pmod{N}$ for each $i=1,\dots,\lambda$.

Proof of Product of Two Primes:

In Step 3.2 of the key refresh process, a participant must prove that the RSA modulus $N$ is a product of two primes $p,q$ such that $N=pq$ and $p \equiv q \equiv 3 \pmod{4}$ and $gcd(N,\phi(N))=1$. The protocol process as follow:

1. The prover samples $w \in \mathbb{Z_N}$ s.t $\left(\dfrac{w}{N}\right)=-1$ where $\left(\dfrac{w}{N}\right)$ denotes the Jacobian symbol.

2. The verifier samples $y_1,\dots,y_{\lambda} \in \mathbb{Z_N}$ and send them to the prover.

3. The prover proceed as follows:

   • Set $x_i=(y_i')^{1/4} \pmod{N}$ where $y_i'=(-1)^{a_i}w^{b_i}y_i$ such that $x_i$ is well defined.

   • Compute $z_i=y_i^{-N} \pmod{N}$

   • Send $(x_i,a_i,b_i,z_i)_{i=1}^\lambda$ to verifier.

4. The verifier checks that $N$ is not a prime, $z_i^N \equiv y_i \pmod{N}$ and $x_i^4 \equiv (-1)^{a_i}w^{b_i}y_i \pmod{N}$. Accept if and only if all checks pass.

Pallier Encryption Range Proof:

In Step 1.2 of the signing process, each participant given $K_i=\mathsf{Enc_i}(k_i)$ has to provide a proof $\pi$ certifying $k_i<2^{3\lambda}$. The protocol for providing $\pi$ proceeds as follow:

1. The protocol chooses $N,h_1,h_2$ to be the auxiliary set-up parameter for the protocol, where $N$ is a product of two safe prime and $h_1,h_2$ generate the same multiplicative group modulo $N$.

2. The prover samples $\alpha \in [-2^{3\lambda},\dots,2^{3\lambda}]$, $\delta \in [-2^{3\lambda}\cdot N,\dots,2^{3\lambda}\cdot N]$, $u \in [-2^{\lambda}\cdot N,\dots,2^{\lambda}\cdot N]$, $r \in \mathbb{Z_{N_1}}$

3. The prover computes $S=h_1^k h_2^u \pmod{N}$, $A=(1+N_1)^\alpha r^{N_1} \pmod {N_1^2}$ and $C=h_1^\alpha h_2^\delta \pmod{N}$

4. The prover sends $(S,A,C)$ to the verifier.

5. The verifier chooses a challenge $e \in [-p,\dots,p]$ and sends $e$ to the prover.

6. The prover computes $z_1=\alpha+ek$, $z_2=r\rho^e \pmod{N_1}$ and $z_3=\delta+eu$

7. The prover sends $\pi=(z_1,z_2,z_3)$ to the verifier

8. The verifier checks if $(1+N_1)^{z_1}z_2^{N_1}=AK^e \pmod{N_1^2}$ and $h_1^{z_1}h_2^{z_3}=CS^e \pmod{N}$

9 The verifier checks that $z_i \in [-2^{3\lambda},\dots,2^{3\lambda}]$

Proof of Paillier Encryption given Group Commitment:

In Step 2.4 of the signing process, each participant has public input $(C,X)$ and secret input $x$ and has to provide a proof $\pi$ which proves that $((C,X),x) \in \mathcal{R}$, where

$\mathcal{R}=\{((C,X),(x,\rho))\ |\ X=g^{x}\ \land\ C=\mathsf{Enc_1}(x,\rho)\ \land\ x \le 2^{3\lambda}\}$. The protocol for providing $\pi$ proceeds as follow:

1. The protocol chooses $N,h_1,h_2$ to be the auxiliary set-up parameter for the protocol, where $N$ is a product of two safe prime and $h_1,h_2$ generate the same multiplicative group modulo $N$.

2. The prover samples $\alpha \in [-2^{3\lambda},\dots,2^{3\lambda}]$, $\delta \in [-2^{3\lambda}\cdot N,\dots,2^{3\lambda}\cdot N]$, $u \in [-2^{\lambda}\cdot N,\dots,2^{\lambda}\cdot N]$, $r \in \mathbb{Z_{N_1}}$

3. The prover computes $S=h_1^xh_2^u \pmod{N}$, $A=(1+N_1)^\alpha r^N_1 \pmod{N_1^2}$, $Y=g^\alpha$, $D=h_1^\alpha h_2^\gamma \pmod{N}$

4. The prover sends $S,A,Y,D,F$ to the verifier.

5. The verifier chooses a challenge $e \in [-p,\dots,p]$ and sends $e$ to the prover.

6. The prover computes $z_1=\alpha+ek$, $z_2=r\rho^e \pmod{N_1}$ and $z_3=\gamma+eu$

7. The prover sends $\pi=(z_1,z_2,z_3)$ to the verifier.

8. The verifier checks that $(1+N_1)^{z_1}z_2^{N_1}=AC^e \pmod{N_1^2}$, $g^{z_1}=YX^e$ and $h_1^{z_1}h_2^{z_3}=DS^e \pmod{N}$

9. The verifier check that $z_1 \in [-2^{3\lambda},\dots,2^{3\lambda}]$

Proof of Paillier Operation given Group Commitment:

In Step 2.5 and 2.6 of the signing process, each participant has public input $(C,X,K,Y)$ and secret input $(x,y)$ and has to provide a proof $\pi$ which proves that $((C,X,K,Y),(x,y)) \in \mathcal{R}$, where

$\mathcal{R}=\{((C,X,K,Y),(x,y,\rho,\rho_y))\ |\ C=x\cdot K-\mathsf{Enc_1}(y,\rho)\ \land\ X=g^{x}\ \land\ Y=\mathsf{Enc_2}(y,\rho_y)\ \land\ x<2^{3\lambda}\ \land \ y \le 2^{7\lambda}\}$ The protocol for providing $\pi$ proceeds as follow:

1. The protocol chooses $N,h_1,h_2$ to be the auxiliary set-up parameter for the protocol, where $N$ is a product of two safe prime and $h_1,h_2$ generate the same multiplicative group modulo $N$.

2. The prover samples $\alpha\in [-2^{3\lambda},\dots,2^{3\lambda}]$, $\beta\in [-2^{7\lambda},\dots,2^{7\lambda}]$, $\gamma, \delta \in [-2^{3\lambda}\cdot N,\dots,2^{3\lambda}\cdot N]$, $m, u \in [-2^{\lambda}\cdot N,\dots,2^{\lambda}\cdot N]$, $r \in \mathbb{Z_{N_1}}$ and $r_y \in \mathbb{Z_{N_2}}$

3. The prover computes $A=K^\alpha((1+N_1)^\beta r^{N_1}) \pmod {N_1^2}$, $B_x=g^\alpha$, $B_y=(1+N_2)^\beta r_y$, $E=h_1^\alpha h_2^\gamma \pmod{N}$, $F=h_1^\beta h_2^\gamma \pmod{N}$, $S=h_1^xh_2^m \pmod{N}$, $T=h_1^yh_2^u \pmod{N}$

4. The prover sends $S,T,A,B_x,B_y,E,F$ to the verifier.

5. The verifier chooses a challenge $e \in [-p,\dots,p]$ and sends $e$ to the prover.

6. The prover compute $z_1=\alpha+ex$, $z_2=\beta+ey$, $z_3=\gamma+em$, $z_4=\delta+eu$, $w=r \rho^e \pmod{N_1}$, $w_y=r \rho_y^e \pmod{N_2}$

7. The prover sends $\pi=(z_1,z_2,z_3,z_4,w,w_y)$ to the verifier.

8. The verifier checks that $K^{z_1}(1+N_1)^{z_2}w^{N_1} = A C^e \pmod{N}$, $g^{z_1}=B_xX^e$, $(1+N_2)^{z_2}w_y^{N_2}=B_yY^e \pmod{N_2}$, $h_1^{z_1}h_2^{z_3}=ES^e \pmod{N}$, $h_1^{z_2}h_2^{z_4}=FT^e \pmod{N}$

9. The verifier check that $z_1 \in [-2^{3\lambda},\dots,2^{3\lambda}]$ and $z_1 \in [-2^{7\lambda},\dots,2^{7\lambda}]$

Commitment Scheme

In Step 1 of the Key Generation protocol, we require participants to commit their messages using a commitment scheme $\mathsf{Com}$. In practice, one can use a cryptographic hash function $\mathsf{H}$ and define the commitment of $X$ to be $\mathsf{H}(X,r)$ where $r$ is chosen uniformly.

Identifying Aborts

Identifying misbehaving participants efficiently is a key contribution of “CGMP21”. An abort will happen if any player deviates from the protocol in a clearly identifiable way by not complying with instructions. In the case of such an abort, the guilty party would have to be identified and removed. In this section, we analyse how the protocol can identify abortion and remove mmisbehaving participants.

Abort Instances

Within the signing protocol, there are 3 instances that the protocol can abort. They can be summarized as follows:

1. In step 2 of the signing process, when an invalid proof $\pi_i$ is detected.

2. In step 3 of the signing process, when an invalid proof $\pi_i^1$ or $\pi_j^2$ or $\pi_k^3$ is detected for some $i,j,k$.

3. In step 5 of the signing proces, when $g^{\delta}=\sum_i\Delta_i$

4. In step 6 of the signing process, when $(r,s)$ is not a valid signature of $M$

How to Identify Abortions

Now, we show that how to identify the misbehaving participants that cause the protocol to abort in each cases above.

1. The first and second instances are straightforward. Whoever submits the wrong proof will be identified as malicious.

2. The third and fourth instance are much more complicated. At a high level, the identification of these two instances proceed as follow:

   1. Each participant $P_i$ is asked to reprove that the ciphertexts $C_{ij}$ are well formed for each $j \neq i$.

   2. Each participant $P_i$ is asked to reveal $H_i=\mathsf{Enc_i}(k_i \gamma_i)$ and $H_i'=\mathsf{Enc_i}(k_i w_i)$ and prove their correctness given $K_i,G_i$ and $X_i$.

   3. Each participant $P_i$ prove that $\delta_i$ is the plaintext obtained via the ciphertext $U_i=H_i\prod_{j \neq i}C_{ij}F_{ji}=\mathsf{Enc_i}(k_i\gamma_i+\sum_{j \neq i}(\alpha_{ij}+\beta_{ij}))$

   4. Similarly, each participant $P_i$ prove that $s_i$ is the plaintext obtained via the ciphertext $V_i=K_i^m(H_i'\prod_{j \neq i}C_{ij}'F_{ji}')^r=\mathsf{Enc_i}(mk_i+r(k_iw_i+\sum_{j \neq i}(u_{ij}+v_{ij})))=\mathsf{Enc_i}(mk_i+r\sigma_i)$

   5. Whoever fails to prove will be identified as the malicious participant.

Security Consideration

Finally, since there has been numerous pracical attacks performed on threshold ECDSA implementations, we would like to discuss several concerns that should be noted when implementing the threshold ECDSA protocol.

• Proving the Discrete Log Relation in Composite Modulus: Recall that in Step 3 of the key refresh process, we require the participants $P_i$ to prove the discrete log relation between $h_{i1}$ and $h_{i2}$ in modulo $N_i$. This can be done using Schnorr's protocol for Ring, as specified in (see Supporting Protocols). The protocol uses binary challenge $c \in \{0,1\}$, which has soundness error $1/2$. It is repeated $\lambda$ times to achieve soundness error $1/2^\lambda$. When the order of the group is a prime number $p$, one can extend the challenge set to be $\mathbb{Z}_p$ and execute the protocol only once, this is the case of an ordinary Schnorr protocol. However, we cannot do the same thing for the group $\mathbb{Z}^*_N$, since its order is divisible by $2$. Verichain showed that doing so can leak the secret key of the protocol. Hence, we need to repeat the Schnorr protocol for Ring $\lambda$ times when proving the discrete log relation in modulo $N_i$ for each $i$.

• The Requirement of Range Proof: Recall that in step 2 of the signing protocol, we require that each participant has to prove that some of their secret range must lie in a specified value (we require $k_i,\lambda_i,w_i, \le 2^{3\lambda}$ and $\gamma_{ij},v_{ij}<2^{7\lambda}$). The range proof might looks unnecessary at the first glance, however it is shown in TS21 that the lack of these range proofs can break the security of the protocol. The reason for this is that range proofs ensure that the encrypted values are within a specified range, and prevent attackers from tampering with the values or sending invalid data. Hence it is necessary to ensure that these range proofs are done in the protocol.

FROST's Construction

In this section we briefly describe the FROST threshold Schnorr protocol in KG20, in which we assume that the readers have some familiarity to Schnorr signature scheme. Recall that the ordinary Schnorr signature scheme, the signature $\sigma=(R,z)$ of a message $M$ is generated as follow

$R=g^r,\ c=\mathsf{H}(R||\mathsf{pk}||M)\ \text{and}\ z=r+c\cdot sk,$

where $r \leftarrow \mathbb{Z}_p$ and $sk$ is the signer's secret key. Note that the EdDSA signature scheme also produces the signature with the exact form above, with the only difference is that the nonce $r$ is produced deterministically. FROST aims to provide a valid Schnorr signature (as well as EdDSA signature) of $M$ above via a threshold manner. Compared to its threshold ECDSA counterpart, the FROST threshold Schnorr signature is much simplier, has much less features to describe and analyse. We now move to the actual construction of FROST and describe it.

Key Generation

In this section, we describe the key generation process in the construction of FROST below.

Notation: Let $\lambda$ to be the security parameter. Let $\mathbb{G}$ to be a cyclic group whose order is a prime number. Let $p \in (2^{\lambda-1},2^\lambda)$ to be the order of $\mathbb{G}$ and let $g,h$ to be two generators of $\mathbb{G}$. We denote $\mathsf{Com}$ to be a secure binding and information theoretic hiding commitment scheme and $\mathsf{H}$ to be a cryptographic hash function. For any set $\mathcal{S}$ and for any $i \in \mathcal{S}$ we denote $\lambda_{i,S}=\prod_{j\in \mathcal{S},j \neq i}\dfrac{j}{j-i}$ to be the Lagrange coefficient w.r.t $S$.

Keygen $(1^\lambda)\langle \{P_i\}_{i=1}^n\rangle$:

The key generation process is executed once at the beginning.

1. Each participant $P_i$ selects $s_i \in Z_p$ and compute $C_i=\mathsf{Com}(g^{s_i})$.

2. Each participant $P_i$ broadcasts $y_i=g^{s_i}$. The public key $pk$ is set to be $pk=\prod_{i=1}^ny_i$. $P_i$ then performs Feldman's Verifiable Secret Sharing scheme (see Supporting Protocols) to share $s_i$ to other participants. Each $P_j$ add the secret shares received as his secret key, i.e, $sk_j=\sum_i s_{ij}$. The values $sk_i$ are the shares of a $(t-n)$ Shamir secret sharing of the secret key $sk$.

3. Finally, each participant uses Schnorr's protocol S91 (see Supporting Protocols) to prove in zero knowledge that he knows the secret key $sk_i$,

By the property of Feldman's VSS, it can be proven that the public key $pk$ is also equal to $g^{sk}$, hence the key pair $(pk,sk)$ generated using the key generation protocol above has the same form of a key pair in a Schnorr signature scheme.

Signing

In this section, we describe the signing process of the protocol. For any set $S \in \{1,\dots,n\}$ of $t+1$ participants who participate to sign a message $M$, let $w_i=\lambda_{i,S}\cdot sk_i \pmod{p}$. Note that by Feldman's VSS, $sk=\sum_{i \in S} w_i$. Note that since $pk_i=g^{sk_i}$ is public after the key generation process, hence the value $W_i=g^{w_i}=pk_i^{\lambda_{i,\mathcal{S}}}$ can also be publicly computed. The signing protocol follows a $6$ steps process below:

Sign$(M)\langle \{P_i(sk_i)\}_{i=1}^n\rangle$:

1. Each participant $P_i$ chooses $d_{i},e_{i} \in \mathbb{Z_p}$ and broadcasts $(D_{i},E_{i})=(g^{d_{i}},g^{e_{i}})$. Denote $B=\{(i,D_i,E_i)\}_{i \in S}$.

2. For each $j \neq i$, each $P_i$ uses Schnorr protocol (see Supporting Algorithms) to check the validity of $(D_i,E_i)$. If any check fails then the protocol aborts.

3. Each $P_i$ computes $\rho_j=\mathsf{H}(j,M,B)$ for all $j \in S$. Each $P_i$ then computes the group commitment $R=\prod_{j \in S} D_jE_j^{\rho_j}$ and the challenge $c=\mathsf{H}(R,\mathsf{pk},M)$, then broadcasts $(\rho_i,R,c)$.

4. Each $P_i$ computes $z_i=d_i+e_i\rho_i+\lambda_{i,S}\cdot \mathsf{sk_i} \cdot c$ and broadcasts $z_i$.

5. Each $P_i$ computes $R_i=D_iE_i^{\rho_i}$ and broadcasts $R_i$.

6. For each $i$, participants check if $R=\prod_{i\in S}R_i$ and $g_i=R_i\mathsf{pk_i}^{c \lambda_{i,S}}$. If any check fails, report the misbehaving $P_i$ and the protocol is aborted. Otherwise, compute $z=\sum_{i \in S}z_i$ and returns $\sigma=(R,z)$.

Verification

Recall that the verification algorithm in threshold Schnorr remain identical to an ordinary Schnorr verification algorithm. Hence, it is sufficient to describe the Verify algorithm of the Schnorr signature scheme below.

Verify$(M,\sigma=(R,z),\mathsf{pk})$: This is just the standard Schnorr verify algorithm, which can be publicly run by anyone. It works as follow:

1. Compute $c=\mathsf{H}(R||\mathsf{pk}||M)$.

2. Compute $R'=g^z \mathsf{pk}^{-c}$.

3. Check if $R'=R$. If the check passes, return $1$, otherwise return $0$.

One can see that, if $(R,z)$ is a valid Schnorr signature scheme, which has the form $R=g^r, c=\mathsf{H}(R||\mathsf{pk}||M)$ and $z=r+c \cdot \mathsf{sk})$, then the verification algorithm above returns $1$ since $R'=g^{z-\mathsf{sk}\cdot c}=g^r=R$. The converse direction also holds, i.e, if the verify algorithm above return $1$, then $(R,c,z)$ must be a valid Schnorr signature which have the form above.

Supporting Protocols

In this section, we specify the supporting protocols that support the signing protocol described in the previous section.

Feldman's VSS

Recall that in Step 2 of the key generation protocol, each participant $P$ has to perform Feldman's VSS to share his secret $s$ to other participants $P_i$. The process of Feldman's VSS is described as follows:

1. $P$ generate a random degree $t$ polynomial $f(x)=a_0+a_1x+\dots+a_tx^t$ such that $a_0=s$, then broadcast $A_i=g^{a_i}$ for $i \in \{0,1,\dots,t\}$. Finally $P$ secretly send the share $s_i=f(i)$ to the $i$-th participant $P_i$.

2. Each participant $P_i$ can verify the correctness of his share $s_i$ by checking $g^{s_i}=\prod_{j=0}^tA_j^{i^j}$. If the check fails, $P_i$ broadcasts a complaint to $P$. If $P$ receives a complaint he will be disqualified.

Zero Knowledge Proofs

Schnorr Protocol:

In Step 3 of the initial key generation process, a participant who broadcasts $pk_i=g^{sk_i}$ must prove the knowledge of $sk_i$ using Schnorr protocol. Schnorr protocol can be described as follows:

1. The prover chooses $a \in \mathbb{Z}_p$ and sends $\alpha=g^a$.

2. The verifier sends a challenge $c \in \mathbb{Z}_p$.

3. The prover sends $u=a+c\sigma$.

4. The verifier checks if $g^u=\alpha\cdot pk_i^c$.

Threshold Signature Instantiations

In this section, we are going to discuss our concrete instatiations for the construction of Canneti et al and FROST. More specifically, we will discuss and analyse the security when instatiating the construction of Canneti et al using secp256k1 parameters and FROST with ed25519 and sr25519 parameters to support the MPC version for these concrete variants.

Threshold signatures for secp256k1

Bitcoin, the first and most well-known cryptocurrency, relies on the curve secp256k1 for its public key cryptography. Specifically, it uses the ECDSA algorithm with secp256k1 as the underlying elliptic curve. Many other cryptocurrencies, including Ethereum have since adopted this curve for their digital signature schemes. Since the curve can be used for the orinary ECDSA algorithm, it can also be used for the threshold ECDSA version as well. Below we describe the curve parameter and its security and efficiency analysis.

The secp256k1 curve parameters $E:y^2=x^3+ax+b$ defined over $\mathbb{F}_p$ with order $n$, cofactor $f$ and base point $G$ are as follows:

• $p=0xfffffffffffffffffffffffffffffffffffffffffffffffffffffffefffffc2f$

• $a=0x00$

• $b=0x07$

• $n=0xfffffffffffffffffffffffffffffffebaaedce6af48a03Bbfd25e8cd0364141$

• $f=1$

• $G=(0x79be667ef9dcbbac55a06295ce870b07029bfcdb2dce28d959f2815b16f81798,$ $0x483ada7726a3c4655da4fbfc0e1108a8fd17b448a68554199c47d08ffb10d4b8)$

For security analysis, this curve is chosen by Satoshi Nakamoto because unlike the popular NIST curves, secp256k1's constants were selected in a predictable way, which significantly reduces the possibility that the curve's creator inserted any sort of backdoor into the curve. In addition, it is implied in SECG1 that the curve has a security level of $128$ bits, which is considered secure.

We intend to implement the threshold ECDSA construction of CGGMP21 using secp256k1 parameters. We would like to use the library libsecp256k1 for curve operations, which has been tested extensively and undergone thorough optimitation, making it very fast to produce signatures.

Threshold signatures for ed25519

Ed25519 is the most popular instance of the Edwards-curve Digital Signature Algorithm (EdDSA) standardized in RFC 8032. In the paper, the authors instatiatied the Schnorr signature scheme with the curve curve25519 in its twisted Edward form instead of an ordinary elliptic curve such as secp256k1. The used curve in the scheme is popular due to its high speed compared to other curves without sacrificing security. Below we describe the curve parameters and its security and efficiency analysis.

The curve parameters $E: ax^2+y^2=1+bx^2y^2$ defined over $\mathbb{F}_p$ with order $n$, cofactor $f$ and base point $G$ are as follows:

• $p=0x7fffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffed$

• $a=0x7fffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffec$

• $b=0x52036cee2b6ffe738cc740797779e89800700a4d4141d8ab75eb4dca135978a3$

• $n= 0x1000000000000000000000000000000014def9dea2f79cd65812631a5cf5d3ed$

• $f=8$

• $G=(0x216936d3cd6e53fec0a4e231fdd6dc5c692cc7609525a7b2c9562d608f25d51a,$ $0x6666666666666666666666666666666666666666666666666666666666666658)$

For security analysis, the provable security of the instatiation of ed25519 parameters has been well studied in BCJZ20. In addition, it has been confirmed in BDLSY12 that the curve achieves $128$ bit security level, the same security level as secp256k1, which is considered secure. However, due to having the cofactor of $8$, the scheme could be potentially vulnerable to a double spend exploit.

Recall that ed25519 is just a variant of Schnorr signature instatiatied with a a twisted Edward curve, and its signature form $R,c,z$ is identical to an ordinary Schnorr signature scheme, we can instatiate the FROST threshold signature scheme of KG20 with the parameters of ed25519 described in to achieve the MPC version of ed25519.

Threshold signatures for sr25519

The term sr25519 refers to the instatiation of Schnorr signature using the curve curve25519, the same curve as of EdDSA, which is specified in Schnorrkel. However, it additionally employs the method of point compression due to Ristretto to make makes Schnorr signatures over the Edward's curve more secure. Below we describe the curve parameter and its security and efficiency analysis.

The sr25519 scheme supports both forms of curve25519, i.e, its twisted Edward form and Montomery form. The twisted Edward form of curve25519 has been described in the previous Section. For the Montomery form, the curve can be written as $E:by^2=x^3+ax^2+x$ over $\mathbb{F}_p$ with order $n$, cofactor $f$ and base point $G$ are as follows:

• $p=0x7fffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffed$

• $a=0x76d06$

• $b=0x01$

• $n=0x1000000000000000000000000000000014def9dea2f79cd65812631a5cf5d3ed$

• $cofactor=1$

• $G=(0x09,0x20ae19a1b8a086b4e01edd2c7748d14c923d4d7e6d7c61b229e9c5a27eced3d9)$

For security analysis, recall that the curve curve25519 achieves $128$ bit security level, as specified in the previous Section. However, since sr25519 additionally uses the point compression due to Ristretto, it is safe from the bug could lead to a double spend expoit of Monero

Finally, because sr25519 is actually the Schnorr signature instatiatied with the curve25519 and FROST is a threshold Schnorr signature scheme that can be instatiated by any curve where the discrete log problem is hard, we can instatiate the FROST threshold signature scheme of KG20 with the parameters of sr25519 described in to achieve the MPC version of sr25519.