Damgaard-Jurik cryptosystem

The Damgård-Jurik cryptosystem [Ivan Damgård, Mads Jurik: [http://www.brics.dk/RS/00/45/ A Generalisation, a Simplification and Some Applications of Paillier's Probabilistic Public-Key System] . Public Key Cryptography 2001: 119-136] is a generalization of the Paillier cryptosystem. It uses computations modulo $$n^{s+1} where $$n is an RSA modulus and $$s a (positive) natural number. Paillier's scheme is the special case with $$s=1. The order $$varphi(n^{s+1}) (Euler's totient function) of $$Z^*_{n^{s+1 can be divided by $$n^s. Moreover $$Z^*_{n^{s+1 can be written as the direct product of $$G imes H. $$G is cyclic and of order $$n^s, while $$H is isomorphic to $$Z^*_n. For encryption, the message is transformed into the corresponding coset of the factor group $$G/H and the security of the scheme relies on the difficulty of distinguishing random elements in different cosets of $$H. It is semantically secure if it is hard to decide if two given elements are in the same coset. Like Paillier, the security of Damgård-Jurik can be proven under the decisional composite residuosity assumption.

Key generation

#Choose two large prime numbers "p" and "q" randomly and independently of each other.
#Compute $$n=pq and $$lambda=lcm(p-1,q-1).
#Choose an element $$g in Z^*_{n^{s+1 such that $$g=(1+n)^j x ;mod; n^{s+1} for a known $$j relative prime to $$n and $$x in H.
#Using the Chinese Remainder Theorem, choose $$d such that $$d ;mod; n in Z^*_n and $$d= 0 ;mod; lambda. For instance $$d could be $$lambda as in Palliers original scheme.
*The public (encryption) key is $$(n, g).
*The private (decryption) key is $$d.

Encryption

#Let $$m be a message to be encrypted where $$min mathbb Z_{n^s}.
#Select random $$r where $$rin mathbb Z^{*}_{n^{s+1 .
#Compute ciphertext as: $$c=g^m cdot r^{n^s} mod n^{s+1} .

Decryption

#Ciphertext $$cin mathbb Z^{*}_{n^{s+1
#Compute $$c^d ;mod;n^{s+1}. If "c" is a valid ciphertext then $$c^d = (g^m r^{n^s})^d = ((1+n)^{jm}x^m r^{n^s})^d = (1+n)^{jmd ;mod; n^s} (x^m r^{n^s})^{d ;mod; lambda} = (1+n)^{jmd ;mod; n^s}.
#Apply a recursive version of the Paillier decryption mechanism to obtain $$jmd. As $$jd is known, it is possible to compute $$m=(jmd)cdot (jd)^{-1} ;mod;n^s.

Simplification

At the cost of no longer containing the classical Paillier cryptosystem as an instance, Damgård-Jurik can be simplified in the following way:
*The base "g" is fixed as $$g=n+1.
*The decryption exponent "d" is computed such that$$d=1 ;mod; n^s and $$d=0 ;mod; lambda.

In this case decryption produces $$c^d = (1+n)^{m} ;mod; n^{s+1}. Using recursive Paillier decryption this gives us directly the plaintext "m".

References