Damgård–Jurik cryptosystem

The Damgård - Jurik cryptosystem is semantically secure, asymmetric encryption algorithm. It was presented in 2001 at the conference of the two PKC cryptographers Ivan Damgård and Mads Jurik. The process is additive - homomorphic, meaning that the plaintexts are added by the multiplication of two key texts. It is therefore not necessary to decrypt the key texts in order to operate on the plaintexts can. The method is a successor of the Paillier cryptosystem and includes this as a special case.

• 3.1 Advantages
• 3.2 disadvantages

Method

Generation of public and private key

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

• One chooses two large primes of the same bit length, and defines. In practice, 1536-2048 bits should be long.
• One defines.
• We choose so that relatively prime for a known to and to being isomorphic.
• By means of the Chinese remainder theorem to calculate with and.

The public key is made, from the private.

Note: To get the Paillier cryptosystem as a special case, and selects one. Furthermore, one can always choose without compromising the security. In particular it must not be fixed to advance in this case, but ad hoc can be selected when encrypting a message.

Encrypting messages

To encrypt a message, the procedure is as follows:

• We choose in random.
• One calculates the ciphertext as.

Decrypt messages ( decoding)

To decrypt a ciphertext, the procedure is reasonably successor:

• Man charged. For valid key texts must apply:

Here, as one that has in the order. On the other hand, it should be noted that, where order has, and order, as too is isomorphic, and is. Furthermore, both are ( by definition ) and elements of.

• Now one applies recursively to the decryption mechanism of the Paillier cryptosystem to compute. As is known, can now be calculated as.

Security

Under the decisional composite Residuosity assumption it can be shown that the method is semantically secure against Chosen - plaintext attacks. This assumption states that for a composite module can not be checked efficiently whether a one - th root modulo possesses or not.

Homomorphieeigenschaften

The Damgård - Jurik cryptosystem is additively homomorphic - whereby unknown plaintexts can be added by operations on ciphertexts:

• By multiplication of two key texts encrypted plaintexts are added:

• By multiplying a ciphertext with an arbitrary value to the encrypted plaintext can be added:

• By multiplying a ciphertext with an encryption can be randomized by again without changing the message:

• By exponentiation of the ciphertext with a natural number can be ver -w- kindled the encrypted message

However, there is no known way to multiply by operations on two key texts which contained messages with each other.

Benefits

The homomorphic properties are exploited among others in connection with the following applications.

• E- Voting: After every voter his voice (in the simplest case, a 1 for yes, 0 for no) is encrypted and transmitted to the electoral authority, all ciphertexts are multiplied, and the resulting encryption, the encryption of the total number of votes in favor. Is now obtained by decrypting the election results. It is important that the first step performing party does not require any knowledge of the secret key, whereby no individual voices can be decrypted.
• eCash
• Zero - knowledge proofs in the Universal Composability model

Disadvantages

Because of the listed Homomorphieeigenschaften the method is, however, not IND -CCA - secure, that is not safe under Chosen - ciphertext attacks. Each encryption system that owns this security, it would need to be non- deformable, a property that is in contradiction to the homomorphism. In the literature, there are also transformations to transform the Damgård - Jurik cryptosystem into an IND -CCA - secure variant. If these transformations are attached or not, depends on the particular application.

Swell

• Asymmetric encryption algorithm