Damgård–Jurik cryptosystem

Encryption

1. Let ${\displaystyle m}$ be a message to be encrypted where ${\displaystyle m\in {\mathbb{Z}}_{n^s}}$.
2. Select random ${\displaystyle r}$ where ${\displaystyle r\in {\mathbb{Z}}_n^{\ast }}$.
3. Compute ciphertext as: ${\displaystyle c=g^m\cdot r^{n^s}\mathrm{mod}{n}^{s+1}}$.

Decryption

1. Ciphertext ${\displaystyle c\in {\mathbb{Z}}_{n^{s+1}}^{\ast }}$
2. Compute ${\displaystyle c^{d}mod{n}^{s+1}}$. If c is a valid ciphertext then ${\displaystyle c^d=(g^m{r}^{n^s}{)}^d=((1+n{)}^{jm}{x}^m{r}^{n^s}{)}^d=(1+n{)}^{jmdmod{n}^s}(x^m{r}^{n^s}{)}^{dmod\lambda }=(1+n{)}^{jmdmod{n}^s}}$.
3. Apply a recursive version of the Paillier decryption mechanism to obtain ${\displaystyle jmd}$. As ${\displaystyle jd}$ is known, it is possible to compute ${\displaystyle 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 ${\displaystyle g=n+1}$.
• The decryption exponent d is computed such that ${\displaystyle d=1mod{n}^s}$ and ${\displaystyle d=0mod\lambda }$.

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