Damgård Jurik cryptosystem

The Damgård Jurik cryptosystem is a semantically secure , asymmetric encryption algorithm . It was presented at the PKC conference in 2001 by the two cryptographers Ivan Damgård and Mads Jurik . The method is additive-homomorphic, which means that the plain texts are added by multiplying two key texts. It is therefore not necessary to decrypt the key texts in order to be able to operate on the plain texts . The method is a successor to the Paillier cryptosystem and contains this as a special case.

Procedure

Generation of the public and private key

The generation of the public and private key works as follows.

• You choose two large prime numbers of the same bit length and define . In practice it should be between 1536 and 2048 bits long. ${\displaystyle p,q}$ ${\displaystyle n=pq}$ ${\displaystyle n}$
• One defines . ${\displaystyle \lambda =\operatorname {kgV} (p-1,q-1)}$
• One chooses such that for a known relatively prime to and , where is isomorphic to . ${\displaystyle g\in (\mathbb {Z} /n^{s+1}\mathbb {Z} )^{*}}$ ${\displaystyle g=(1+n)^{j}x\mod n^{s+1}}$ ${\displaystyle j}$ ${\displaystyle n}$ ${\displaystyle x\in H}$ ${\displaystyle H}$ ${\displaystyle (\mathbb {Z} /n\mathbb {Z} )^{*}}$
• Using the Chinese remainder , one calculates with and . ${\displaystyle d}$ ${\displaystyle d\mod n\in (\mathbb {Z} /n\mathbb {Z} )^{*}}$ ${\displaystyle d=0\mod \lambda }$

The public key consists of , the private one . ${\displaystyle (n,g)}$ ${\displaystyle d}$

Note : To get the Paillier cryptosystem as a special case, choose and . You can always choose further without compromising security. In particular, in this case there is no need to fix in advance, but can be selected ad hoc when encrypting a message. ${\displaystyle s=1}$ ${\displaystyle d=\lambda }$ ${\displaystyle g=1+n}$ ${\displaystyle s}$

Encrypt messages

To encrypt a message , proceed as follows: ${\displaystyle m\in (\mathbb {Z} /n^{s}\mathbb {Z} )}$

• One randomly chooses in . ${\displaystyle r}$ ${\displaystyle (\mathbb {Z} /n^{s+1}\mathbb {Z} )^{*}}$
• The key text is calculated as . ${\displaystyle c=g^{m}\cdot r^{n^{s}}\mod n^{s+1}}$

Decrypting messages (decoding)

To decipher a ciphertext, proceed as follows: ${\displaystyle c}$

• One calculates . The following must apply to valid key texts : ${\displaystyle c^{d}\mod n^{s+1}}$ ${\displaystyle c}$

${\displaystyle 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}}\mod n^{s+1}}$.

While using one hand, that in the order has. On the other hand, it should be noted that where has order , and order , since is isomorphic to , and is. Furthermore, both (by definition) and are elements of . ${\displaystyle (1+n)}$ ${\displaystyle (\mathbb {Z} /n^{s+1}\mathbb {Z} )^{*}}$ ${\displaystyle n^{s}}$ ${\displaystyle (\mathbb {Z} /n^{s+1}\mathbb {Z} )^{*}\equiv G\times H}$ ${\displaystyle G}$ ${\displaystyle n^{s}}$ ${\displaystyle H}$ ${\displaystyle \lambda =\operatorname {kgV} (p-1,q-1)}$ ${\displaystyle H}$ ${\displaystyle (\mathbb {Z} /n\mathbb {Z} )^{*}}$ ${\displaystyle d=0\mod \lambda }$ ${\displaystyle x}$ ${\displaystyle r^{n^{s}}}$ ${\displaystyle H}$

• If one applies recursively the decryption mechanism of Paillier cryptosystem in order to calculate. Since are known, one can now calculate as . ${\displaystyle jmd}$ ${\displaystyle j,d}$ ${\displaystyle m}$ ${\displaystyle m=(jmd)\cdot (jd)^{-1}\mod n^{s}}$

safety

Under the Decisional Composite Residuosity assumption, it can be shown that the method is semantically secure against selected plaintext attacks . This assumption states that for a composite module can not be checked effectively if a one th root modulo has or not. ${\displaystyle n}$ ${\displaystyle (\mathbb {Z} /n^{2}\mathbb {Z} )}$ ${\displaystyle n}$ ${\displaystyle n^{2}}$

Homomorphism properties

The Damgård-Jurik cryptosystem is additive- homomorphic , which means that unknown plaintexts can be added through operations on key texts :

• By multiplying two key texts , the encrypted plain texts are added: ${\displaystyle c_{1},c_{2}}$ ${\displaystyle m_{1},m_{2}}$

${\displaystyle g^{m_{1}}r_{1}^{n^{s}}\cdot g^{m_{2}}r_{2}^{n^{s}}=g^{m_{1}+m_{2}}(r_{1}r_{2})^{n^{s}}=g^{m_{1}+m_{2}}r'^{n^{s}}\mod n^{s+1}}$.

Sometimes two special cases are of particular interest:

• By multiplying a ciphertext with an arbitrary value can for encrypted clear text is added: ${\displaystyle c}$ ${\displaystyle g^{\Delta m}}$ ${\displaystyle \Delta m}$ ${\displaystyle m}$

${\displaystyle g^{m}r^{n^{s}}\cdot g^{\Delta m}=g^{m+\Delta m}r^{n^{s}}\mod n^{s+1}}$.

• By multiplying a ciphertext by , an encryption of can be randomized again without changing the message : ${\displaystyle c}$ ${\displaystyle \Delta r^{n^{s}}}$ ${\displaystyle m}$ ${\displaystyle m}$

${\displaystyle g^{m}r^{n^{s}}\cdot \Delta r^{n^{s}}=g^{m}(r\Delta r)^{n^{s}}=g^{m}r'^{n^{s}}\mod n^{s+1}}$.

• By exponentiation of a key text by a natural number , the encrypted message comparable w -facht be ${\displaystyle c}$ ${\displaystyle w}$ ${\displaystyle m}$

${\displaystyle (g^{m}r^{n^{s}})^{w}=g^{wm}(r^{w})^{n^{s}}=g^{wm}r'^{n^{s}}\mod n^{s+1}}$.

However, there is no known way to multiply the messages contained by operations on two key texts.

advantages

The homomorphic properties are u. a. exploited in connection with the following applications.

• E-voting : After each eligible voter has encrypted their vote (in the simplest case a 1 for yes , a 0 for no ) and transmitted it to the electoral authority, all key texts are multiplied and the resulting encryption contains the encryption of the total number of yes votes. The result of the election is obtained by decoding. It is important that the party performing the first step does not need to know the secret key, which means that no individual votes can be decrypted.
• eCash
• Zero-knowledge evidence in the universal composability model

disadvantage

Due to the listed homomorphism properties, however, the process is not IND-CCA-safe. H. not safe from elected ciphertext attacks . Every encryption system that has this security would have to be non-deformable , a property that contradicts homomorphism. In the literature one can also find transformations to transform the Damgård-Jurik cryptosystem into an IND-CCA-safe variant. Whether these transformations are appropriate or not depends on the particular application.

swell

1. ↑ Ivan Damgård, Mads Jurik: A Generalization, a Simplification and Some Applications of Paillier's Probabilistic Public-Key System . In: Kwangjo Kim (Ed.): Public Key Cryptography . tape 1992 . Springer, Berlin / Heidelberg 2001, ISBN 3-540-41658-7 , pp. 119-136 , doi : 10.1007 / 3-540-44586-2_9 .
2. ↑ Eiichiro Fujisaki, Tatsuaki Okamoto: How to Enhance the Security of Public-Key Encryption at minimum cost . In: Public Key Cryptography . tape 1560 . Springer, Berlin / Heidelberg 1999, ISBN 3-540-65644-8 , pp. 53-68 , doi : 10.1007 / 3-540-49162-7_5 .
3. ↑ Pascal Paillier, David Pointcheval: Efficient Public-Key Cryptosystems Provably Secure Against Active Adversaries . In: Kwok-Yan Lam, Eiji Okamoto, Chaoping Xing (Eds.): Advances in Cryptology - ASIACRYPT'99 . tape 1716 . Springer, Berlin / Heidelberg 1999, ISBN 3-540-66666-4 , pp. 165-179 , doi : 10.1007 / 978-3-540-48000-6_14 .