# Threshold ECDSA¶

Threshold signature schemes enable sharing signing power amongst n parties such that any subset of t + 1 can jointly sign, but any smaller subset cannot.

## I Model, Definitions and Tools¶

### 1.1 Model¶

**Communication Model**¶

We assume that our computation model is composed of a set of \(n\) players \(P_1,\cdots, P_n\) connected by a complete network of point-to-point channels and a broadcast channel.

**The Adversary**¶

We assume that an adversary, \(A\), can corrupt up to \(t\) of the \(n\) players in the network. \(A\) learns all the information stored at the corrupted nodes, and hears all the broadcasted messages. We consider two type of adver saries:

### 1.2 Deﬁnitions¶

**Signature Scheme**¶

A signature scheme \(S\) is a triple of eﬃcient randomized algorithms \((Key-Gen, Sig, Ver)\).

**Key-Gen**is the key generator algorithm.on input the security parameter \(1^\lambda\) , it outputs a pair \((y, x)\), such that \(y\) is the public key and \(x\) is the secret key of the signature scheme.

**Sig**is the signing algorithm:on input a message m and the secret key \(x\), it outputs \(sig\), a signature of the message \(m\).

Since \(Sig\) can be a randomized algorithm there might be several valid signatures \(sig\) of a message \(m\) under the key \(x\); with \(Sig(m, x)\) we will denote the set of such signatures

**Ver**is the veriﬁcation algorithm.On input a message \(m\), the public key \(y\), and a string \(sig\), it checks whether \(sig\) is a proper signature of \(m\), i.e. if \(sig \in Sig(m, x)\).

#### Threshold secret sharing¶

Given a secret value \(x\) we say that the values \((x_1 , \cdots , x_n)\) constitute a \((t, n)\)-threshold secret sharing of \(x\) if \(t\) (or less) of these values reveal no information about \(x\), and if there is an eﬃcient algorithm that outputs \(x\) having \(t + 1\) of the values \(x_i\) as inputs.

#### Threshold signature schemes.¶

Let \(S=(Key-Gen, Sig, Ver)\) be a signature scheme. A \((t, n)\)-threshold signature scheme \(TS\) for \(S\) is a pair of protocols \((Thresh-Key-Gen, Thresh-Sig)\) for the set of players \(P_1 , \cdots, P_n\) .

**Thresh-Key-Gen**is a distributed key generation protocol used by the players to jointly generate a pair \((y, x)\) of public/private keys on input a security parameter \(1^\lambda\) .**Thresh-Sig**is the distributed signature protocol. The private input of \(P_i\) is the value \(x_i\) . The public inputs consist of a message m and the public key \(y\). The output of the protocol is a value \(sig \in Sig(m, x)\).

### 1.3 Tools¶

#### Additively Homomorphic Encryption¶

We assume the existence of an encryption scheme E which is additively homo- morphic modulo a large integer \(N\), One instantiation of a scheme with these properties is **Paillier’s encryption scheme**.

ref: [Paillier’s encryption scheme](https://ryankung.github.io/klefki/Paillier’s%20encryption%20Scheme.html)

With \(\oplus_{i=1}^{t+1}\)a_i, we denote the summation over the addition operation \(+_E\) of the encryption scheme:

#### Threshold Cryptosystems¶

In a \((t, n)\)-threshold cryptosystem, there is a public key \(pk\) with a matching secret key \(sk\) which is shared among \(n\) players with a \((t, n)\)-secret sharing.

When a message \(m\) is encrypted under \(pk\), \(t+1\) players can decrypt it via a communication protocol that does not expose the secret key.

More formally, a public key cryptosystem \(\epsilon\) is deﬁned by three eﬃcient algorithms:

key generation

**Enc-Key-Gen**that takes as input a security parameter \(λ\), and outputs a public key \(pk\) and a secret key \(sk\).An encryption algorithm

**Enc**that takes as input the public key \(pk\) and a message \(m\), and outputs a ciphertext \(c\). Since**Enc**is a randomized algorithm, there will be several valid encryptions of a message \(m\) under the key \(pk\); with \(Enc(m, pk)\) we will denote the set of such ciphertexts.And a decryption algorithm Dec which is run on input \(c\), \(sk\) and outputs \(m\), such that \(c \in Enc(m, pk)\).

A \((t, n)\) threshold cryptosystem \(T\epsilon\), consists of the following protocols for \(n\) players \(P_1 , \cdots , P_n\).

A key generation protocol

**TEnc-Key-Gen**that takes as input a security parameter \(\lambda\), and the parameter \(t, n\), and it outputs a public key \(pk\) and a vector of secret keys \((sk_1, \cdots, sk_n)\) where \(sk_i\) is private to player \(P_i\) . This protocol could be obtained by having a trusted party run Enc-Key-Gen and sharing sk among the players.A threshold decryption protocol

**TDec**, which is run on public input a ciphertext \(c\) and private input the share \(sk_i\) . The output is \(m\), such that \(c\in Enc(m, pk)\).

Threshold variations of Paillier’s scheme have been presented in the literature:

Baudron, P.-A. Fouque, D. Pointcheval, G. Poupard and J. Stern. Practical Multi-Candidate Election System. PODC’01

Damg˚ard and M. Jurik. A Generalisation, a Simpliﬁcation and Some Appli- cations of Paillier’s Probabilistic Public-Key System. PKC’01, LNCS Vol.1992, pp.119–136

Damg˚ard, M. Koprowski: Practical Threshold RSA Signatures without a Trusted Dealer. EUROCRYPT 2001: LNCS Vol.2045, pp. 152-165

Hazay, G.L. Mikkelsen, T. Rabin, T. Toft. and A.A. Nicolosi: Eﬃcient RSA key generation and threshold Paillier in the two-party setting.

#### Independent Trapdoor Commitments¶

A trapdoor commitment scheme allows a sender to commit to a message with information-theoretic privacy.

A (non-interactive) **trapdoor commitment scheme** consists of four algorithms \(KG, Com, Ver, Equiv\) with the following properties:

\(KG\) is the key generation algorithm, on input the security parameter it outputs a pair \(pk, tk\) where \(pk\) is the public key associated with the commitment scheme, and \(tk\) is called the

**trapdoor**.

\(Com\) is the commitment algorithm. On input pk and a message M it outputs \([C(M), D(M)] = Com(pk, M, R)\) where \(r\) are the coin tosses. \(C(M)\) is the commitment string, while \(D(M)\) is the decommitment string which is kept secret until opening time.

\(Ver\) is the veriﬁcation algorithm. On input \(C, D\) and \(pk\) it either outputs a message M or \(\bot\).

\(Equiv\) is the algorithm that opens a commitment in any possible way given the trapdoor information. It takes as input \(pk\), strings \(M, R\) with \([C(M), D(M)] = Com(pk, M, R)\), a message \(M' \neq M\) and a string \(T\). If \(T = tk\) then \(Equiv\) outputs \(D'\) such that \(Ver(pk, C(M), D') = M'\) .

We note that if the sender refuses to open a commitment we can set \(D = \bot\) and \(Ver(pk, C, \bot) = \bot\). Trapdoor commitments must satisfy the following properties:

**Correctness:**If \([C(M), D(M)] = Com(pk, M, R)\) then \(Ver(pk, C(M), D(M)) = M\).

**Information Theoretic Security:**For every message pair \(M, M'\) the distributions \(C(M\)) and \(C(M')\) are statistically close.

**Secure Binding:**We say that an adversary \(A\) wins if it outputs \(C, D, D'\) such that \(Ver(pk, C, D) = M, Ver(pk, C, D') = M'\) and \(M \neq M'\) . We require that for all eﬃcient algorithms \(A\), the probability that \(A\) wins is negligible in the security parameter.

**Independence:**if the honest parties open their commitments in diﬀerent ways using the trapdoor, the adversary cannot change the way he opens his commitments C_j based on the honest parties’ opening.

## II Scheme of GG16¶

### Initialization phase¶

In this phase, a common reference string containing the public information \(pk\) for an independent trapdoor commitment \(KG\), \(Com\), \(Ver\), \(Equiv\) is selected and published. This could be accomplished by a trusted third party, who can be assumed to erase any secret information (i.e. the trapdoor of the commitment) after selection.

The common parameters \(G, g, q\) for the DSA scheme are assumed to be known.

### Key generation protocol¶

```
[1]:
```

```
from klefki.types.algebra.concrete import EllipticCurveCyclicSubgroupSecp256k1 as ECC
from klefki.types.algebra.concrete import EllipticCurveGroupSecp256k1 as Cruve
from klefki.types.algebra.concrete import FiniteFieldCyclicSecp256k1 as CF
from klefki.types.algebra.concrete import FiniteFieldSecp256k1 as F
from klefki.zkp.pedersen import PedersonCommitment
from klefki.types.algebra.utils import randfield
from klefki.bitcoin.address import gen_address
```

Here we describe how the players can jointly generate a DSA key pair \((x, y = g_x)\) with \(y\) public and \(x\) shared among the players.

The idea is to generate a public key \(E\) for an additively \((\mod N)\) homomorphic encryption scheme \(E\), together with the secret key \(D\) in shared form among the players.

The value \(N\) is is chosen to be larger than \(q^8\)

```
[2]:
```

```
from klefki.crypto.paillier import Paillier
from klefki.zkp.pedersen import PedersonCommitment, com as commit
from functools import partial
from klefki.types.algebra.concrete import FiniteFieldCyclicSecp256k1 as CF
from klefki.numbers.primes import generate_prime
from functools import reduce
from operator import mul, add
```

```
[3]:
```

```
q = CF(CF.P)
```

```
[4]:
```

```
P = generate_prime(1024)
Q = generate_prime(1024)
Pai = Paillier(P, Q)
E, D = Pai.E, Pai.D
```

Then a value \(x\) is generated, and encrypted with E, with the value \(α = E(x)\) made public.

Note that this is an implicit \((t, n)\) secret sharing of \(x\), since the decryption key of \(E\) is shared among the players.

Each player \(P_i\) selects a random value \(x_i ∈ Z_q\) , computes \(y_i\) = \(g^{x_i} ∈ G\) and \([C_i , D_i ] = Com(y_i)\);

```
[5]:
```

```
G = ECC.G
n = 3
xs = [randfield(CF) for _ in range(n)]
ys = [G ** x for x in xs]
trap = randfield(CF)
H = G ** trap
com = partial(PedersonCommitment, H=H, G=G)
coms = [com(x=y.value[0], r=y.value[1]) for y in ys]
```

```
[6]:
```

```
x = reduce(add, xs)
```

Each player \(P_i\) broadcast \(C_i\)

\(D_i\) which allows everybody to compute \(y_i = Ver(C_i , D_i )\)

\(\alpha_i=E(x_i);\)

a ZK argument \(\Pi_i\) that states

\(\exists \mu=y_i\)

\(D(a_i)=\mu\)

If any of the ZK arguments fails, the protocol terminates.

```
[7]:
```

```
all([c.C == commit(H=H, G=G, *c.D) for c in coms])
```

```
[7]:
```

```
True
```

```
[8]:
```

```
from operator import mul
from klefki.types.algebra.meta import field
```

```
[9]:
```

```
from operator import add
from functools import reduce
alpha = reduce(mul, [E(x.value) for x in xs])
y = reduce(add, ys)
FN = alpha.functor
```

proof

```
[10]:
```

```
assert CF(D(alpha)) == reduce(add, xs) == x
assert G ** CF(D(alpha)) == y
```

The players compute \(\alpha=\oplus_{i=1}^{t+1}a_i\) and \(y=\sum_{i=1}^{t+1}y_i\)

### Signature Generation¶

The signature generation protocol is run on input \(m\) (the hash of the message \(M\) being signed)

```
[11]:
```

```
from klefki.utils import to_sha256int
m = CF(to_sha256int("Hello Threshold ECDSA"))
```

#### Round 1¶

Each player \(P_i\)

choose \(\rho_i \leftarrow Z_q\)

compute \(u_i=E(\rho_i)\) and \(v_i=p_i \times_E\alpha = E(\rho_ix)\)

compute \([C_{1,i}, D_{i,i}]=Com([u_i, v_i])\) and broadcast \(C_{1,i}\)

```
[12]:
```

```
ps = [randfield(CF) for _ in range(n)]
us = [E(p) for p in ps]
vs = [alpha ** p for p in ps]
coms1 = [com(x=t[0], r=t[1]) for t in zip(us, vs)]
```

#### Round 2¶

Each player \(P_i\) broadcasts:

\(D_{1,i}\). This allow everybody to compute \([u_i, v_i]=Ver(C_{1,i}, D_{1,i})\)

a zero-knowledge argument \(\Pi_{1,i}\) which states

\(\exists \eta \in [-q^3,q^3]\) such that

\(D(u_i)=\eta\)

\(D(v_i)=\eta D(E(x)\)

Players compute \(u=\oplus_{i=1}^{t+1}u_i=E(\rho)\) and \(v=\oplus_{i=1}^{t+1}v_i=E(\rho x)\), where \(\rho=\sum_{i=1}^{1+1}\rho_i\)

```
[13]:
```

```
all([c.C == commit(H=H, G=G, *c.D) for c in coms1])
```

```
[13]:
```

```
True
```

```
[14]:
```

```
u = reduce(mul, us)
v = reduce(mul, vs)
```

proof

```
[15]:
```

```
assert CF(D(u)) == reduce(add, (ps))
```

```
[16]:
```

```
assert CF(D(alpha ** ps[1])) == x * ps[1]
```

```
[17]:
```

```
assert CF(D(alpha ** ps[0] * alpha ** ps[1] * alpha ** ps[2])) == x * (ps[0] + ps[1] + ps[2]) == CF(D(v))
```

```
[18]:
```

```
assert CF(D(v)) == CF(D(E(reduce(add, ps) * x)))
```

#### Round 3¶

Each player \(P_i\)

choose \(k_i \in Z_q\) and \(c_i \in R[-q^6, q^6]\)

computes \(r_i=g^{k_i}\) and \(w_i=(k_i\times_E u) +_E E(c_iq)=E(k_i\rho+c_iq))\)

computes \([C_{2,i},D_{2_i}=Com(r_i,w_i)\) and broadcast \(C_{2i}\)

```
[19]:
```

```
ks = [randfield(CF) for _ in range(n)]
rs = [G**k for k in ks]
```

```
[20]:
```

```
cs = [randfield(CF) for _ in range(n)]
ws = [(u ** k) * E(c*q) for c, k in zip(cs, ks)]
```

```
[21]:
```

```
coms2 = [com(x=c, r=w) for c, w in zip(cs, ws)]
```

```
[22]:
```

```
dcoms2 = [c.D for c in coms]
```

Proof

```
[23]:
```

```
CF(D(u ** ks[0])) == reduce(add, (ps)) * ks[0]
```

```
[23]:
```

```
True
```

```
[24]:
```

```
CF(D(u ** ks[0] * E(cs[0] * q))) == CF(D(u ** ks[0]) + D(E(cs[0] * q))) \
== reduce(add, (ps)) * ks[0] + cs[0] * q
```

```
[24]:
```

```
True
```

#### Round 4¶

Each player P_i broadcasts

\(D_{2,i}\), which allows everybody to compute \([r_i , w_i ]\) = \(Ver(C_{2,i} , D_{2,i} )\)

a zero-knowledge argument \(Π_{(2,i)}\)

Players compute \(w=\oplus_{i=1}^{t+1}w_i=E(k\rho + cq)\) where \(k=\sum_{i=1}^{t+1}k_i\) and \(c=\sum_{i=1}^{t+1}c_i\). Players also compute \(R=\Pi_i^{t+1}r_i=g^k\) and \(r=H'(R)\in Z_q\)

```
[25]:
```

```
all([c.C == commit(H=H, G=G, *c.D) for c in coms2])
```

```
[25]:
```

```
True
```

```
[26]:
```

```
w = reduce(mul, ws)
R = reduce(mul, rs)
r = CF(R.x)
```

Proof

```
[27]:
```

```
R == G ** reduce(add, ks)
```

```
[27]:
```

```
True
```

```
[28]:
```

```
CF(D(w)) == reduce(add, (ps)) * reduce(add, ks) + reduce(add, cs) * q
```

```
[28]:
```

```
True
```

#### Round 5¶

players jointly decrypt \(w\) using **TDec** to learn the value \(\tau ∈ [−q^7 , q^7]\) such that \(\tau = kρ \mod q\) and \(ψ = η ^{−1} \mod q\)

Each player computes:

```
[29]:
```

```
psi = CF(D(w))
```

```
[30]:
```

```
pai = ~psi
```

```
[31]:
```

```
sigma = ((u**m) * (v**r)) ** pai
```

Proof

```
[32]:
```

```
x = reduce(add, xs)
p = reduce(add, ps)
k = reduce(add, ks)
```

```
[33]:
```

```
assert CF(D(u**m)) == m * p
assert CF(D(v**r)) == r * p * x
assert CF(D(u**m)) + CF(D(v**r)) == p * (m + x * r)
assert CF(D((u**m) * (v**r))) == p * (m + x * r)
assert CF(D(((u**m) * (v**r)) ** pai)) == (m + x * r)/k
```

```
[34]:
```

```
assert CF(D(sigma)) == (m + x * r)/k
assert (G ** k).x == r
```

#### Round 6¶

The players invoke distributed decryption protocol TDec over the ciphertext \(σ\). Let \(s = D(σ) mod q\). The players output \((r, s)\) as the signature for \(m\).

```
[35]:
```

```
r, s = r, CF(D(sigma))
```

### Verify¶

```
[36]:
```

```
from klefki.crypto.ecdsa.secp256k1 import verify
```

```
[37]:
```

```
verify(pub=y, sig=(r, s), msg="Hello Threshold ECDSA")
```

```
[37]:
```

```
True
```

## III Scheme of GG18¶

### Key generation Protocol¶

**Phase 1**. Each Player \(P_i\) select \(u_i \in_R Z_q\); computes \([KGC_i, KGD_i]=Com(g^{u_i})\) and broadcast \(KGC_i\). Each player \(P_i\) broadcast \(E_i\) the public key for Paillier’ cryptosytem

```
[50]:
```

```
n = 9
t = 6
G = ECC.G
p = generate_prime(128)
q = generate_prime(128)
pai = Paillier(p, q)
```

```
[51]:
```

```
pai_pks = [Paillier(p, q) for _ in range(n)]
```

```
[52]:
```

```
us = [randfield(CF) for _ in range(n)]
```

```
[53]:
```

```
ys = [G ** u for u in us]
trap = randfield(CF)
H = G ** trap
com = partial(PedersonCommitment, H=H, G=G)
coms = [com(x=y.value[0], r=y.value[1]) for y in ys]
```

**Phase 2**. Each Player \(P_i\) broadcast \(KCD_i\), let \(y_i\) be the value decommitted by \(P_i\). The player \(P_i\) performs a \((t, n)\) Feldman-VSS of the value \(u_i\), with \(y_i\) as the “free term in the exponent”. The pubkey is set to \(y=\prod_i y_i\). Each player adds the private shares received during the \(n\) VSS. The resoulting values \(x_i\) are a \((t, n)\) SSSS of secret key \(x = \sum_iu_i\). Note that the value \(X_i=g^x_i\) are public.

```
[54]:
```

```
from klefki.crypto.vss import VSS
from klefki.types.algebra.concrete import FiniteFieldCyclicSecp256k1 as CF
from klefki.types.algebra.concrete import EllipticCurveCyclicSubgroupSecp256k1 as ECC
from functools import reduce
from operator import mul, add
```

```
[55]:
```

```
vss = [VSS(CF, ECC.G).setup(u, t, n) for u in us]
assert len(vss) == n
```

```
[56]:
```

```
ids = [randfield(CF) for i in range(n)]
vss_shares = [(CF(i), reduce(add, [v.f(i) for v in vss])) for i in ids]
```

```
[57]:
```

```
xs = [i[1] for i in vss_shares]
ids = [i[0] for i in vss_shares]
```

```
[58]:
```

```
x = reduce(add, us)
y = reduce(mul, ys)
assert G ** x == y
```

```
[59]:
```

```
assert x == VSS.decrypt(vss_shares)
```

**Phase 3**, let \(N_i=p_iq_i\) be the RSA mod associated with E_i, Each palyer \(P_i\) proves in ZK that he knows \(x_i\)

### Signature Generation¶

**Prepare**

Using the appropriate Lagrangian coeﬃcients \(\lambda_{i,S}\) each player in \(S\) can locally map its own \((t, n)\) share of \(x_i\) of x into a \((t, t)\) share of \(x\).

```
[60]:
```

```
ws = [xs[j] * reduce(mul, [ids[m] / (ids[m]-ids[j]) for m in range(t) if m != j]) for j in range(t)]
```

```
[61]:
```

```
assert x == reduce(add, ws)
```

We will to sign msg \(m\):

```
[62]:
```

```
from klefki.utils import to_sha256int
m = CF(to_sha256int("Hello Threshold ECDSA"))
```

**Phase1**.

Each Player \(P_i\) selects \(k_i, \gamma_i \in_R Z_q\); computes \([C_i, D_i]=Com(G^{\gamma_i})\) and broad cast \(C_i\). Define \(k=\sum_{i \in s}k_i, \gamma = \sum_{i \in s}\gamma_i\). Note that

```
[63]:
```

```
ks = [randfield(CF) for _ in range(t)]
rs = [randfield(CF) for _ in range(t)]
```

```
[64]:
```

```
k = reduce(add, ks)
r = reduce(add, rs)
```

**Phase2**.

Every pair of player \(P_i, P_j\) engages in two \(multiplicative-to-additive\) share conversation subprotocols

2.1 \(P_i, P_j\) run \(MtA\) with shares \(k_i, \gamma_j\) respectively. Let \(\alpha_{ij}\) [resp. \(\beta_{ij}\)] be the share received by player \(P_i\) [resp. \(P_j\)] at the end of this protocol, i.e.

Player \(P_i\) set \(\delta_i = k_i\gamma_i + \sum_{j\neq i}\alpha_{ij}+\sum_{j\neq i}\beta_{ij}\). Note that the \(\delta_i\) are a \((t, t)\) additive sharing of \(k\gamma=\sum_{i \in s} \delta_i\)

```
[65]:
```

```
p = generate_prime(512)
q = generate_prime(512)
```

```
[66]:
```

```
PMtA = partial(MtA, p=p, q=q)
shares_kg = [
[PMtA(a=ks[i], b=rs[j]) for j in range(t) if j != i]
for i in range(t)]
```

```
[67]:
```

```
ds = [ks[i]*rs[i] + reduce(add, [s[0] + s[1] for s in shares_kg[i]]) for i in range(t)]
```

```
[68]:
```

```
assert k * r == reduce(add, ds)
```

2.2 \(P_i,P_j\) run MtAwc with shares \(k_i, w_i\) respectively. Let \(\mu_{ij}\) [resp. \(v_{ij}\)] be the share received by player \(P_i\)[resp. \(P_j\)] at the end of this protocol, i.e.

Player \(P_i\) sets \(\sigma_i = k_iw_i + \sum_{j\neq i}\mu_{ij}+\sum_{j\neq i}v_{ij}\)

```
[69]:
```

```
p = generate_prime(512)
q = generate_prime(512)
PMtA = partial(MtA, p=p, q=q)
shares_kw = [
[PMtA(a=ks[i], b=ws[j]) for j in range(t) if j != i]
for i in range(t)]
```

```
[70]:
```

```
sigmas = [ks[i] * ws[i] + reduce(add, [s[0] + s[1] for s in shares_kw[i]]) for i in range(t)]
```

```
[71]:
```

```
assert k * x == reduce(add, sigmas)
```

**Phase 3**

Every player \(P_i\) broadcasts \(\delta_i\) and the players reconstruct \(\delta = \sum_{i \in s} \delta_i = k\gamma\). The players compute \(\delta^{−1} \mod q\).

```
[72]:
```

```
d = reduce(add, ds)
```

```
[73]:
```

```
d_ = ~d
```

**Phase 4**

Each Player \(P_i\) broadcasts \(D_i\), let \(\Gamma_i\) be the value decommited by \(P_i\) who proves in \(ZK\) that he knows \(\gamma_i\) s.t. \(\Gamma_i = g^{\gamma_i}\) using Schnoor’s protocol.

The players compute

and \(r = R.x\)

```
[74]:
```

```
assert k * r == reduce(add, ds)
```

```
[75]:
```

```
reduce(add, ds) * (~r) == k
```

```
[75]:
```

```
True
```

```
[76]:
```

```
com_rs = [G**r for r in rs]
```

```
[77]:
```

```
R = reduce(mul, com_rs) ** d_
```

```
[78]:
```

```
assert R == G ** (~k)
```

```
[79]:
```

```
r = CF(R.x)
```

**Phase 5**

Each Player \(P_i\) sets \(s_i=mk_i+r\sigma_i\). Note that

```
[80]:
```

```
assert G ** x == y
assert k * x == reduce(add, sigmas)
assert k == reduce(add, ks)
```

```
[81]:
```

```
assert m * reduce(add, ks) + reduce(add, sigmas) * r == k * (m + x * r)
```

```
[82]:
```

```
ss = [m * ks[i] + sigmas[i] * r for i in range(t)]
```

```
[83]:
```

```
s = reduce(add, ss)
```

```
[84]:
```

```
s == k * (m + x * r)
```

```
[84]:
```

```
True
```

### Verify¶

```
[85]:
```

```
from klefki.crypto.ecdsa.secp256k1 import verify
```

```
[86]:
```

```
verify(pub=y, sig=(r, s), msg="Hello Threshold ECDSA")
```

```
[86]:
```

```
True
```

## Ref:¶

Antonio Salazar Cardozo, Threshold ECDSA — Safer, more private multi-signatures, https://blog.keep.network/threshold-ecdsa-safer-more-private-multi-signatures-51153f3e9ed2

Gennaro, Rosario, Steven Goldfeder, and Arvind Narayanan. “Threshold-Optimal DSA/ECDSA Signatures and an Application to Bitcoin Wallet Security.” In Applied Cryptography and Network Security, edited by Mark Manulis, Ahmad-Reza Sadeghi, and Steve Schneider, 9696:156–74. Cham: Springer International Publishing, 2016. https://doi.org/10.1007/978-3-319-39555-5_9.

Rosario Gennaro and Steven Goldfeder. 2018. Fast Multiparty Threshold ECDSA with Fast Trustless Setup. In Proceedings of the 2018 ACM SIGSAC Conference on Computer and Communications Security (CCS ’18). Association for Computing Machinery, New York, NY, USA, 1179–1194. DOI:https://doi.org/10.1145/3243734.3243859