Code360 powered by Coding Ninjas X Naukri.com. Code360 powered by Coding Ninjas X Naukri.com
Table of contents
1.
Introduction
2.
The Paillier Cryptosystem
3.
Encryption in the Paillier Cryptosystem
4.
Decryption in the Paillier Cryptosystem
5.
Example
6.
Homomorphic Properties
6.1.
Addition of two Ciphertexts
6.2.
Multiplication of a Ciphertext by a Plaintext
7.
The Paillier Cryptosystem in Electronic Voting
8.
Frequently Asked Questions
8.1.
What is the Paillier Cryptosystem?
8.2.
What are the prominent helper functions used in the encryption of the Paillier Cryptosystem?
8.3.
What are the applications of the Paillier Cryptosystem?
8.4.
What is homomorphic property?
9.
Conclusion
Last Updated: Mar 27, 2024

The Paillier Cryptosystem

Master Python: Predicting weather forecasts
Speaker
Ashwin Goyal
Product Manager @

Introduction

Sometimes when the message’s intended recipient needs to be the only person who should know the information, there is a need for some encryption techniques to maintain privacy in message transmission. Techniques such as “shift-ciphers” were used in the early days for encrypting messages. In this method, an alphabet is replaced by some other alphabet, and a private key is used to decrypt the message.

Introduction

In those techniques, the private key needs to be sent along with the message, which again makes the message highly contingent. To meet this problem, “public key” cryptosystems were invented. One of the public key cryptosystems is The Paillier Cryptosystem.

The Paillier Cryptosystem

The Paillier Cryptosystem is a modular, public key encryption technique. It was created by and named after Pascal Paillier with some properties. To study the encryption and decryption techniques used in this method, we must know about modular arithmetic and converting an alphanumeric message into a purely numeric message. If you have no idea or want to revise these topics, refer here.

Paillier Cryptography

That message can be broken down into N blocks (N is predetermined). The term plaintext refers to a numeric message that is not yet encrypted. The term cipher denotes the plaintexts that have been encrypted but not yet decrypted.

Get the tech career you deserve, faster!
Connect with our expert counsellors to understand how to hack your way to success
User rating 4.7/5
1:1 doubt support
95% placement record
Akash Pal
Senior Software Engineer
326% Hike After Job Bootcamp
Himanshu Gusain
Programmer Analyst
32 LPA After Job Bootcamp
After Job
Bootcamp

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 n2.
  • Calculate the modular multiplicative inverse 𝛍 = (L(gλ mod n2))−1 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 = gm . rn mod n2 .

Decryption in the Paillier Cryptosystem

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

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

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

np*q = 221

λ =LCM(12,16) = 48

= 4886 (Random between 1 and 2212)

μ(L(gλ mod n2))−1 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 = 25889 mod 2212.

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

Mdecrypted = 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.

Dpriv( Epub ( m) ⋅ Epub ( m) mod n) = m1+mmod 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.

Dpriv( Epub ( m)m2 mod n) = m1⋅mmod n

Here, Dpriv means decryption using the private key, and Epub means encryption using the public key. M1 and m2 are blocks of message or plaintext.

The Paillier Cryptosystem in Electronic Voting

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:

Happy Coding!

Previous article
Boneh-Franklin Identity-Based Cryptosystem
Next article
Identifiable Parent Property
Live masterclass