## FANDOM

566 Pages

The Damgård-Jurik cryptosystem[1] 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 \times 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 Edit

1. Choose two large prime numbers p and q randomly and independently of each other.
2. Compute $n=pq$ and $\lambda=lcm(p-1,q-1)$.
3. 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$.
4. 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 Paillier's original scheme.
• The public (encryption) key is $(n, g)$.
• The private (decryption) key is $d$.

## Encryption Edit

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

## Decryption Edit

1. Ciphertext $c\in \mathbb Z^{*}_{n^{s+1}}$
2. 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}$.
3. 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 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 $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.