# Threshold Paillier Cryptosystem¶

## A Distributed Decryption for Paillier¶

The protocol offers a distributive decryption for Paillier with simulation based security against malicious adversaries without randomness extraction. It is comprised of the following two subprotocols:

The parties produce shares of a value d similarly to the

**Damgard-Jurik scheme**The parties run the distributed decryption algorithm using their shares.

use \(g = 1 + N\) as a generator of the subgroup of \(Z^∗_{N^2}\) of order \(N\). Encryption of a plaintext \(m\) with randomness \(r\) is then,

### Performing a Joint Paillier Decryption¶

To perform a joint decryption of some ciphertext \(c\), both parties need to raise \(c\) to their share of the key, \(d_0\) or \(d_1\) . They then demonstrate that this has been computed correctly using the commitments of the shares. The plaintext is immediately computable from \(c^{d_0}\) and \(c^{d_1}\) .

## Generating a threshold key¶

Constructing a threshold key essentially consists of computing a Shamir sharing of this. Our solution consists of two steps:

First, compute an additive sharing of \(d\).

Then, compute Shamir shares of this and decrypt these toward the relevant parties.

```
[39]:
```

```
from klefki.numbers.primes import generate_prime
from klefki.types.algebra.meta import field
from klefki.numbers import invmod
from klefki.mpc.secret_sharing import additive_share
from functools import reduce
from operator import add
```

```
[40]:
```

```
inv_phi = invmod(Phi, N)
```

```
[41]:
```

```
assert Phi * inv_phi % Phi == 0
assert Phi * inv_phi % N == 1
```

### Protocol (the ZK part was ignored):¶

For \(1 \le i \le k\), party \(P_i\) pick \(t_i\), uniformly at random from \(Z_N\) and \(r_i\) uniformly at random from \(Z_{N·k·2^n}\) , where \(n\) is a security parameter. Each \(P_i\) then broadcasts ElGamal two encryptions, \(c_{ti}\) of \(t_i\) and \(c_ri\) of \(r_i\). These will be views as sharings of random values, \(t=\sum_{i=1}^{k}t_i\) and \(r=\sum_{i=1}^kr_i\)

```
[42]:
```

```
n = 3
k = 6
F1 = field(N, "Z_N")
F2 = field(N*k*2**3, "Z_N.k.2^n")
```

```
[43]:
```

```
ts = [randfield(F1) for i in range(k)]
rs = [randfield(F2) for i in range(k)]
```

The parities obtaining shares \(u_i, \cdots, u_n\) of \(t \cdot \phi(N)\) as well as encryptions \(c_{ui}\) of those shares.

```
[44]:
```

```
us = [i*Phi for i in ts]
```

For \(1 \le i \le k\), party \(P_i\) broadcast \(u_i+N \cdot r_i\); the parties then decrypt \(c_{ui}.(c_{ri})^N\), The parties compute

```
[45]:
```

```
from functools import reduce
from operator import add
```

```
[54]:
```

```
v = sum([us[i] + rs[i] * N for i in range(k)])
```

Each party locally computes the public value

Thies is then used to compute an additive sharing of \(w = t \cdot \bar{v}\); \(P_i\) locally multiplies \(t_i\) by \(\bar{v}\) to compute \(w_i\), and all parities raise the encryptions of the \(t_i\) to \(\bar{v}\) to opbtain encryption of the \(w_i\)

```
[55]:
```

```
~v
```

```
[55]:
```

```
Z_N::7516726862107618122
```

```
[82]:
```

```
ws = [t* (~v) for t in ts]
ds = [w.value * Phi for w in ws]
```

Finally, the parities obtaining shares \(d_i\) of \(d\) along with encryptions \(c_{di}\) of the \(d_i\).

The sahred \(w=\sum_{i=1}^kw_i eques\)

```
[83]:
```

```
w = sum(ws)
```

For some integer \(z\) of atmost \(\lfloor log_k \rfloor + \lfloor logN \rfloor\) bits. This implies that

```
[87]:
```

```
assert Phi * w.value % lcm((P-1), (Q-1)) == 0
assert Phi * w.value % (P * Q) == 1
assert sum(ds) % lcm((P-1), (Q-1)) == 0
assert sum(ds) % (P * Q) == 1
```

Ref:

Carmit Hazay, Gert Læssøe Mikkelsen, etc.., Efﬁcient RSA Key Generation and Threshold Paillier in the Two-Party Setting