Damgård–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.

Key generation

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

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}}$ .

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 $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

↑ 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 t e Public-key cryptography

Algorithms	Benaloh Blum–Goldwasser Cayley–Purser CEILIDH Cramer–Shoup Damgård–Jurik DH DSA EPOC ECDH ECDSA EKE ElGamal signature scheme GMR Goldwasser–Micali HFE IES Lamport McEliece Merkle–Hellman MQV Naccache–Stern Naccache–Stern knapsack cryptosystem NTRUEncrypt NTRUSign Paillier Rabin RSA Okamoto–Uchiyama Schnorr Schmidt–Samoa SPEKE SRP STS Three-pass protocol XTR

Theory	Discrete logarithm Elliptic curve cryptography RSA problem

Standardization	CRYPTREC IEEE P1363 NESSIE NSA Suite B

Topics	Digital signature OAEP Fingerprint PKI Web of trust Key size

v t e Cryptography

History of cryptography Cryptanalysis Cryptography portal Outline of cryptography

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

This article is issued from Wikipedia. The text is available under the Creative Commons Attribution/Share Alike; additional terms may apply for the media files.