ZK/SEC Quarterly

Back to all posts

Threshold ECDSA: Building CGGMP from scratch

Samuel Tang July 27, 2026 37 min read
crypto mpc threshold-ecdsa

Why threshold ECDSA is trickier than it looks

This post is based on CGGMP24 (IACR 2021/060), an $n$-of-$n$ threshold ECDSA scheme1. The idea for threshold ECDSA is that each party $\mathbf{P}_1, \mathbf{P}_2, \dots, \mathbf{P}_n$ owns a secret key share, and they can collaboratively come up with an ECDSA signature, without leaking their secret, as long as the threshold is reached.

We will use an elliptic curve parameterized by $(\mathbb{G}, G, q)$ (the curve group, a generator and the curve order) for ECDSA. Let $m$ be the message2, $x$ be the private key and $k$ be a random nonce in $\mathbb{F}_q$. The signature, $(r, s)$, is given by

$$ \left\{\begin{aligned} & R = k \cdot G \\ & s = k^{-1} \cdot (m + r \cdot x)\ \text{mod}\ q, \end{aligned}\right. $$

where $r$ is the $x$-coordinate of $R$.

Now, given that party $i$ (namely, $\mathbf{P}_i$) has a private key share $x_i$ and generates a nonce share $k_i$, such that

$$ x = \sum_i x_i \quad \text{and} \quad k = \sum_i k_i. $$

CGGMP uses the inverse nonce technique, i.e., replace $k$ by $k^{-1}$:

$$ \left\{\begin{aligned} & R = k^{-1} \cdot G \\ & s = (k \cdot m + r \cdot k \cdot x)\ \text{mod}\ q. \end{aligned}\right. $$
Important

Problem: How do we compute $k^{-1} \cdot G$? We will introduce another random value, $\gamma$ with $\gamma = \sum_j \gamma_j$ and $\mathbf{P}_i$ has its share $\gamma_i$. Rewrite $R = (k \cdot \gamma)^{-1} \cdot (\gamma \cdot G)$.

Eventually, the relations are

$$ \left\{\begin{aligned} & R = ({\color{#ff7b72}k \cdot \gamma})^{-1} \cdot (\gamma \cdot G) \\ & s = (k \cdot m + r \cdot {\color{#ff7b72}k \cdot x})\ \text{mod}\ q. \end{aligned}\right. $$

Even if the parties are semi-honest, in that they will faithfully follow the protocol while learning from the transcript, $k \cdot \gamma$ and $k \cdot x$ are still non-trivial to compute. Here we introduce the Multiplicative-to-Additive (MtA) protocol.

The MtA protocol

Alice owns $a$ and Bob owns $b$ with $a, b \in [0, q)$, where $q \approx 2^\ell$. Suppose that they want to collaboratively compute $a \cdot b \ \text{mod} \ q$ without learning the other party's share.

Note

What is $q$? In our case, $q$ is the curve order of ECDSA. We use secp256k13 and thus $\ell = 256$.

CGGMP uses Paillier cryptosystem for MtA. Alice owns the key, and denote the modulus by $N$. Denote also $\textsf{Paillier}.\textsf{Encrypt}_N(x, \rho) := (1 + N)^x \cdot \rho^N \ \text{mod}\ N^2 \in \mathbb{Z}_{N^2}^*$ be the ciphertext of message $x \in \mathbb{Z}_N$ and nonce $\rho \in \mathbb{Z}_N^*$.

With the MtA protocol below, Alice and Bob own $\alpha$ and $\beta$ with $a \cdot b \equiv \alpha - \beta \ (\text{mod}\ q)$.

Note

In most literature, one will use $a \cdot b = \alpha + \beta$ to show the multiplicative to additive conversion. We will use $\alpha - \beta$ to prevent underflowing values from Paillier.

Important

Meaning of $c'$ in Bob's calculation $c' = \textsf{Paillier}.\textsf{Encrypt}_{N}(a \cdot b + \beta, r^b \cdot r')$. Made possible by the homomorphic properties of Paillier cryptosystem. Concretely,

  • Alice computes $c := (1 + N)^a \cdot r^N\ \text{mod}\ N^2$.
  • Bob computes $c' := c^b \cdot [(1 + N)^\beta \cdot {r'}^N]\ \text{mod}\ N^2$.

Finally, Alice obtains her share $\alpha = (a \cdot b + \beta) \ \text{mod}\ q$, and Bob has $\beta$.

[!NOTE] A note on the sizes of $N$ and $\ell'$ Note that the modulus $N$ should be significantly larger than $q$ (so as not to overflow). Additionally, $\ell' := 5 \cdot \ell$ is chosen to ensure $\beta$ is large enough that Alice cannot learn $b$ from $\alpha$. In Fireblocks' implementation as well as suggested in appendix C.1 of the CGGMP paper, $\ell = 256$4, $\ell' = 1280$5 and $N$ is of 2048 bits6.

In a multi-party scenario, where the parties $\mathbf{P}_1, \mathbf{P}_2, \dots, \mathbf{P}_n$ want to compute

$$ a \cdot b = \sum_j a_j \cdot \sum_j b_j, $$

where $\mathbf{P}_i$ has $a_i$ and $b_i$. They will need $\mathcal{O}(n^2)$ MtAs to compute $a \cdot b$:

For each distinct $i, j \in \{1, ..., n\}$, $\mathbf{P}_i$ and $\mathbf{P}_j$ will go through MtA to compute $a_i \cdot b_j$. After that $\mathbf{P}_i$ and $\mathbf{P}_j$ will respectively have $\alpha_{ij}$ and $\beta_{ji}$ with $a_i \cdot b_j = \alpha_{ij} - \beta_{ji}$.

When $\mathbf{P}_i$ completes the $2n-2$ MtAs, it computes $\delta_i$ given by

$$ \delta_i := a_i \cdot b_i + \sum_{j \neq i} (\alpha_{ij} - \beta_{ij}), $$

then finally broadcasts $\delta_i$. After that, one can get $a \cdot b\ \text{mod}\ q$ by computing $\sum_j \delta_j\ \text{mod}\ q$.

Below is an example with three parties, $\color{#f07178}\mathbf{P}_1$, $\color{#c3e88d}\mathbf{P}_2$ and $\color{#82aaff}\mathbf{P}_3$, on what each of them has after the MtA, and how they could obtain $a \cdot b$ collaboratively:

$\color{#f07178}a_1$ $\color{#c3e88d}a_2$ $\color{#82aaff}a_3$
$\color{#f07178}b_1$ $\color{#f07178}a_1 \cdot b_1$ ${\color{#c3e88d}\alpha_{21}} - {\color{#f07178}\beta_{12}}$ ${\color{#82aaff}\alpha_{31}} - {\color{#f07178}\beta_{13}}$
$\color{#c3e88d}b_2$ ${\color{#f07178}\alpha_{12}} - {\color{#c3e88d}\beta_{21}}$ $\color{#c3e88d}a_2 \cdot b_2$ ${\color{#82aaff}\alpha_{32}} - {\color{#c3e88d}\beta_{23}}$
$\color{#82aaff}b_3$ ${\color{#f07178}\alpha_{13}} - {\color{#82aaff}\beta_{31}}$ ${\color{#c3e88d}\alpha_{23}} - {\color{#82aaff}\beta_{32}}$ $\color{#82aaff}a_3 \cdot b_3$

After all, $a \cdot b \equiv (a_1 + a_2 + a_3) \cdot (b_1 + b_2 + b_3) \equiv \delta_1 + \delta_2 + \delta_3\ (\text{mod}\ q)$.

For CGGMP, the party $\mathbf{P}_i$ initiates two MtAs with $\mathbf{P}_j$ to compute $k_i \cdot \gamma_j$ and $k_i \cdot x_j$. From the two MtAs, $\mathbf{P}_i$ gets $\alpha_{ij}$ and $\hat\alpha_{ij}$, and $\mathbf{P}_j$ gets $\beta_{ji}$ and $\hat\beta_{ji}$ such that

$$ \left\{\begin{aligned} & \alpha_{ij} - \beta_{ji} = k_i \cdot \gamma_j \\ & \hat\alpha_{ij} - \hat\beta_{ji} = k_i \cdot x_j. \end{aligned}\right. $$

Then $\mathbf{P}_i$ computes

$$ \left\{\begin{aligned} & \delta_i := [k_i \cdot \gamma_i + \sum_{j \neq i} (\alpha_{ij} - \beta_{ij})]\ \text{mod}\ q \\ & \chi_i := [k_i \cdot x_i + \sum_{j \neq i} (\hat\alpha_{ij} - \hat\beta_{ij})]\ \text{mod}\ q. \end{aligned}\right. $$

CGGMP, the semi-honest protocol

This is what $\mathbf{P}_i$ does in the semi-honest setting:

$\textsf{CGGMP}.\textsf{KeyGenV1}$

The public key is $X := \sum_j X_j$.

$\textsf{CGGMP}.\textsf{SignV1}$

After the five rounds, an observer could compute the signature $(r, s)$ for message $m$:

$$ \left\{\begin{aligned} & R = \left(\sum_j \delta_j\right)^{-1} \cdot \sum_j \Gamma_j \\ & s = \sum_j \sigma_j \ \text{mod} \ q \end{aligned}\right. $$

The parties are no longer semi-honest

Some parties are now malicious and they no longer faithfully follow the protocol. To make sure the parties are following the protocol as intended, CGGMP requires the parties to provide commitments and/or zero-knowledge proofs for things that could go wrong.

CGGMP addresses the few issues that would lead to either unattributable denial-of-service or key leaks. We assume that $\mathbf{P}_i$ is one of the malicious parties below.

Warning

Issue 1: In round 1, $\mathbf{P}_i$ waits for $\Gamma_j$ ($j \neq i$) from everyone, then adaptively computes and broadcasts $\Gamma_i$ to their liking. Impact: $\mathbf{P}_i$ could send $\Gamma_i := -\sum_{j \neq i} \Gamma_j$ and make $\Gamma = O$ (i.e., the additive identity). This would make $R = O$ which the verifier should always reject.

CGGMP addresses this issue by making $\mathbf{P}_i$ broadcast $B_i$ (an ElGamal commitment of $\gamma_i$) in round 1, and defer $\Gamma_i$ to round 2. $\mathbf{P}_i$ also sends a ZKP in round 2, $\psi_i$ to prove $\Gamma_i$ is consistent with $B_i$.

Note

What is $\Pi^\textsf{elog}$? $\Pi^\textsf{elog}$ is the zero-knowledge proof showing the relation

$$ R_\textsf{elog} = \{(\underbrace{X, H}_\text{dlog}, \underbrace{B, Y}_\text{ElGamal}; x, \alpha) \ | \ X = x \cdot H \wedge B = (\alpha \cdot G, x \cdot G + \alpha \cdot Y) \}. $$

Intuitively, it proves that $X = {\color{#ffb454}x} \cdot H$ and $B = \textsf{ElGamal}.\textsf{Encrypt}({\color{#ffb454}x}, \alpha)$ share the same ${\color{#ffb454}x}$.

There are two functions associated with $\Pi^\textsf{elog}$ (and the future ZKPs), - $\Pi^\textsf{elog}.\textsf{Prove}((X, H, B, Y), (x, \alpha))$ which generates a zero-knowledge proof $\psi$, and - $\Pi^\textsf{elog}.\textsf{Verify}((X, H, B, Y), \psi)$ which verifies the generated proof.

$\mathbf{P}_i$ uses $\Pi^\textsf{elog}$ to generate $\psi_i$ in CGGMP, to convince the other parties that $\Gamma_i$ uses the same $\gamma_i$ as $B_i$ without revealing it.

$\textsf{CGGMP}.\textsf{SignV2}$
Warning

Issue 2a: In round 2, the $\gamma_i$ used to compute $D_{ji}$ might be different from the one that is used to compute $\Gamma_i$. Impact: A malicious party can fail the signing process and the culprit couldn't be identified.

CGGMP addresses this issue by introducing the ZKP, $\Pi^\textsf{aff-g}$, to show that $D_{ji}$ is correctly computed using the same $\gamma_i$ as $\Gamma_i$. To make this happen, $\textsf{CGGMP}.\textsf{KeyGen}$ also generates the Pedersen parameters.

Note

What is $\Pi^\textsf{aff-g}$? $\Pi^\textsf{aff-g}$ is another zero-knowledge proof showing the relation

$$ \begin{aligned} R_\textsf{aff-g} = \{(\textsf{PUB}, D, K, F, X; x, y, r, \rho) \ | & \ D = K^x \cdot (1 + N_0)^y \cdot r^{N_0} \ \text{mod}\ N_0^2 \\ & \quad \wedge F = (1 + N_1)^y \cdot \rho^{N_1}\ \text{mod} \ N_1^2 \\ & \quad \wedge X = x \cdot G \}. \end{aligned} $$

Here $\textsf{PUB} = (N_0, N_1, \hat N, s, t)$, where $N_0$ and $N_1$ respectively are the Paillier moduli for the verifier and the prover, and $(\hat N, s, t)$ are the Pedersen parameters with $s, t \in \mathbb{Z}_{\hat N}^*$ and $s \in \langle t \rangle$. The Pedersen parameters will be generated by the verifier to make sure that the provers could not forge a proof.

The goal of the proof is to show that if $K = \textsf{Paillier}.\textsf{Encrypt}_{N_0}(u, s')$, then $D = \textsf{Paillier}.\textsf{Encrypt}_{N_0}({\color{#f07178}x} \cdot u + {\color{#82aaff}y}, s'^{\color{#f07178}x} \cdot r)$, and that the $\color{#f07178}x$ and $\color{#82aaff}y$ used are the same as those in $X = {\color{#f07178}x} \cdot G$ and $F = \textsf{Paillier}.\textsf{Encrypt}_{N_1}({\color{#82aaff}y}, \rho)$. Note that the prover does not know the plaintext for $K$, as $K$ is computed by the verifier.

This shows that the prover knows $x$ and $y$ and correctly uses them to compute $D$.

$\textsf{CGGMP}.\textsf{KeyGenV2}$

The public key is $X := \sum_j X_j$.

$\textsf{CGGMP}.\textsf{SignV3}$
Warning

Issue 2b: In round 2, the $x_i$ used to compute $\hat D_{ji}$ might be different from $\mathbf{P}_i$'s secret key share. Impact: Similar to issue 2a.

Similar to issue 2a, CGGMP introduces $\hat\psi_{ji}$ to show that $\hat D_{ji}$ is computed from $K_j, x_i$ and $\hat \beta_{ij}$.

$\textsf{CGGMP}.\textsf{SignV4}$
Warning

Issue 3a: In round 2, $\gamma_i, x_i, \beta_{ij}$ and $\hat\beta_{ij}$ are unbounded. Impact: A malicious $\mathbf{P}_i$ could bias $k$ toward small values by forcing an abort whenever another party's $k_j$ is large.

Below is an example to create a biased $k$. $\mathbf{P}_i$ sets $k_i := 0, \gamma_i \in [0, 2^\ell)$ and $\beta_{ij} := N_j - \gamma_i \cdot 2^{240}$ for all $j \neq i$. Then $k_j \in [0, 2^{240})$ if and only if

$$ \begin{aligned} \gamma_i \cdot k_j + \beta_{ij} = \gamma_i \cdot k_j + (N_j - 2^{240} \cdot \gamma_i) = N_j + \gamma_i \cdot (k_j - 2^{240}) \in [0, N_j). \end{aligned} $$

Thus $\alpha_{ji} := \textsf{Paillier}.\textsf{Decrypt}(D_{ji}) = \gamma_i \cdot k_j + \beta_{ij}\ \text{mod}\ N_j$ overflows if $k_j \geq 2^{240}$. With that, the protocol would fail somewhere and a signature would not be produced. This would imply a signature could be produced if and only if $k_j \in [0, 2^{240})$ for all $j \neq i$, and now $k := \sum k_i$ is biased toward small values7.

CGGMP extends $\Pi^\textsf{aff-g}$ to include range proofs, in addition to the original checks. That said, it also requires that $x \in [0, 2^{\ell + \epsilon})$ and $y \in [0, 2^{\ell' + \epsilon})$. It is suggested from the paper that $\ell = 256$, $\ell' = 1280$, $\epsilon = 512$, and $\text{log}_2 N \approx 2048$. Assuming that $c \in [0, 2^{\ell + \epsilon})$, we have

$$ 0 \leq 0 \cdot 0 + 0 \leq x \cdot c + y < 2^{\ell + \epsilon} \cdot 2^{\ell + \epsilon} + 2^{\ell' + \epsilon} < 2^{\ell' + \epsilon} + 2^{\ell' + \epsilon} = 2 \cdot 2^{\ell' + \epsilon} < N. $$

Since $x \cdot c + y$ would always fall in $[0, N)$, $\textsf{Paillier}.\textsf{Decrypt}$ always yields correct results.

Warning

Issue 3b: In round 1, $k_i$ used to compute $K_i$ is unbounded. Impact: $\mathbf{P}_i$ can leak the key share of $\mathbf{P}_j$ ($j \neq i$) in one go.

By setting $k_i := 2^{\ell' + \epsilon}$, they could receive $\hat \alpha_{ij} := x_j \cdot k_i + \hat \beta_{ji} = 2^{\ell' + \epsilon} \cdot x_j + \hat\beta_{ji}$. Since $\hat\beta_{ji} \in [0, 2^{\ell' + \epsilon})$, $\mathbf{P}_i$ retrieves $\mathbf{P}_j$'s key share $x_j$ with $x_j = \lfloor \hat \alpha_{ij} / 2^{\ell' + \epsilon} \rfloor$.

CGGMP introduces a range proof $\psi_{ji}^0$ to make sure that $k_i \in [0, 2^{\ell + \epsilon})$.

Note

What is $\Pi^\textsf{enc-elg}$? $\Pi^\textsf{enc-elg}$ is the zero-knowledge proof showing the relation

$$ \begin{aligned} R_\textsf{enc-elg} = \{(\textsf{PUB}, C, X, A; x, \rho, a) \ | \ & C = (1 + N_0)^x \cdot \rho^{N_0}\ \text{mod}\ N_0^2 \\ & \quad \wedge A = (a \cdot G, x \cdot G + a \cdot X) \\ & \quad \wedge x \in [0, 2^{\ell + \epsilon})\}. \end{aligned} $$

This proves that $A = \textsf{ElGamal}.\textsf{Encrypt}({\color{#ffb454}x}, a)$ and $C = \textsf{Paillier}.\textsf{Encrypt}({\color{#ffb454}x}, \rho)$ have the same ${\color{#ffb454}x} \in [0, 2^{\ell + \epsilon})$.

$\textsf{CGGMP}.\textsf{SignV5}$
Warning

Issue 4: In round 4, $\mathbf{P}_i$ could silently send a different $\sigma_i$, failing the signature. Impact: Similar to issue 2a.

The party $\mathbf{P}_i$ sends $\Delta_i := k_i \cdot \Gamma$ and $S_i := \chi_i \cdot \Gamma$, along with the ZKP $\psi_i'$ to show that the $k_i$ used to compute $\Delta_i$ is legitimate, in round 3. It also performs additional checks in round 4 to make sure the pre-signature materials generated (i.e., $\delta = k \cdot \gamma$ and $\chi = k \cdot x$) are valid before they are broadcast.

$\textsf{CGGMP}.\textsf{SignV6}$
Note

What are the checks on the third point in round 4? The correctness is shown below: - $\sum_j \Delta_j = \sum_j k_j \cdot \Gamma = k \cdot (\gamma \cdot G) = (k \cdot \gamma) \cdot G = \delta \cdot G$, and - $\sum_j S_j = \sum_j \chi_j \cdot \Gamma = (k \cdot x) \cdot (\gamma \cdot G) = (k \cdot \gamma) \cdot (x \cdot G) = \delta \cdot X$.

[!WARNING] Non-identifiable aborts in $\delta \cdot G \stackrel{?}{=} \sum_j \Delta_j$ and $\delta \cdot X \stackrel{?}{=} \sum_j S_j$. Note that the checks there are not attributed by any external party. CGGMP has a protocol to identify the culprit. For more details, please read Figure 9 of the CGGMP24 paper. We omit it here for brevity.

Warning

Issue 5: The correctness of the final $\sigma_i$ is not checked. Impact: Similar to issue 2a.

CGGMP introduces an additional check after round 4 to check whether each $\mathbf{P}_j$ sent its $\sigma_j$ correctly.

$\textsf{CGGMP}.\textsf{SignV7}$
Note

Correctness of round 5. $m \cdot \Delta_j + r \cdot S_j = m \cdot (k_j \cdot \Gamma) + r \cdot (\chi_j \cdot \Gamma) = (k_j \cdot m + r \cdot \chi_j) \cdot \Gamma = \sigma_j \cdot \Gamma$.

Securing auxiliary parameters

Note

Difference with the CGGMP protocol The below are the differences between $\textsf{CGGMP}.\textsf{SignV7}$ and the actual CGGMP protocol: 1. CGGMP also computes $G_i := \textsf{Paillier}.\textsf{Encrypt}(\gamma_i, \nu_i)$ and $\psi_{ji}^1 := \Pi^\textsf{enc-elg}((\textsf{PUB}, G_i, Y_i, B_i), (\gamma_i, \nu_i, b_i))$ in round 1, then checks the ZKP in round 2. 2. CGGMP uses the nonce $\gamma$ instead of $k^{-1}$ (the inverse nonce technique). To achieve this, they set $R := \Gamma$ and compute $\sigma_i := \delta^{-1} \cdot (k_i \cdot m + r \cdot \chi_i)\ \text{mod}\ q$.

Now that we have the signing protocol in place, we have to validate the auxiliary parameters (i.e., the Paillier keys and Pedersen parameters). If the parameters are improperly validated, the corresponding ZKPs are simply voided. To be exact:

The "good" Ring-Pedersen parameters

Ring-Pedersen parameters $(\hat N_j, s_j, t_j)$ should satisfy $s_j, t_j \in \mathbb{Z}_{\hat N_j}^*$ and $s_j \in \langle t_j \rangle$ (i.e., there exists $\lambda_j$ such that $s_j = t_j^{\lambda_j}\ \text{mod}\ \hat N_j$).

In the related ZKPs (e.g., $\Pi^\textsf{aff-g}$ and $\Pi^\textsf{enc-elg}$), they often compute $A = s_j^{\color{#ff7b72}x} \cdot t_j^{\color{#ff7b72}y}\ \text{mod}\ \hat N_j$ and publish $A$ as part of the proof. Here $x$ is usually the secret, and $y$ is the blinding factor which is used to hide $x$ from being exposed. If $s_j$ is not generated from $t_j$, it is possible that $x$ could be recovered from $A$.

The "good" Paillier moduli

A Paillier modulus should be a product of two distinct primes. Also, the prime factors should not be small. Having small factors ($\approx 2^{16}$) would lead to leakage of private key shares. An example is the 6ix1een attack.

The new keygen protocol

Below is the largely revamped $\textsf{KeyGenV3}$.

Note

What are the three zero-knowledge proofs $\Pi^\textsf{prm}$, $\Pi^\textsf{mod}$ and $\Pi^\textsf{fac}$? They are the zero-knowledge proof showing the relations

$$ \begin{aligned} & R_\textsf{prm} = \{ (N, s, t; \lambda) \ | \ s = t^\lambda \ \text{mod}\ N \wedge t \in \mathbb{Z}_N^* \wedge \lambda \in \mathbb{Z} \}, \\ & R_\textsf{mod} = \{ (N; p, q) \ | \ p, q\ \text{are distinct primes} \wedge p, q \equiv 3\ (\text{mod}\ 4) \wedge N = p \cdot q \}, \\ & R_\textsf{fac} = \{ (\hat N_0, s_0, t_0, N; p, q) \ | \ N = p \cdot q \wedge p, q \in [0, 2^{\ell + \epsilon} \cdot \sqrt{N}) \}. \end{aligned} $$ Here $(\hat N_0, s_0, t_0)$ are the verifier's Pedersen parameters.

$\textsf{CGGMP}.\textsf{KeyGenV3}$
Warning

$\textsf{CGGMP}.\textsf{KeyGenV3}$ is very different from the actual CGGMP protocol! This is largely different from the actual $\textsf{KeyGen}$ protocol in CGGMP. The Paillier moduli and Pedersen parameters are handled by the additional $\textsf{AuxiliaryInfoAndKeyRefresh}$ protocol, which performs many more validations. The above includes some checks that I think they are more critical. For more details, please refer to figures 6 and 7 in the CGGMP paper.

The auxiliary zero-knowledge proofs

Now we have introduced the protocol, but the crux would be the zero-knowledge proofs. CGGMP24 uses over 10 different ZKP protocols (and we introduced six). We will cover some of them below. For more details, please refer to section 5 and the appendix A in the CGGMP24 paper.

$\Pi^\textsf{fac}$, the small-factor proof

The zero-knowledge proof $\Pi^\textsf{fac}$ proves that $N$ is a product of two integers $p$ and $q$, where $p, q$ are "small" enough.

$$ R_\textsf{fac} = \{ (\hat N_0, s_0, t_0, N; p, q) \ | \ N = p \cdot q \wedge p, q \in [0, 2^{\ell + \epsilon} \cdot \sqrt{N}) \}. $$

Recall that CGGMP uses 2048-bit Paillier moduli $N$, $\ell = 256$ and $\epsilon = 512$. By showing a factor is small, it shows that the other factor is "large enough":

$$ q = \frac{N}{p} > \frac{N}{2^{\ell + \epsilon} \cdot \sqrt{N}} \approx \frac{2^{2048}}{2^{256 + 512 + 1024}} = 2^{256}. $$ $\Pi^\textsf{fac}.\textsf{Proof}((\hat N_0, s_0, t_0, N), (p, q))$

The proof is given by $\psi := (P, Q, A, B, T, z_1, z_2, w_1, w_2, v)$.

$\Pi^\textsf{fac}.\textsf{Verify}((\hat N_0, s_0, t_0, N), \psi)$
Importance of Pedersen parameters $(\hat N_0, s_0, t_0)$ and how secret is leaked

Previously we mentioned that how important $\Pi^\textsf{prm}$ is, now we show a concrete example without the proof:

We could set $s_0 \in \mathbb{Z}_{\hat N_0}^*$ to be a primitive root of $\hat N_0$ and $t_0 = 1$. By picking $\hat N_0$ such that $\phi(\hat N_0)$ has small factors, we could easily compute the discrete logarithms (i.e., we could easily find $x$ such that $a^x = b\ (\text{mod}\ \hat N_0)$).

Hence the verifier could easily find $p$ from $P \equiv s_0^p\ (\text{mod}\ \hat N_0)$ and $q$ from $Q$.

If we are sure that $N$ does not have small factors (ideally at least $2^{256}$), the 6ix1een attack will be eliminated. However, with $\Pi^\textsf{fac}$ alone, we could not achieve that because one could set $p$ and $q$ to be composite numbers that consist of small prime factors. To resolve that, we will also need $\Pi^\textsf{mod}$.

$\Pi^\textsf{mod}$, the Paillier-Blum modulus proof

The zero-knowledge proof $\Pi^\textsf{mod}$ is used to make sure $N = p \cdot q$, and here $p \neq q$ and $p, q$ are both primes. $\Pi^\textsf{mod}$ also requires $p, q \equiv 3\ (\text{mod}\ 4)$ because it is much more efficient to prove. Also $t$ is usually $80$.

$\Pi^\textsf{mod}.\textsf{Prove}(N, (p, q))$

The proof is given by $\psi := (w, (a_i, b_i, x_i, z_i)_{i \in \{1, 2, ..., t\}})$.

$\Pi^\textsf{mod}.\textsf{Verify}(N, \psi)$

It effectively rejects $N$ that

  1. has more than two prime factors by the $x_i$ check.

  2. is not squarefree by the $z_i$ check. If $N$ is not squarefree (i.e., $N = p^2 \cdot r$ for some factor $p$), then $\text{GCD}(N, \phi(N))$ is a multiple of $p$. Thus the prover could not compute $d$, which makes it hard to compute the $z_i$.

$\Pi^\textsf{enc-elg}$, the range proof with El-Gamal commitment

Recall that $\Pi^\textsf{enc-elg}$ proves the relationship

$$ \begin{aligned} R_\textsf{enc-elg} = \{(\textsf{PUB}, C, X, A; x, \rho, a) \ | \ & C = (1 + N_0)^x \cdot \rho^{N_0}\ \text{mod}\ N_0^2 \\ & \quad \wedge A = (a \cdot G, x \cdot G + a \cdot X) \\ & \quad \wedge x \in [0, 2^{\ell + \epsilon})\}, \end{aligned} $$

which needs $C = \textsf{Paillier}.\textsf{Encrypt}(x, \rho)$ and $A = \textsf{ElGamal}.\textsf{Encrypt}(x, a)$ to share the same $x$.

$\Pi^\textsf{enc-elg}.\textsf{Prove}((\textsf{PUB}, C, X, (A_1, A_2)), (x, \rho, a))$

The proof is given by $\psi := (S, T, D, Y, Z, z_1, z_2, z_3, w)$.

$\Pi^\textsf{enc-elg}.\textsf{Verify}((\textsf{PUB}, C, X, (A_1, A_2)), \psi)$

Conclusion

This blogpost summarizes how a threshold ECDSA protocol, CGGMP24, is implemented. It involves a handful of zero-knowledge proofs which are central to ensuring the correctness of the auxiliary parameters, thus the protocol.

Threshold ECDSA is powerful that no one holds the private key, thus an attacker must compromise a threshold number of parties simultaneously. However, it is easy to make mistakes while implementing - and a single bug in the zero-knowledge proofs (e.g., a missing check somewhere) would be disastrous.

  1. As the paper mentions, CGGMP can be converted into a $t$-of-$n$ scheme with $t < n$. ↩

  2. It is usually the hash of the message, but here we'll be calling it the message for simplicity. ↩

  3. https://std.neuromancer.sk/secg/secp256k1/ ↩

  4. cmp_ecdsa_signing_service.cpp#L114 passes sizeof(elliptic_curve256_scalar_t) (32 bytes) to be the secret size of mta::answer_mta_request. ↩

  5. mta.cpp#L713 passes secret_size * BETA_HIDING_FACTOR bytes of randomness for beta. Here BETA_HIDING_FACTOR = 5. ↩

  6. cmp_setup_service.cpp#L22 defines the PAILLIER_KEY_SIZE to be 2048 bits. ↩

  7. The probability that $k_j \in [0, 2^{240})$ for all $j \neq i$ is around $1 / 2^{16 \cdot (n-1)}$ if there are $n$ parties, so this would be feasible if there are fewer parties. ↩

zkSecurity offers auditing, research, and development services for cryptographic systems including zero-knowledge proofs, MPCs, FHE, consensus protocols and more.

Learn More →

Latest Posts

zkao 2.0 is here

zk/sec, False Witness team July 24, 2026
zkao security zk AI announcement

zkao 2.0 is out: a complete redesign of our continuous security scanning tool, a new pay-as-you-go model that replaces subscriptions, and a long list of improvements across scanning, triaging, and reporting.

Archetype x zkSecurity - Proof is in the Pudding: Groth16

ZK/SEC July 23, 2026
educative zk groth16

In Session 10 of "Proof is in the Pudding," we work backward from Groth16's famously compact verifier equation to explain why the protocol is shaped the way it is. We cover how R1CS constraints become polynomial identities, why pairings are needed to multiply hidden commitments, how random linear combinations and the Schwartz-Zippel lemma enforce witness consistency, and how the separating factors gamma and delta restrict which pieces of the CRS a prover can use.

AI meets Cryptography 3: What AI Found in Bron Labs's bron-crypto

Stefanos Chaliasos, Hao Pham, False Witness Team July 22, 2026
security crypto AI zkao audit mpc

We pointed our AI audit pipeline at bron-crypto, Bron Labs's Go library for MPC and threshold signatures, and confirmed four bugs. All of them are now fixed upstream. This is the third post in our series on bugs our agents found across open source cryptography.

Recommended Reading

Announcing mpcsec.org: What Goes Wrong When You Implement MPC

ZK/SEC May 25, 2026
educative security MPC

mpcsec.org is a new collaborative reference for common pitfalls in MPC implementations and the cryptographic primitives they rely on, built with contributors from zkSecurity, Trail of Bits, Partisia, and Zama. If you build, audit, or deploy threshold signatures, distributed key generation, or other MPC protocols, it's a starting point for the mistakes you don't want to repeat.

zkSecurity x Bain Capital (Whiteboard Session): Unveiling the Power of Multi-Party Computation

ZK/SEC June 04, 2024
educative MPC

We're thrilled to share that we're featured in Bain Capital Crypto's Whiteboards series! In the first episode, David and Guillermo Angeris dive deep into the intriguing world of Multi-Party Computation (MPC). Join them as they break down complex concepts like additively-shared secrets and Shamir Secret Sharing, making the cutting-edge tech behind MPC accessible and engaging. Check out the full episode for some engaging insights and reach out to us if you're looking for MPC stack auditors!

New on mpcsec.org: An MPC Bug Tracker, Templates, and a Cleaner UI

ZK/SEC June 25, 2026
educative security MPC

A month after launching mpcsec.org, we added a searchable tracker of real-world MPC bugs, expanded the pitfall taxonomy, published contribution templates and refreshed the site UI.

More to Explore

Archetype x zkSecurity - Proof is in the Pudding: The Other Dark Forest (Offchain Public Keys)

ZK/SEC October 21, 2025
educative zk

In Session 07 of "Proof is in the Pudding," we explore the other dark forest, the realm of offchain public keys. We dive into zkLogin, ZK Email, and ZKPassport, examining how these protocols handle authentication and privacy. We also discuss the issue of unlinkability in privacy protocols and why replacing traditional signature verifications with zero-knowledge proofs could unlock more interesting and powerful ZK products.

Public report of Sui's zkLogin audit

ZK/SEC November 07, 2023
security zk

We just finished an audit of the Sui Foundation's zkLogin application and we're sharing what we found: the code is well-documented, tested, and specified. The zkLogin is set to make user authentication on the blockchain secure but simple, replacing cryptographic keys with familiar SSO methods like Google or Facebook while preserving user privacy. We also dive into the technical details behind JWT verification, non-native arithmetic for RSA, and vector programming. Plus, learn about the trusted setup process for zkLogin, ensuring maximum security through a decentralized multi-party ceremony. If you're curious about the intricate mechanics behind zkLogin, this is a must-read.

ZK programmability adds a whole new layer to worry about

David Wong May 31, 2023
announcement security zk

Zero-knowledge (ZK) programs are revolutionizing how developers can build secure systems by proving execution without exposing data, making them incredibly useful for privacy and security. However, they come with their own set of challenges. In this blog, we delve into these security implications and offer practical strategies to help developers navigate the risks. From understanding private inputs to the intricacies of proof systems and trusted setups, we unpack the complexities and provide insights on how to address potential pitfalls, ensuring you're well-prepared to harness the power of ZK programs effectively.
View all articles