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:
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\).
Any such choice of \(d\) will work in the following.
Now the pubkey is \(n, g\) while the secret key is \(d\).
[1]:
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
[2]:
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")
[3]:
j = generate_prime(k)
assert gcd(j, n) == 1
x = randfield(H)
g = MG((MG(1 + n) ** j) * x)
[4]:
from klefki.numbers import crt
[5]:
# 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
[6]:
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}\)
[7]:
r = randfield(MG)
i = 31415926
def encrypt(i, r):
return g ** i * r ** (n**s)
[8]:
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
[9]:
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)
[9]:
True
[10]:
(((MG(x) ** i) * r ** (n**s)) ** LG(d)).value == 1
[10]:
True
[11]:
G(damgard_jurik_reduce((c ** d).value, n, s)) * ~G(damgard_jurik_reduce((g ** d).value, n, s))
[11]:
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:
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\).
[27]:
from klefki.crypto.ssss import SSSS
[28]:
k = 256
p_, q_ = generate_prime(k), generate_prime(k)
assert p != q
[29]:
p, q = (p - 1) // 2, (q - 1) // 2
[30]:
n = p * q
m = p_ * q_
[31]:
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")
[32]:
j = generate_prime(k)
assert gcd(j, n) == 1
x = randfield(H)
g = MG((MG(1 + n) ** j) * x)
[33]:
d = crt(a_list=[0, 1], n_list=[m, n])
[34]:
F = field(n**s * m, "n^sm")
[35]:
ssss = SSSS(F)
[36]:
k = 3
l = n = 6
[37]:
ssss.setup(d, k, n)
[37]:
<klefki.crypto.ssss.SSSS at 0x1076f8be0>
[38]:
shares = [ssss.join(i) for i in range(1, n)]
Encryption¶
[39]:
def encrypt(i, r):
return g ** m * r ** (n**s)
[40]:
r = randfield(MG)
i = 31415926
[41]:
c = encrypt(i, r)
Implementation¶
[27]:
from klefki.crypto.damgard_jurik import DJPaillier
from klefki.numbers.primes import generate_prime
[28]:
P, Q = generate_prime(256), generate_prime(256)
s = 3
[29]:
m = 42
[30]:
djp = DJPaillier(P, Q, s)
[31]:
djp.D(djp.E(m)).value == m
[31]:
True
Note that the threshold DJP is imported via https://github.com/cryptovoting/damgard-jurik
[32]:
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
)
[33]:
private_key_ring.i_list
[33]:
[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)]
[34]:
m = 42
c = public_key.encrypt(m)
private_key_ring.decrypt(c)
[34]:
mpz(42)
Ref:¶
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
[ ]: