In today’s world, data security is a crucial concern for individuals and organizations alike. Encryption is a popular technique used to safeguard sensitive information from unauthorized access. However, traditional encryption methods have limitations when it comes to performing computations on encrypted data. This is where homomorphic encryption comes in. Homomorphic encryption allows computations to be performed on encrypted data without the need for decryption. In this blog post, we will explore Paillier encryption, a partially homomorphic encryption scheme that enables computations on encrypted data with respect to addition and multiplication. We will delve into the math behind the algorithm and its homomorphic features, demonstrating how it can be implemented step-by-step in Python. This post will be an excellent resource for those looking to understand the principles of partially homomorphic encryption with Paillier and its use cases.
Vlog
You can either continue to read this tutorial or watch the following video. They both cover the implementation of Paillier cryptosystem with its homomorphic features in python programming language.
šāāļø You may consider to enroll my top-rated cryptography course on Udemy
š Python Library
In this post, we will mostly focus on the math behind the cryptosystem and implement it from scratch. If you are interested in how to use the algorithm easy and fast instead of its mathematical foundation, then you may consider to use LightPHE.
LightPHE is a lightweight partially homomorphic encryption library for python. It wraps many partially homomorphic algorithms such as RSA, ElGamal, Exponential ElGamal, Elliptic Curve ElGamal, Paillier, Damgard-Jurik, OkamotoāUchiyama, Benaloh, NaccacheāStern, GoldwasserāMicali. With LightPHE, you can build homomorphic crypto systems with a couple of lines of code, encrypt & decrypt your data and perform homomorphic operations such as homomorphic addition, homomorphic multiplication, homomorphic xor, regenerate cipher texts, multiplying your cipher text with a known plain constant according to the built algorithm.
# pip install lightphe from lightphe import LightPHE # build a cryptosystem cs = LightPHE(algorithm_name = 'Paillier') # define plaintexts m1 = 17 m2 = 23 # calculate ciphertexts c1 = cs.encrypt(m1) c2 = cs.encrypt(m2) # performing homomorphic addition on ciphertexts assert cs.decrypt(c1 + c2) == m1 + m2 # scalar multiplication (increase its value 5%) k = 1.05 assert cs.decrypt(k * c1) == k * m1
You may consider to watch the LightPHE demo video.
Now, let’s turn back to understand and implement the crypto system from scratch!
Pre-requisites
Similar to RSA, we are firstly expected to pick two different large primes.
p = 13 q = 17 assert p != q
We should perform the primeness tests for p and q.
def is_prime(n):
for i in range(2, n): # [2, n)
if n % i == 0:
return False
return True
# ---------------------------------
assert is_prime(p)
assert is_prime(q)
We then calculate the totient function of n where n is the multiplication of two primes we just picked.
import math n = p*q phi = (p-1)*(q-1) assert math.gcd(n, phi) == 1
Paillier cryptosystem depends on a L function such that L(x) = (x-1)/n. Notice that result of function L must be integer always. We will use this function in optionally key generation and decryption.
def lx(x):
y = (x-1)/n
assert y - int(y) == 0
return int(y)
Key Generation
We are going to generate generator g, lamdba and mu. According to the original paper,
- g should be picked randomly in range of [0, n*n]
- Lambda is the least common multiple (lcm) of p-1 and q-1. Lcm function comes with python 3.9.
- Mu should be calculated with the formula such that Ī¼ = ( L(gĪ» mod n2) )-1
g = random.randint(0, n*n) lmbda = math.lcm(p-1, q-1) mu = pow(lx(pow(g, lmbda, n*n)), -1, n)
Instead, we are simply able to generate these values as:
- g should be equal to n plus 1
- lambda should be equal to the totient function of n or shortly phi
- mu is equal to the multiplicative inverse of lambda in mod n
g = n + 1 lmbda = phi * 1 mu = pow(lmbda, -1, n)
This simplified variant is recommended for implementation purposes because of required time.
So, public key will be n, g and mu to encrypt messages whereas private key will be lambda to decrypt messages.
Encryption and decryption theory
To encrypt a message, we are going to calculate the message-th power of generator times n-th power of a random integer in modulus n squared.
c = gm . rn (mod n2)
Then, we are able to restore a message from ciphertext c with the following formula.
m = L(cĪ» mod n2) x Ī¼ (mod n)
Proof of Paillier decryption
You can skip to the next topic if you are not interested in the math behind the algorithm.
Remember the ciphertext calculation formula first.
c = gm . rn (mod n2)
We have set generator g to n+1.
c = (1+n)m . rn (mod n2)
Plaintext restoration requires to find lambda-th power of ciphertext.
cĪ» = ( (1+n)m . rn )Ī» mod n2
Move lambda-th power into the parenthesis
cĪ» = (1+n)mĪ» . rnĪ» mod n2
Please focus on the term rnĪ» mod n2, we have set lambda to totient function Ļ(n) in the simplified key generation.
rnĻ(n) mod n2
Besides, totient function of n-squared is n times Ļ(n) if n is the multiplication of two prime numbers.
Ļ(n2) = n.Ļ(n)
where n=pq and p and q are prime numbers.
So, the term – rnĻ(n) mod n2 – is exactly same with the Fermat-Euler Theorem. This has to be 1 according to this theorem. In that way, we can simplify the lambda-th power of ciphertext.
cĪ» = (1+n)mĪ» mod n2
To expand the mĪ»-th power of (1+n), we are going to use binomial theorem.
(x+y)n = C(n, 0).xny0 + C(n, 1).xn-1y1 + C(n, 2).xn-2y2 + …
Apply binomial theorem to the (1+n)mĪ»
(1+n)mĪ» = C(mĪ», 0)1mĪ»n0 + C(mĪ», 1)1mĪ»-1n1 + C(mĪ», 2)1mĪ»-2n2 + … mod n2
(1+n)mĪ» = 1 + nmĪ» + C(mĪ», 2)1mĪ»-2n2 + … mod n2
Since the third term, all items are divisible by n2. And we are working on mod n2. That is why, we can ignore these terms and have much simplified expression.
(1+n)mĪ» = 1 + nmĪ» mod n2
Now, please focus on the decryption.
m = L(cĪ» mod n2) x Ī¼ (mod n)
Replace lambda-th power of ciphertext in the plaintext restoration formula.
m = L(1 + nmĪ» mod n2) x Ī¼ (mod n)
Formula of function L is such that
L(u) = (u-1)/n
Expand the formula L in the plaintext restoration.
m = ( (1 + nmĪ» – 1)/n ) x Ī¼ (mod n)
Plus 1 and minus 1 terms and also n terms in the dividend and divisor can be simplified.
m = mĪ» x Ī¼ (mod n)
We have set Ī¼ to multiplicative inverse of totient function in modulus n. We also set Ī» to totient function itself. So, multiplication of Ī» and Ī¼ must be 1.
m = m (mod n)
As you can see, Paillier decryption is proven because m is equal to m always!
Encryption and decryption implementation
So, we are going to use following function to encrypt and decrypt messages. Notice that modulus is n squared is required in encryption whereas n itself is required in decryption.
def encrypt(m, r):
assert math.gcd(r, n) == 1
c = ( pow(g, m, n*n) * pow(r, n, n*n) ) % (n*n)
return c
def decrypt(c):
p = ( lx(pow(c, lmbda, n*n)) * mu ) % n
return p
Encryption and decryption
Suppose that we want to encrypt a message 123. We will also need to generate a random integer for each encryption.
m = 123 r = random.randint(0, n) c = encrypt(m, r) p = decrypt(c) assert p == m
Additive homomorphic feature
To encrypt a message, we are using a formula such that
E(m, r) = gm . rn (mod n2)
Let’s encrypt a message pair according to this formula.
E(m1, r1) = gm1 . r1n (mod n2)
E(m2, r2) = gm2 . r2n (mod n2)
Multiply these two encrypted messages
E(m1, r1).E(m2, r2) = gm1.gm2.r1n.r2n (mod n2)
Here, g bases and n exponents are common. We can simplify this as
E(m1, r1).E(m2, r2) = gm1+m2.(r1.r2)n (mod n2)
On the other hand, if we encrypt the sum of these message pair with the multiplication of its random keys, we will have same result.
E(m1+m2, r1.r2) = gm1+m2.(r1.r2)n (mod n2)
So, Paillier is homomorphic with respect to the addition.
Additive homomorphic implementation
Let’s encrypt a message pair with Paillier cryptosystem.
m1 = 123 r1 = random.randint(0, n) m2 = 37 r2 = random.randint(0, n) c1 = encrypt(m1, r1) c2 = encrypt(m2, r2)
The following rule must be satisfied always because we proven Paillier is homomorphic with respect to the addition.
assert (c1*c2) % (n*n) == encrypt(m1 + m2, r1*r2)
Re-encrypting a ciphertext with the neutral element
Neutral element in addition is 0. If we add 0 to something, we must have same value. This rule is valid in Paillier. But Paillier has one to many mapping. In other words, a plaintext should have many ciphertext. If we multiply something to the encrypted neutral element, then we should have different ciphertexts but this should not affect plaintext.
m1 = 123 r1 = random.randint(0, n) c1 = encrypt(m1, r1) m2 = 0 r2 = random.randint(0, n) c2 = encrypt(m2, r2) c1_reencrypted = (c1*c2) % (n*n) assert c1 != c1_reencrypted assert decrypt(c1) == decrypt(c1_reencrypted)
This usage is very common in e-voting applications. Imagine that a political party got same votes in many ballot boxes. We can re-encrypt that number of votes with neutral element and we have many different ciphertexts. However, we will have same plaintext when we decrypt it.
Multiplicative homomorphic feature
Remember that we are using the following rule to encrypt messages
E(m, r) = gm . rn (mod n2)
Let’s encrypt a message m1 according to this rule.
E(m1, r1) = gm1 . r1n (mod n2)
Then, let’s find the message m2-th power of encrypted message m1. Notice that E(m1, r1) is encrypted but m2 is plain here.
E(m1, r1)m2 = (gm1 . r1n)m2 (mod n2)
Let’s apply the m2 power into the parenthesis.
E(m1, r1)m2 = gm1m2 . r1nm2 (mod n2)
On the other hand, if we encrypt the multiplication of m1 and m2 with the random key m2-th power of r1, we will have the same result.
E(m1m2, r1m2) = gm1m2 . r1nm2 (mod n2)
Multiplicative homomorphic implementation
Let’s encrypt a message pair first.
m1 = 123 r1 = random.randint(0, n) c1 = encrypt(m1, r1) m2 = 25 r2 = random.randint(0, n) c2 = encrypt(m2, r2)
The following rules must be satisfied because we proven the multiplicative homomorphic feature of Paillier.
assert pow(c1, m2, n*n) == encrypt(m1*m2, pow(r1, m2, n*n)) assert pow(c2, m1, n*n) == encrypt(m1*m2, pow(r2, m1, n*n))
Why Paillier is not fully homomorphic
Even though Paillier has both additive and multiplicative homomorphic features, this does not make it fully homomorphic. In its multiplicative feature, we have to use a plain message-th power of a encrypted message. In fully homomorphic encryption, we should perform the multiplication of two encrypted values.
Conclusion
So, we have mentioned Paillier cryptosystem with its homomorphic features and implement it in python programming language from scratch. In contrast to RSA and ElGamal, Paillier comes with additive and homomorphic features by default. This made the crypto-system very popular in the past for real world homomorphic encryption applications such as e-voting. Still, the crypto-system is not fully homomorphic.
I pushed the source code of this experiment to GitHub. You can support this study if you star its repo.
Like this blog? Support me on Patreon
