Damgard-Jurik Scheme of Paillier

Generalisation

The publickey cryptosystem uses computations modulo \(n^{s+1}\) where \(n\) is an \(RSA\) modulus and \(s\) is a natural number. It contains Paillier’s scheme as a special case by setting \(s=1\)

We start from the observation that if \(n=pq,p,q\) odd primes, then \(Z^*_{n^{s+1}}\) as a multiplicative group is a direct product \(G\times H\), where \(G\) ic cyclic of order \(n^s\) and \(H\) is isomorphic to \(Z^*_{n}\), which follows directly from elementary number theory.

Thus, the factor group \(\bar{G}=Z*_{n^{s+1}}/H\) is also cyclic of order \(n^s\). For an arbitary element \(a \in Z_n^{s+1}\), we let \(\bar{a} H\) we denote the element represented by \(a\) in the factor group \(\bar{G}\).

• Lemma 1: For any \(s< p, q\), the element \(n+1\) has order \(n^s\) in \(Z_n^{s+1}\).

It is easy to compute \(i\) from \((1+n)^i \mod n^{s+1}\). If we define the function \(L()\) by \(L(b)=(b-1)/n\) then clealy we have:

\[L((1+n)^i \mod n^{s+1}) =(1 + \binom i 2 n + \cdots + \binom i s n ^{s-1} ) \mod n ^s\]

Key Generation

On input the security parameter \(k\), choose an \(RSA\) modulus \(n=pq\) of length \(k\) bits. Also choose an element \(g\in Z_n^{s+1}\) such that \(g=(1+n)^j x\) mod \(n^{s+1}\) for a known \(j\) relatively prime to \(n\) and \(x \in H\).

This can be done, \(e.g\), by choosing \(j, x\) as random first and computing \(g\);

Let \(\lambda\) be the \(lcm\) of \(p-1\) and \(q-1\). By the Chinese Remainder Theorem, choose \(d\) such that \(d\) mod \(n\in Z_n\) and \(d=0\) mod \(\lambda\).

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

Any such choice of \(d\) will work in the following.

Now the pubkey is \(n, g\) while the secret key is \(d\).

from klefki.types.algebra.meta import field
from klefki.types.algebra.utils import randfield
from klefki.numbers.primes import generate_prime
from klefki.crypto.damgard_jurik import damgard_jurik_reduce
from klefki.numbers import lcm
from random import randint
from math import gcd

k = 256

p, q = generate_prime(k), generate_prime(k)
assert p != q

# Paillier's scheme is a special case by setting s=1
s = 3
n = p * q

lam = lcm((p - 1), (q - 1))
assert gcd(n, lam) == 1

G = field(n**s, "G") # n ** s == n if s = 1
# multiplicative group
MG = field(n ** (s+1), "N^{s+1}") # n ** (s +1 ) == n2 in pailer case
H = field(n, "H")
LG = field(lam, "LCMGroup")

j = generate_prime(k)
assert gcd(j, n) == 1

x = randfield(H)
g = MG((MG(1 + n) ** j) * x)

from klefki.numbers import crt

# Find d such that d = 0 mod lambda and d = 1 mod n^s
d = crt(a_list=[0, 1], n_list=[LG.P, G.P])
assert d % G.P == 1
assert d % LG.P == 0

pubkey = (n, g)
privkey = d

Encryption

The paintext set is \(Z_{n^s}\). Given a paintext \(i\), choose a random \(r \leftarrow Z^*_{n^{s+1}}\), and lte the cipertext be \(E(i, r) = g^ir^{n^s} \mod n^{s+1}\)

r = randfield(MG)
i = 31415926

def encrypt(i, r):
    return g ** i * r ** (n**s)

c = encrypt(i, r)

Decryption

Given a ciphertext \(c\), first compute \(c^d \mod n^{s+1}\), Clearly, if \(c=E(v, r)\), we get

\begin{align} c^d &= (g^i r^{n^s})^d\\ &=((1+n)^{ij} x^i r^{n^s})^d\\ &=(1+n)^{jid}(x^ir^{n^s})^d \\ &=(1+n)^{jid \mod n^s}(x^ir^{n^s})^{d \mod \lambda}\\ &=(1+n)^{jid \mod n^s} \end{align}

\begin{align} g^d &= ((1 + n)^jx)^d \\ &=(1 + n)^{jd} x^d \\ &=(1+n)^{jd \mod n^2}x^{d \mod \lambda} \end{align}

c ** d == (g ** i * r ** (n**s))**d \
       == (MG((MG(1 + n) ** j) * x) ** i * r ** (n**s)) ** d \
       == (MG(MG(1 + n) ** (j*i)) * (MG(x) ** i) * r ** (n**s)) ** d \
       == MG(MG(1 + n) ** (j * i * d)) * (((MG(x) ** i) * r ** (n**s)) ** d)

True

(((MG(x) ** i) * r ** (n**s)) ** LG(d)).value == 1

True

G(damgard_jurik_reduce((c ** d).value, n, s)) * ~G(damgard_jurik_reduce((g ** d).value, n, s))

G::31415926

A Threshold Variant of Paillier

We can solve our problem by letting the servers help us compute \(E(i, r)^d \mod n^{s+1}\). Then if we use \(g = n + 1\) and choose d such that \(d = 1 mod n^s\) and \(d = 0 \mod \lambda\), the remaining part of the decryption is easy to do without knowledge of \(d\).

Key generation

We find 2 primes \(p\) and \(q\), that satisifies \(p = 2p' + 1\) and \(q = 2q' + 1\), where \(p'\) and \(q'\) are primes and different from \(p,q\).

We set \(n = pq\) and \(m = p'q'\),we decide some \(s>0\), thus the paintext space will be \(Z_{n^s}\).

We pick \(d\) to satisfy:

\[\begin{split}d \equiv \left\{ \begin{aligned} 0 &\mod m \\ 1 &\mod n^s \end{aligned} \right\}\end{split}\]

And share \(d\) with \(SSSS\) in \(Z_{n^sm}\), the secret share of the i’th authority will be \(s_i=f(i)\) for \(1 \le i \le l\), and the pubkey will be \(n\).

from klefki.crypto.ssss import SSSS

k = 256

p_, q_ = generate_prime(k), generate_prime(k)
assert p != q

p, q = (p - 1) // 2, (q - 1) // 2

n = p * q
m = p_ * q_

G = field(n**s, "G") # n ** s == n if s = 1
# multiplicative group
MG = field(n ** (s+1), "N^{s+1}") # n ** (s +1 ) == n2 in pailer case
H = field(n, "H")
LG = field(m, "MGroup")

j = generate_prime(k)
assert gcd(j, n) == 1
x = randfield(H)
g = MG((MG(1 + n) ** j) * x)

d = crt(a_list=[0, 1], n_list=[m, n])

F = field(n**s * m, "n^sm")

ssss = SSSS(F)

k = 3
l = n = 6

ssss.setup(d, k, n)

<klefki.crypto.ssss.SSSS at 0x1076f8be0>

shares = [ssss.join(i) for i in range(1, n)]

Encryption

def encrypt(i, r):
    return g ** m * r ** (n**s)

r = randfield(MG)
i = 31415926

c = encrypt(i, r)

Share decryption

The i’th authority will compute \(c_i = c^{2 \Delta s_i}\), where \(c\) is the ciphertext, \(\Delta = l!\)

If we have the required k (or more) number of shares with a correct proof, we can combine them into the result by taking a subset S of k shares and combine them to

\[\begin{split}c' = \prod_{i\in S} c_i^{2\lambda_{0,i}^S} \\\end{split}\]

Where:

\[\lambda_{0,i}^s=\Delta \prod_{i' \in S;i} \frac{-i}{i-i'} \in Z\]

Implementation

from klefki.crypto.damgard_jurik import DJPaillier
from klefki.numbers.primes import generate_prime

P, Q = generate_prime(256), generate_prime(256)
s = 3

m = 42

djp = DJPaillier(P, Q, s)

djp.D(djp.E(m)).value == m

True

• Note that the threshold DJP is imported via https://github.com/cryptovoting/damgard-jurik

from klefki.crypto.damgard_jurik import ts_dj

public_key, private_key_ring = ts_dj.keygen(
    n_bits=512,
    s=3,
    threshold=100,
    n_shares=300
)

private_key_ring.i_list

[mpz(124),
 mpz(186),
 mpz(54),
 mpz(239),
 mpz(252),
 mpz(269),
 mpz(136),
 mpz(221),
 mpz(109),
 mpz(29),
 mpz(74),
 mpz(212),
 mpz(90),
 mpz(259),
 mpz(13),
 mpz(172),
 mpz(231),
 mpz(32),
 mpz(43),
 mpz(194),
 mpz(53),
 mpz(3),
 mpz(176),
 mpz(246),
 mpz(300),
 mpz(37),
 mpz(14),
 mpz(190),
 mpz(125),
 mpz(208),
 mpz(233),
 mpz(297),
 mpz(42),
 mpz(127),
 mpz(30),
 mpz(236),
 mpz(188),
 mpz(290),
 mpz(248),
 mpz(81),
 mpz(211),
 mpz(95),
 mpz(143),
 mpz(187),
 mpz(170),
 mpz(46),
 mpz(110),
 mpz(8),
 mpz(112),
 mpz(150),
 mpz(68),
 mpz(52),
 mpz(79),
 mpz(12),
 mpz(126),
 mpz(103),
 mpz(86),
 mpz(139),
 mpz(93),
 mpz(135),
 mpz(134),
 mpz(18),
 mpz(223),
 mpz(262),
 mpz(104),
 mpz(218),
 mpz(60),
 mpz(10),
 mpz(131),
 mpz(162),
 mpz(261),
 mpz(267),
 mpz(284),
 mpz(44),
 mpz(140),
 mpz(65),
 mpz(33),
 mpz(204),
 mpz(230),
 mpz(282),
 mpz(39),
 mpz(58),
 mpz(4),
 mpz(203),
 mpz(27),
 mpz(88),
 mpz(106),
 mpz(242),
 mpz(67),
 mpz(210),
 mpz(50),
 mpz(111),
 mpz(173),
 mpz(180),
 mpz(219),
 mpz(59),
 mpz(107),
 mpz(289),
 mpz(57),
 mpz(174)]

m = 42
c = public_key.encrypt(m)
private_key_ring.decrypt(c)

mpz(42)

Ref:

• 1. Damg˚ard and M. Jurik. A generalisation, a simplification and some applications of paillier’s proba- bilistic public-key system. In Public Key Cryptography, pages 119–136, 2001.

• Damgard-Jurik implementation https://github.com/cryptovoting/damgard-jurik