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.

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.

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.

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^{2}.

Calculate themodular multiplicative inverse 𝛍 = (L(g^{λ} mod n^{2}))^{−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 = g^{m} . r^{n} mod n^{2} .

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^{2}.

Now the plaintext can be recalculated as m = L(c^{λ }mod n^{2 }).μ mod^{n}.

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^{2})

μ = (L(g^{λ} mod n^{2}))^{−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 c =25889 mod 221^{2}.

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_{1 }) ⋅ E_{pub }( m_{2 }) mod n^{2 }) = m_{1}+m_{2 }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_{1 })^{m2} mod n^{2 }) = m_{1}⋅m_{2 }mod n

Here, D_{priv} means decryption using the private key, and E_{pub} means encryption using the public key. M1_{ }and m_{2} 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.