Damgård–Jurik cryptosystem

Key generation

1. Choose two large prime numbers p and q randomly and independently of each other.
2. Compute n=pq and \lambda=\operatorname{lcm}(p-1,q-1).
3. Choose an element g \in \mathbb{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 \mathbb{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

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

Decryption

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

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

References

1. [[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