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:

  1. The parties produce shares of a value d similarly to the Damgard-Jurik scheme

  2. 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,

\[Enc_N(m, r) = (1+N)^m \cdot r^N \mod N^2\]

Generating a Shared Paillier Decryption Key

We now present our protocol for generating a shared Paillier decryption key. As stated, similarly to Damgard and Jurik , we share a decryption exponent as follows:

\[\begin{split}d \equiv \left\{ \begin{aligned} 0 &\mod \phi(N) \\ 1 &\mod N \end{aligned} \right\}\end{split}\]

A distributed generation of a shared Paillier decryption key with passive security:

  • Input:

A public RSA modulus \(N=pq\) with unknow factorization, additive shares of \(\phi(N)\):

\[\begin{split}sk_0 = N-p_0-q_0+1\\ sk_1 = -p_1-q_2\end{split}\]

\(sk_0\), \(sk_1\) hold by \(P_0\), and \(P_1\) respectively, A public ElGamel key \((g,h)\) with secret key shared between the parities. A public Pailler key \(N_0>>N^3\) with the secret key hold by \(P_0\)

[1]:

from klefki.numbers.primes import generate_prime
from klefki.numbers import lcm
from klefki.mpc.secret_sharing import additive_share
from klefki.types.algebra.meta import field
import random

[2]:

P, Q = generate_prime(32), generate_prime(32)
N = P * Q
Phi = (P-1) * (Q-1)


[3]:

sk0, sk1 = additive_share(Phi, field(N), 2)
sk0, sk1 = sk0.value, sk1.value

[4]:

from klefki.crypto.elgamal import ElGamal

[5]:

x = 42
el = ElGamal(x)

[6]:

g, h = el.pubkey
The protocol

  1. \(P_0\) encrypts \(sk_0\) using \(N_0\) and sends this to \(P_1\)

[7]:

from klefki.crypto.paillier import Paillier

[8]:

p0, q0 = generate_prime(32**2), generate_prime(32**2)

[9]:

N0 = p0 * q0

[10]:

p0 = Paillier(p0, q0)

[11]:

e_sk0 = p0.E(sk0)

[12]:

p0.D(e_sk0).value == sk0

[12]:

True

  1. \(P_1\) picks \(r_1 \in Z_N\) and \(r_\sigma \in Z_{2^{logN+k}}\) uniformly at random (for a statistical parameter \(κ\) that enables to mask the secret key). \(P_1\) computes an encryption of

\[(sk_0 + sk_1) \cdot r_1 + N \cdot r_\sigma\]

using the homomorphic property of Paillier encryption. This is rerandomized and sent to \(P_0\) .

[13]:

from klefki.types.algebra.utils import randfield
from klefki.types.algebra.meta import field
from math import log

[14]:

r1 = randfield(field(N)).value
ro = randfield(field(int(2 ** log(N, 2)))).value

[15]:

re = (p0.E(sk1) * e_sk0) ** r1 * p0.E(N) ** ro

[16]:

assert p0.D((p0.E(sk1) * e_sk0) ** r1 * p0.E(N) ** ro) == p0.D(p0.E((sk0+sk1) * r1 + N * ro))

  1. \(P_0\) decrypts, thus obtaining plaintext \(r_0 ; P_0\) computes \(r_0^{−1} \mod N\) and encrypts this as well as plaintext \(sk_0 (r_0^{−1} \mod N)\) under public-key \(N_0\) . Both ciphertexts are sent to \(P_1\)

[17]:

r0 = p0.D(re)

[18]:

(~field(N)(r0)).value

[18]:

1270707545493826762

[19]:

er0 = p0.E((~field(N)(r0)))

[20]:

esk_r0 = p0.E(sk0 * (~field(N)(r0)).value)

  1. Based on the encryptions of \(r_0^{-1} \mod N\) and \(sk_0(r_0^{-1} \mod N)\), \(P_1\) computes an encryption of:

\begin{align} d&=(sk_0(r_0^{-1} \mod N) \cdot r_1 + (r_0^{-1} \mod N)(sk_1 \cdot r_1))\\ &=r_1(sk_0+sk_1)(r_0^{01} \mod N)\\ &=r_1 \cdot \phi(N) \cdot (r_0^{-1} \mod N) \end{align}

\(P_1\) then picks \(\bar{d}_1\) uniformly at random in \(Z_{2^3logN+κ}\) , and computes and rerandomizes an encryption of \(d + \bar{d}_1\) . This is sent to \(P_0\) and finally, \(P_1\) sets its share of d to the integer \(-\bar{d}_1\) .

[21]:

e_d = esk_r0 ** r1 * (er0 ** sk1) ** r1

[22]:

assert p0.D(e_d).value == r1 * (P-1) * (Q-1) * (~field(N)(r0)).value

[23]:

d1_ = randfield(field(int(2 ** (3 * log(N, 2))))).value

e_d0 = p0.E(d1_) * e_d

[24]:

d1 = -d1_

  1. \(P_0\) decrypts and obtains \(d_0\) : its share of \(d\).

[25]:

d0 = p0.D(e_d0).value
Correctness:
[26]:

d = p0.D(e_d).value

[27]:

assert p0.D(e_d).value == d1 + d0

[28]:

assert d % ((P-1) * (Q-1)) == 0
assert d % (P * Q) == 1

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}\) .

A distributed Paillier decryption with a shared key:

Inputs: A public Paillier key \(N=pq\) with unknown factorization and a ciphertext \(C=E_N(m,r)\).

Party \(P_i\) hold its share \(d_i\) of the secret decryption exponent, \(d=d_0+d_1\) where

\[d \equiv 1 \mod N \wedge d \equiv 0 \mod \phi(N)\]

Finall, the parties hold commitments to (or rather: ElGamal encryptions of) their key-shares.

The protocol:

  1. \(P_0\) sends \(c_0=c^{sk0} \mod N^2\) to \(P_1\). Moreover, \(P_0\) demonstrates that this has been done correctly by executing \(\pi_{EQ}\), i.e., that the committed number equals the discrete log of \(c_0\) with base c and the plaintext encrypted with ElGamal.

  2. \(P_1\) sends \(c_1=c^{sk2} \mod N^2\) to \(P_0\). Moreover, \(P_1\) demonstrates that this has been done correctly by executing \(\pi_{EQ}\), i.e., that the committed number equals the discrete log of \(c_0\) with base c and the plaintext encrypted with ElGamal.

  3. Finally, both parties compute the paintext via Function \(L\), \(m=L(c_0 \cdot c_1) \mod N^2)=((c_0 \cdot c_1) \mod N^2 -1) / N)\)

\[L(u) = \frac{(u-1)}{n}\]
[29]:

from klefki.crypto.damgard_jurik import DJPaillier
from klefki.crypto.paillier import L

[30]:

m = 31415926
djp = DJPaillier(P, Q, s=3, strict=True)

[31]:

N, G = djp.pubkey

[32]:

r = randfield(G.functor)

[33]:

c = djp.E(m, r=r)
assert djp.D(c, priv=d).value == m
assert djp.privkey % lcm((P-1), (Q-1)) == 0
assert djp.privkey % (P * Q) == 1

[34]:

N, G = djp.pubkey

[35]:

c0 = c ** d0
c1 = c ** d1
g0 = G ** d0
g1 = G ** d1

[36]:

assert c0 * c1 == c ** d0 * c ** d1
assert c ** (d0 + d1) == c ** d
assert g0 * g1 == G ** d

[37]:

F = field(N, "N")

F(L((c0 * c1).value, N)) * ~F(L((g0 * g1).value, N))

[37]:

N::31415926

[38]:

~F(L((g0 * g1).value, N))

[38]:

N::2763856104640951191

Generating a threshold key

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

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

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

\[\begin{split}\phi(N) \cdot (\phi(N)^{-1} \mod N) \equiv \left\{ \begin{aligned} 0 &\mod \phi(N) \\ 1 &\mod N \end{aligned} \right\}\end{split}\]
[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):

    1. 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)]

    1. 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]

    1. 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

\[v=\sum_{i=1}^ku_i+N \cdot r_i\]
[45]:

from functools import reduce
from operator import add

[54]:

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

    1. Each party locally computes the public value

\[\bar{v} = v^{-1} \mod N\]

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]

    1. 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\)

\begin{align} w=\left( (t \cdot \phi(N) + r \cdot N)^{-1} \right) \cdot t = \left( \phi(N)^{-1} \mod N\right) + ZN \end{align}
[83]:

w = sum(ws)

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

\[d=( ( \phi(N)^-1 \mod N) + zN) \cdot \phi(N) = ((\phi(N)^{-1} \mod N)\phi(N) +z\phi(N)N\]
\[d = w \cdot Phi(N)\]
[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.., Efficient RSA Key Generation and Threshold Paillier in the Two-Party Setting