The Damgård–Jurik cryptosystem^[1] is a generalization of the Paillier cryptosystem. It uses computations modulo ${\displaystyle n^{s+1}}$ where ${\displaystyle n}$ is an RSA modulus and ${\displaystyle s}$ a (positive) natural number. Paillier's scheme is the special case with ${\displaystyle s=1}$. The order ${\displaystyle \varphi (n^{s+1})}$ (Euler's totient function) of ${\displaystyle Z_{n^{s+1}}^{*}}$ can be divided by ${\displaystyle n^{s}}$. Moreover, ${\displaystyle Z_{n^{s+1}}^{*}}$ can be written as the direct product of ${\displaystyle G\times H}$. ${\displaystyle G}$ is cyclic and of order ${\displaystyle n^{s}}$, while ${\displaystyle H}$ is isomorphic to ${\displaystyle Z_{n}^{*}}$. For encryption, the message is transformed into the corresponding coset of the factor group ${\displaystyle G\times H/H}$ and the security of the scheme relies on the difficulty of distinguishing random elements in different cosets of ${\displaystyle 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

1. Choose two large prime numbers p and q randomly and independently of each other.
2. Compute ${\displaystyle n=pq}$ and ${\displaystyle \lambda =\operatorname {lcm} (p-1,q-1)}$.
3. Choose an element ${\displaystyle g\in \mathbb {Z} _{n^{s+1}}^{*}}$ such that ${\displaystyle g=(1+n)^{j}x\mod n^{s+1}}$ for a known ${\displaystyle j}$ relative prime to ${\displaystyle n}$ and ${\displaystyle x\in H}$.
4. Using the Chinese Remainder Theorem, choose ${\displaystyle d}$ such that ${\displaystyle d\mod n\in \mathbb {Z} _{n}^{*}}$ and ${\displaystyle d=0\mod \lambda }$. For instance ${\displaystyle d}$ could be ${\displaystyle \lambda }$ as in Paillier's original scheme.

• The public (encryption) key is ${\displaystyle (n,g)}$.
• The private (decryption) key is ${\displaystyle d}$.

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}^{*}}$.
3. Compute ciphertext as: ${\displaystyle c=g^{m}\cdot r^{n^{s}}\mod n^{s+1}}$.

Decryption

1. Ciphertext ${\displaystyle c\in \mathbb {Z} _{n^{s+1}}^{*}}$
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)^{jmd\;mod\;n^{s}}(x^{m}r^{n^{s}})^{d\;mod\;\lambda }=(1+n)^{jmd\;mod\;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 <!--\; \cdot \; -->(jd{)}^{-<!--\; -\; -->1}mod{n}^s}$Zdroj:https://en.wikipedia.org?pojem=Damgård–Jurik_cryptosystem
   Text je dostupný za podmienok Creative Commons Attribution/Share-Alike License 3.0 Unported; prípadne za ďalších podmienok. Podrobnejšie informácie nájdete na stránke Podmienky použitia.

   ---