The Paillier Cryptosystem

Encryption in the Paillier Cryptosystem

First, we will look at some helper functions.

• LCM (a, b): It outputs the least common multiple of a and b.
• GCD (a, b): It outputs the Greatest Common Divisor of a and b.

Now we can start our task of key generation.

• Pick two large prime numbers, p, and q, randomly. Confirm that gcd(pq, (p-1)(q-1)) is 1. If not, pick another pair of prime numbers.
• Compute n = p*q.
• Define function L(x) = (x−1) / n.
• Compute 𝝺 as LCM(p-1, q-1).
• Pick a random integer g in the set 1 to n².
• Calculate the modular multiplicative inverse 𝛍 = (L(g^λ mod n²))⁻¹ mod n. If no 𝛍 exists, then restart from step 1.
• The public key is (n, g), which can be used for encryption.
• The private key is 𝝺 which can be used for decryption.

Any block m of the message in the range 0 ≤ m < n can be encrypted as

• Pick any random number r in the range 0 < r < n.
• Compute the cyphertext c = g^m . rⁿ mod n² .

Decryption in the Paillier Cryptosystem

Looking at the above encryption algorithm, we can see that each cyphertext c will be such that 0 < c < n².

Now the plaintext can be recalculated as m = L(c^λ mod n² ).μ modⁿ.

Also, λ and μ can be recalculated from the public key.

Example

Pick p = 13 and q = 17. This pair satisfies the condition mentioned. Then the key can be computed as

n = p*q = 221

λ =LCM(12,16) = 48

g = 4886 (Random between 1 and 221²)

μ = (L(g^λ mod n²))⁻¹ mod n = 159.

Now for a block, m = 123. We can pick any random number r in the acceptable range. So our cipher c will be c = 25889 mod 221².

Using the method specified above, we can decrypt the message as follows:

M_decrypted = 123 mod 221.

This method is used in the Paillier Cryptosystem for encryption and decryption. Now we will look at some of the properties followed by the cipher generated.

Homomorphic Properties

The Paillier cryptosystem is a partially homomorphic encryption scheme that allows two types of computation:

• Addition of two ciphertexts
• Multiplication of ciphertext by a plaintext number

Addition of two Ciphertexts

When two ciphertexts are multiplied, then the decryption of the result will be the sum of their plaintexts.

D_priv( E_pub ( m₁ ) ⋅ E_pub ( m₂ ) mod n² ) = m₁+m₂ mod n

Multiplication of a Ciphertext by a Plaintext

When a Ciphertext is raised to the power of any plaintext, then the decryption of the result will be the product of their plaintexts.

D_priv( E_pub ( m₁ )^m2 mod n² ) = m₁⋅m₂ mod n

Here, D_priv means decryption using the private key, and E_pub means encryption using the public key. M1 and m₂ are blocks of message or plaintext.

The Paillier Cryptosystem in Electronic Voting

Imagine a voting situation where one needs to vote in favor or opposition to something. So a vote in favor can be represented by a plaintext 1, and a vote in resistance can be represented by a plaintext 0. Each voter chooses a random r to encrypt their vote. But the public key (n, g) is the same. A total count of the votes is maintained as x. Then all the encrypted votes are multiplied together, and the result is decrypted as y. Since multiplying encrypted text results in the addition of plaintexts, this process will add 1s and 0s as y. So y is the sum of all the votes in favor.

We can see that we don’t need to know who voted in what favor to get the results.

Frequently Asked Questions

What is the Paillier Cryptosystem?

The Paillier cryptosystem, invented by Pascal Paillier in 1999, is an asymmetric probabilistic algorithm for public key encryption.

What are the prominent helper functions used in the encryption of the Paillier Cryptosystem?

The prominent helper functions used in the encryption of the Paillier Cryptosystem are the least common multiple or the LCM function and the greatest common divisor or the HCF function.

What are the applications of the Paillier Cryptosystem?

The Paillier cryptosystem is widely used in the following situations:

• Electronic voting.
• Electronic Cash.
• Threshold cryptosystem.

What is homomorphic property?

The Paillier cryptosystem is a partially homomorphic encryption scheme. It allows two types of computation:

• Addition of two ciphertexts.
• Multiplication of ciphertext by a plaintext number.

Conclusion

In this article, we have extensively discussed the Paillier Cryptosystem. Its encryption and decryption technique, along with its applications.

We hope that this blog has helped you enhance your knowledge of Paillier Cryptosystem, and if you would like to learn more, check out our articles on Cryptosystem, Public Key Cryptography, and What are basic Cryptography tools? Do upvote our blog to help other ninjas grow. 

Recommended Readings:

• Difference between Public Key and Private Key
• Monte Carlo Simulation
   

Happy Coding!