Damgaard-Jurik cryptosystem

Damgaard-Jurik cryptosystem

The Damgård-Jurik cryptosystem [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] 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 imes 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=lcm(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 lambda as in Palliers 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 min mathbb Z_{n^s}.
#Select random r where rin mathbb Z^{*}_{n^{s+1 .
#Compute ciphertext as: c=g^m cdot r^{n^s} mod n^{s+1} .

Decryption

#Ciphertext cin 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 thatd=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


Wikimedia Foundation. 2010.

Игры ⚽ Поможем решить контрольную работу

Look at other dictionaries:

  • Private information retrieval — In cryptography, a private information retrieval (PIR) protocol allows a user to retrieve an item from a server in possession of a database without revealing which item she is retrieving. PIR is a weaker version of 1 out of n oblivious transfer,… …   Wikipedia

Share the article and excerpts

Direct link
Do a right-click on the link above
and select “Copy Link”