Contents

Damgård–Jurik cryptosystem

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 primeto${\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[edit]

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[edit]

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 ($jd)^{-1}\;mod\;n^{s}} .

Simplification[edit]

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=1\;mod\;n^{s}}$ and ${\displaystyle d=0\;mod\;\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.

See also[edit]

• The Damgård–Jurik cryptosystem interactive simulator demonstrates a voting application.

References[edit]