Damgaard-Jurik cryptosystem

From Wikipedia, the free encyclopedia

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.

1 Key generation
2 Encryption
3 Decryption
4 Simplification
5 References

[edit] Key generation

Choose two large prime numbers p and q randomly and independently of each other.
Compute $n = p q$ and $λ = l c m (p - 1, q - 1)$ .
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$ .
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 $λ$ as in Palliers original scheme.

The public (encryption) key is $(n, g)$ .
The private (decryption) key is $d$ .

[edit] Encryption

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

[edit] Decryption

Ciphertext $c\in \mathbb Z^{*}_{n^{s+1}}$
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}$ .
Apply a recursive version of the Paillier decryption mechanism to obtain $j m d$ . As $j d$ is known, it is possible to compute $m=(jmd)\cdot (jd)^{-1} \;mod\;n^s$ .

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

[edit] References

^ Ivan Damgård, Mads Jurik: A Generalisation, a Simplification and Some Applications of Paillier's Probabilistic Public-Key System. Public Key Cryptography 2001: 119-136

v • d • e Public-key cryptography

Algorithms: CEILIDH \| Cramer-Shoup \| DH \| DSA \| ECDH \| ECDSA \| EKE \| ElGamal encryption \| ElGamal signature scheme \| GMR \| IES \| Lamport \| MQV \| NTRUEncrypt \| NTRUSign \| Paillier \| Rabin \| RSA \| Schnorr \| SPEKE \| SRP \| XTR

Theory: Discrete logarithm \| Elliptic curve cryptography \| RSA problem

Standardization: ANS X9F1 \| CRYPTREC \| IEEE P1363 \| NESSIE \| NSA Suite B

Misc: Digital signature \| Fingerprint \| PKI \| Web of trust \| Key size

v • d • e Cryptography

History of cryptography \| Cryptanalysis \| Cryptography portal \| Topics in cryptography

Symmetric-key algorithm \| Block cipher \| Stream cipher \| Public-key cryptography \| Cryptographic hash function \| Message authentication code \| Random numbers \| Steganography