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