Paillier cryptosystem

The Paillier cryptosystem was introduced in 1999 by Pascal Paillier at Eurocrypt. It is an asymmetric cryptosystem whose security is based on that for a composite module can not be checked efficiently whether an item in a - th root modulo possesses or not. A special feature of the Paillier cryptosystem is that two encrypted messages can be added, without decrypting the messages previously.

The process is often referred to as successor of the Okamoto - Uchiyama cryptosystem. Furthermore, it is a special case of Damgård - Jurik cryptosystem.

  • 3.1 Advantages
  • 3.2 disadvantages
  • 4.1 Key Generation
  • 4.2 Preliminary work
  • 4.3 encryption
  • 4.4 decryption

Method

In the following, we describe the key generation, and the algorithms for encryption and decryption of messages.

Generation of public and private key

The key pair is generated as follows:

  • It generates two random prime numbers, so true. In practice, n should be at least 1024, but have better 1536 or 2048 binary digits. It then sets well.
  • It randomly chooses in, so that the order of divides.

The public key consists of the private key from.

Simplification: The key generation can also be simplified as follows:

  • One chooses a security parameter, and the two primes in random, ie with the same bit length.
  • One defines, as well.

Encrypting messages

To encrypt a message, the procedure is as follows:

  • First you choose a random.
  • The encrypted message is then given by.

Decrypt messages ( decoding)

To decrypt first defined the function. For a ciphertext one then proceeds as follows:

  • One is, the logarithmic function from above.

In this step, it should be noted that the modulo division needs to be performed, i.e., . By multiplication by the multiplicative inverse The division in the calculation of the logarithmic function is performed over the integers.

Simplification: If you have chosen the simplified variant of the key generation, the decoding results for:

  • It is where the division is modulo understand them again.

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 an item in a - th root modulo possesses or not.

Homomorphieeigenschaften

The Paillier 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 with a key text, ie the addition of the encoded value "0", an encryption may be randomly reapplied 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 Paillier cryptosystem into an IND -CCA - secure variant. If these transformations are attached or not, depends on the particular application.

Complete Example

The above steps will be illustrated here with a simple example.

Key generation

First, we choose the security parameter, then and. This now allows us to choose the simplified version of the key generation. Thus we obtain:

The public key is thus given by:

The secret key is.

Preparatory work

In a first step, the text to be encrypted must be smaller than translated into numbers. We simply replace each letter to its position in the alphabet:

A = 01 B = 02 C = 03, etc. (00 = space ) We now encode three characters at a time, as four consecutive letters under certain circumstances could provide a too large value.

Plaintext: P A I L L I E R Encoding: 16 01 09 12 12 09 05 18 00 encoding

We have three to encrypt plaintexts ( and ) for which we need one.

R1 = 12312 r2 = 623 543 r3 = 215 688 The encryption result is then:

Ci = gmirin mod n2 c1 = 899 778 160 109 809 598 649 729 = 594 091 908 920 12,312,899,777 mod c2 = 508 000 332 395 c3 = 8964598855 decryption

Since we had chosen the simplified variant for key generation, we can decrypt the message by:

Mi = L ( ci mod n2) / mod n Important here is that the division is performed. We therefore calculated using the extended Euclidean algorithm, the multiplicative inverse of modulo, and get it. Thus, the decoding results for:

M1 = L ( 594091908920897876 mod 809 598 649 729 ) * 141522 mod 899 777 = 160109 m2 = 121209 m3 = 051 900 By inverting the substitution rule, these values ​​can be translated into letters again.

Public-key cryptography Okamoto–Uchiyama cryptosystem Group homomorphism
629897
de