0x

MPC / TSS

Multiparty Computation for Threshold Signatures

Notation & Setting

\text{Finite field } \mathbb{F}_q,\ q\ \text{prime};\ \langle G\rangle\ \text{elliptic-curve group of order } q;\ \text{scalars in } \mathbb{Z}_q.

\text{Parties } P_1,\dots,P_n;\ \text{threshold } t;\ I\subseteq\{1,\dots,n\},\ |I|=t.

\text{ECDSA key: } x\in\mathbb{Z}_q,\ Q=xG;\ \text{hash } H:\{0,1\}^\*\to \mathbb{Z}_q.

Lagrange Interpolation

Let $f(X)\in\mathbb{F}_q[X]$ with $\deg f\le t-1$ . For distinct nonzero indices $I=\{i_1,\dots,i_t\}\subseteq\mathbb{F}_q^\*$ :

\lambda_i^{(I)}(0)= \prod_{\substack{j\in I\\ j\neq i}}\frac{0-j}{i-j}\in\mathbb{F}_q, \qquad f(0)=\sum_{i\in I}\lambda_i^{(I)}(0)\,f(i).

This simple identity lets any $t$ parties reconstruct the constant term of a polynomial, while fewer learn nothing.

Try moving the points around to see how the polynomial changes:

Lagrange Interpolation

Simplification for $t=2$

For $I=\{i,j\},\ i\neq j$ :

\lambda_i^{(\{i,j\})}(0)=\frac{-j}{i-j},\qquad \lambda_j^{(\{i,j\})}(0)=\frac{-i}{j-i}.

Shamir’s Secret Sharing (SSS)

SSS, or Shamir's Secret Sharing, is a cryptographic protocol that allows a secret to be split into multiple shares, such that the secret can only be reconstructed when a sufficient number of shares are combined. The protocol is designed to be secure even if some of the shares are compromised.

It was invented by Adi Shamir in 1979 in his paper How to share a secret.

SSS is based on polynomial interpolation, where the secret is the y-intercept of the polynomial. The shares are the y-values of the polynomial at different x-values.

Sharing:

f(X)=s+a_1 X+\cdots+a_{t-1}X^{t-1},\quad a_j\in\mathbb{F}_q.

Party $P_i$ receives $v_i=f(i)$ .

Reconstruction:

s=f(0)=\sum_{i\in I}\lambda_i^{(I)}(0)\,v_i.

Dealerless:

DKG

Verifiable Secret Sharing (VSS)

VSS, or Verifiable Secret Sharing, is a cryptographic protocol that allows a secret to be split into multiple shares, such that the secret can only be reconstructed when a sufficient number of shares are combined. The protocol is designed to be secure even if some of the shares are compromised.

It was invented by Feldman in 1987.

VSS is similar to SSS, but with the additional property that the shares can be verified to be correct. This is done by attaching a proof to each share, which can be used to verify that the share is consistent with the other shares.

Feldman VSS

C_j=g^{a_j},\qquad g^{v_i}\stackrel{?}{=}\prod_{j=0}^{t-1}C_j^{i^j}.

Pedersen VSS

C_j=g^{a_j}h^{b_j}.

VSS ensures consistency of shares and thwarts malicious dealers.

Distributed Key Generation (DKG)

Distributed Key Generation (DKG) is a cryptographic protocol that allows a group of parties to generate a shared public key without revealing their private keys. The protocol is designed to be secure even if some of the parties are malicious.

Each party $P_\ell$ runs VSS for its polynomial $f^{(\ell)}(X)$ . Parties add up:

f(X)=\sum_{\ell=1}^n f^{(\ell)}(X),\quad x=f(0).

Public key $Q=xG$ is computable from commitments.

Mathematical steps of complaint-based DKG:

Commitments,
Share distribution,
Verification → complaints,
Complaint resolution → disqualification,
Aggregation over honest dealers,
Final secret and public key,
Lagrange interpolation for reconstruction.

1) Dealer’s local polynomial and commitments

For each dealer $\ell \in \{1,\dots,n\}$ :

Feldman VSS

f^{(\ell)}(X) = \sum_{j=0}^{t-1} a^{(\ell)}_j X^j, \qquad C^{(\ell)}_j = g^{\,a^{(\ell)}_j}\ \ (j=0,\dots,t-1).

Pedersen VSS (hiding + binding)

f^{(\ell)}(X) = \sum_{j=0}^{t-1} a^{(\ell)}_j X^j, \quad r^{(\ell)}(X) = \sum_{j=0}^{t-1} b^{(\ell)}_j X^j,

C^{(\ell)}_j = g^{\,a^{(\ell)}_j}\, h^{\,b^{(\ell)}_j}\ \ (j=0,\dots,t-1).

2) Distributed shares

For each receiver $P_i$ :

Feldman

v^{(\ell)}_i = f^{(\ell)}(i).

Pedersen

v^{(\ell)}_i = f^{(\ell)}(i), \qquad \rho^{(\ell)}_i = r^{(\ell)}(i).

3) Local verifiability (basis of complaints)

Feldman check

g^{\,v^{(\ell)}_i} \stackrel{?}{=} \prod_{j=0}^{t-1} \big(C^{(\ell)}_j\big)^{\,i^j}.

Pedersen check

g^{\,v^{(\ell)}_i}\, h^{\,\rho^{(\ell)}_i} \stackrel{?}{=} \prod_{j=0}^{t-1} \big(C^{(\ell)}_j\big)^{\,i^j}.

If this equation does not hold (or the share never arrives), party $P_i$ raises a complaint against dealer $\ell$ .

4) Complaint resolution and disqualification

If dealer $\ell$ can open/prove that the disputed share is valid, the complaint is dismissed.
Otherwise, mark $\ell$ as faulty and disqualify it.

Formal rule (Pedersen; Feldman is the same without the $h$ -term):

\exists\ i \text{ honest such that}\ g^{\,v^{(\ell)}_i}\,h^{\,\rho^{(\ell)}_i} \neq \prod_{j=0}^{t-1}\big(C^{(\ell)}_j\big)^{\,i^j} \quad \Longrightarrow\quad \ell \in \mathcal{B}.

5) Aggregation (keeping only honest dealers $\mathcal\{H\} = [n]\setminus \mathcal\{B\}$ )

Global polynomial and shares

f(X) = \sum_{\ell\in\mathcal{H}} f^{(\ell)}(X), \qquad v_i = \sum_{\ell\in\mathcal{H}} v^{(\ell)}_i = f(i).

Aggregated commitments

C_j = \prod_{\ell\in\mathcal{H}} C^{(\ell)}_j \quad (j=0,\dots,t-1).

Verification (Pedersen form)

g^{\,v_i}\, h^{\,\rho_i} \stackrel{?}{=} \prod_{j=0}^{t-1} C_j^{\,i^j}, \qquad \rho_i = \sum_{\ell\in\mathcal{H}} \rho^{(\ell)}_i.

6) Global secret and public key

The final secret is

x = f(0) = \sum_{\ell\in\mathcal{H}} a^{(\ell)}_0.

If commitments are curve-based, the public key is $Q = xG = \sum_{\ell\in\mathcal{H}} a^{(\ell)}_0 G.$

In Feldman’s exponent form, $C_0 = \prod_{\ell\in\mathcal{H}} C^{(\ell)}_0 = g^{\,x}.$

7) Lagrange interpolation (for reconstruction or signing subsets)

For any $I \subseteq \{1,\dots,n\}$ with $|I|=t$ :

\lambda_i^{(I)}(0) = \prod_{\substack{j\in I\\ j\neq i}}\frac{0-j}{\,i-j\,}, \qquad f(0) = \sum_{i\in I} \lambda_i^{(I)}(0)\, v_i.

Special case $t=2$ , $I=\{i,j\}$ :

\lambda_i^{(\{i,j\})}(0) = \frac{-j}{\,i-j\,}, \qquad \lambda_j^{(\{i,j\})}(0) = \frac{-i}{\,j-i\,}.

Sequence (complaint-based DKG):

Complaint-based DKG (math sketch).
Each dealer $\ell$ broadcasts commitments $C^{(\ell)}_j = g^{a^{(\ell)}_j}\ (j=0,\dots,t-1),$ and sends shares $v^{(\ell)}_i = f^{(\ell)}(i)$ .

Each receiver checks $g^{v^{(\ell)}_i} \stackrel{?}{=} \prod_{j=0}^{t-1}\big(C^{(\ell)}_j\big)^{i^j},$ complains if it fails, and faulty dealers are disqualified.
Honest contributions are aggregated: $f(X)=\sum_{\ell\in\mathcal{H}} f^{(\ell)}(X),\quad x=f(0),\quad Q=xG.$

Threshold ECDSA as MPC

ECDSA signature:

R=kG,\quad r=R_x\bmod q,\qquad s=k^{-1}(H(m)+rx)\bmod q.

Both $x$ and $k$ are shared. MPC must handle multiplication and inversion securely. Paillier-based MtA protocols + ZK proofs solve this.

{2,2} ECDSA — Lindell-17

Steps

Sample $k_A,k_B$ ; compute $R=(k_A+k_B)G,\ r=R_x$ .
Use Paillier MtA to get additive shares of $r\cdot x$ and $k$ .
Combine to $s$ .

s=(\,\beta_A+\beta_B\,)^{-1}\big(H(m)+\alpha_A+\alpha_B\big)\bmod q.

Sequence

{2,n} — production pattern

From DKG with degree-1 polynomial:

x^{(i)}=\lambda_i^{(\{i,j\})}(0)v_i,\quad x^{(j)}=\lambda_j^{(\{i,j\})}(0)v_j,\quad x^{(i)}+x^{(j)}=x.

Then run Lindell-17 as a 2PC signer.

Sequence

{t,n} — general threshold

DKG: dealerless, robust.
Preprocessing: many presignatures via MtA + ZKs.
Online: short signing with $t$ parties.
Identifiable aborts: pinpoint cheaters.

Sequence

ECDSA Verification

u_1=H(m)s^{-1},\quad u_2=rs^{-1},\quad V=u_1G+u_2Q,\quad r\equiv x\text{-coord}(V)\pmod q.

Threshold signatures must satisfy the exact same equation.

Minimal Interfaces

type Share = struct { idx: int ; val: Fq }
type PreSign = opaque
 
interface DKG {
  run(t, n) -> (shares: Share[n], Q: ECPoint)
}
 
interface TwoPartySign {
  sign(xA_share, xB_share, m) -> (r, s)
}
 
interface TN_Sign {
  preprocess(M: int) -> PreSign[M]
  sign(m, I: set<int> with |I|=t, presign: PreSign) -> (r, s)
}

Worked Mini-Examples

Lagrange example (t=2)

Indices $I=\{1,3\}$ :

\lambda_1=\tfrac{-3}{1-3}=\tfrac{3}{2},\quad \lambda_3=\tfrac{-1}{3-1}=\tfrac{-1}{2}.

Reconstruction:

f(0)=\tfrac{3}{2}v_1+(-\tfrac{1}{2})v_3\pmod q.

{2,2} structure

\alpha_A+\alpha_B=r x,\quad \beta_A+\beta_B=k,

s=(\beta_A+\beta_B)^{-1}(H(m)+\alpha_A+\alpha_B)\pmod q.

Summary

Polynomials are used because any $t$ points determine a degree $(t-1)$ curve.
VSS prevents malicious dealers from derailing the protocol.
Schnorr threshold (FROST) is simpler, but blockchains often require ECDSA.
Identifiable aborts give governance evidence against misbehaving signers.

Parameterization Guide

Curves

Bitcoin/Ethereum: secp256k1 (q ≈ 2^256).
Enterprise / NIST standards: P-256, P-384.
Experimental / EdDSA-style: Ed25519 (different signing equation, simpler threshold).

Paillier parameters

Use modulus ≥ 2048 bits (3072+ for long-term).
Secure key generation must be joint (two-party or multi-party).
Homomorphic encryption cost dominates preprocessing.

Zero-knowledge proofs

Range proofs: ensure encrypted values are in $[0,q)$ .
Typical bit length: 256–384 bits (depends on curve).
Sigma protocols or Bulletproofs; trade size vs performance.

Preprocessing

Presignature batch size: tune to traffic (e.g., hundreds cached).
Online signing: 2–4 rounds, tens of ms latency in practice.
Refresh interval: periodic VSS refresh (weeks to months).

Operational choices

{2,2} for small custodial pairs (HSM + server).
{2,n} for flexible hot-wallet fleets.
{t,n} for large institutions with governance rules (5-of-7, 10-of-15).

Appendix: A Brief History

MPC evolved from theory (1980s) → verifiable primitives (1990s) → efficient protocols (2010s) → real-world threshold ECDSA (2017+).

1970s: Early Building Blocks

1979 — Shamir’s Secret Sharing (SSS)
Secret sharing using polynomials and Lagrange interpolation: any (t) shares reconstruct the secret, fewer reveal nothing. Foundation for all later threshold cryptography.

1980s: Feasibility and Completeness

1982 — Andrew Yao: Defined secure two-party computation in Protocols for Secure Computations. Introduced the “Millionaires’ Problem.”
1986 — Yao again: Garbled circuits (How to Generate and Exchange Secrets), enabling general 2PC.
1987 — GMW (Goldreich–Micali–Wigderson): Showed that, with an honest majority, any function can be securely computed.
1988 — BGW & CCD: Unconditional security for MPC with less than one-third corruptions. BGW emphasized interpolation; CCD introduced simulation-based security.

1990s: Verifiability and Preprocessing

1991 — Pedersen VSS: Perfectly hiding, binding commitments for verifiable secret sharing.
1991 — Beaver triples: Preprocessing multiplication triples, enabling fast online MPC.
1999 — Paillier encryption: Additively homomorphic encryption, crucial for later ECDSA threshold protocols.

Late 1990s–2000s: DKG and OT

1999/2007 — GJKR DKG: Robust distributed key generation with uniform distribution.
2003 — IKNP OT extension: Reduced cost of Oblivious Transfer, making large-scale GC/OT-based MPC practical.

2010–2014: From Theory to Engineering

2011 — BDOZ: Preprocessing techniques for efficient malicious MPC.
2012 — TinyOT: Lightweight authenticated sharing for Boolean circuits.
2012 — SPDZ: MAC-authenticated shares, heavy preprocessing but extremely fast online phase.

2017+: Threshold ECDSA Becomes Practical

2017 — Lindell: First efficient 2PC ECDSA, practical for wallets/HSMs.
2018 — GG18: General ((t,n)) threshold ECDSA with dealerless DKG.
2020 — CGGMP: UC-secure, identifiable aborts, proactive refresh.
2021–2024: Optimizations, batch proofs, real-world deployments.

MPC / TSS

Notation & Setting

Lagrange Interpolation

Simplification for t=2t=2t=2

Shamir’s Secret Sharing (SSS)

Verifiable Secret Sharing (VSS)

Feldman VSS

Pedersen VSS

Distributed Key Generation (DKG)

1) Dealer’s local polynomial and commitments

2) Distributed shares

3) Local verifiability (basis of complaints)

4) Complaint resolution and disqualification

5) Aggregation (keeping only honest dealers {H}=[n]∖{B}\mathcal\{H\} = [n]\setminus \mathcal\{B\}{H}=[n]∖{B})

6) Global secret and public key

7) Lagrange interpolation (for reconstruction or signing subsets)

Sequence (complaint-based DKG):

Threshold ECDSA as MPC

{2,2} ECDSA — Lindell-17

Steps

Sequence

{2,n} — production pattern

Sequence

{t,n} — general threshold

Sequence

ECDSA Verification

Minimal Interfaces

Worked Mini-Examples

Lagrange example (t=2)

{2,2} structure

Summary

Parameterization Guide

Curves

Paillier parameters

Zero-knowledge proofs

Preprocessing

Operational choices

Appendix: A Brief History

Simplification for $t=2$

5) Aggregation (keeping only honest dealers $\mathcal\{H\} = [n]\setminus \mathcal\{B\}$ )