A Step by Step Partially Homomorphic Encryption Example with Damgard-Jurik in Python

In the world of data security and privacy, encryption plays a pivotal role in safeguarding sensitive information from prying eyes. One intriguing facet of encryption is homomorphic encryption, which allows us to perform computations on encrypted data without the need to decrypt it first. Among the various homomorphic encryption schemes, the Damgard-Jurik encryption method stands out as a powerful and efficient partially homomorphic encryption technique, serving as a generalized version of the well-known Paillier algorithm. In this blog post, we’ll take you through a step-by-step journey into the fascinating realm of additively homomorphic encryption with Damgard-Jurik in Python. By the end of this tutorial, you’ll not only understand the fundamental concepts but also be able to implement this additively homomorphic encryption scheme in your own Python projects. So, let’s embark on this cryptographic adventure and explore the inner workings of Damgard-Jurik encryption.

🐍 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.

---

🙋‍♂️ You may consider to enroll my top-rated cryptography course on Udemy

---

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 = 'Damgard-Jurik')

# 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!

Key Generation

Firstly, we will pick two large prime numbers p and q

import sympy

# generate prime numbers
p = sympy.randprime(1000, 2000)
q = sympy.randprime(1000, 2000)

Then, we will calculate n and ϕ(n) values similar to RSA. I set µ to multiplicative inverse of ϕ(n) in modulo n.

n = p*q
phi = (p-1)*(q-1)
mu = pow(phi, -1, n)

Thereafter, we will define the module n^s+1. If we set s to 1, then cryptosystem becomes Paillier.

s = 2
assert s >= 1

if s == 1:
    print('Cryptosystem is equivalent to Paillier')

modulo = pow(n, s+1)

Next, we will calculate the generator g which is equal to next number of n.

---

---

g = n + 1

Finally, public keys are (n, g) and private key is ϕ(n)

print(f'public keys is {n=}, {g=}')
print(f'private key is {phi=}')

Encryption

To encrypt a message m, we firstly need to generate a random integer ∈ {0, 1, 2, …, n} that must be coprime with n.

def generate_random():
    while True:
        r = random.randint(0, n)
        if math.gcd(r, n) == 1:
            break
    return r

r = generate_random()

Then, ciphertext will be generator g to the power of message times randon key to the power of n^s mod n^s+1.

c = g^m r ^{n^s} mod n^s+1

def encrypt(m, r):
    return ( pow(g, m, modulo) * pow(r, pow(n, s), modulo) ) % modulo

c = encrypt(m, r)

Logarithm over Cyclic Group

We are going to need a logarithm function over cyclic group.

L(x) = (x-1) /n

def lx(x):
    y = (x-1)/n
    assert y - int(y) == 0
    return int(y)

Decryption

To decrypt a ciphertext, we need to perform the following calculation:

m’ = L( c^ϕ(n) mod n^s+1 ) ϕ(n)^-1 mod n

def decrypt(c):
    return ( ( lx(pow(c, phi, modulo)) ) * mu ) % n

m_prime = decrypt(c)
assert m_prime == m

Homomorphic Features

Damgard-Jurik cryptosystem comes with additively homomorphic features. Multiplying the encryption of two messages is equivalent to encryption of their sum.

m1 = 17
r1 = 292
c1 = encrypt(m1, r1)

m2 = 22
r2  = 31
c2 = encrypt(m2, r2)

assert ( c1 * c2 ) % modulo == encrypt(m1+m2, (r1*r2))
assert decrypt(( c1 * c2 ) % modulo) == m1 + m2

Proof of Homomorphic Features

We performed the following calculation to encrypt a message with random key r.

---

---

E(m, s) = c = g^m r ^{n^s} mod n^s+1

If we encrypt m1 and m2 with random keys r1 and r2

E(m1, r1) = c₁ = g^m1 r₁ ^{n^s} mod n^s+1

E(m2, r2) = c₂ = g^m2 r₂ ^{n^s} mod n^s+1

Multiply two ciphertexts

E(m1, r1) . E(m2, r2) = g^m1 r₁ ^{n^s} g^m2 r₂ ^{n^s} mod n^s+1

According to the product rule of exponent rules, when multiplying two exponential terms with the same base, you can combine their exponents by addition.

E(m1, r1) . E(m2, r2) = g^m1+m2 (r₁r₂) ^{n^s} mod n^s+1

On the other hand, if we encrypt m1+m2 with random key r1.r2 then we will have same result

E(m1, r1) . E(m2, r2) = g^m1+m2 (r₁r₂) ^{n^s} mod n^s+1 = E(m1+m2, r1.r2)

---

---

So, we proven the partially homomorphic feature of Damgard-Jurik cryptosystem.

The Math Behind Decryption

We have been working on modulo n^s+1

ϕ(n^s+1) = ϕ((pq)^s+1) = ϕ(p^s+1q^s+1)

Totient function is a multiplicative function:

ϕ(p^s+1q^s+1) = ϕ(p^s+1).ϕ(q^s+1)

According to the prime power rule:

Φ(pⁿ) = p^(n-1)Φ(p)

The both p and q are primes. We can expand these as:

ϕ(p^s+1).ϕ(q^s+1) = (p^s+1-1)Φ(p).(q^s+1-1)Φ(q) = p^sΦ(p).q^sΦ(q)

ϕ(n^s+1) = p^s.q^s.Φ(p).Φ(q)

---

---

We can combine the multiplication of two totient functions in a single totient function

ϕ(n^s+1) = p^s.q^s.Φ(pq)

ϕ(n^s+1) = p^s.q^s.Φ(n)

Now, please focus on the encryption calculation

c = g^m r^ns mod n^s+1

g was calculated as (1+n)

c = (1+n)^m r^ns mod n^s+1

Let’s find the totient power of both sides

c^ϕ(n) = ( (1+n)^m r^ns )^ϕ(n) mod n^s+1

c^ϕ(n) = (1+n)^mϕ(n) r^(ns)ϕ(n) mod n^s+1

---

---

Please focus on the power of the second term

n^sϕ(n) = (pq)^sϕ(n) = p^sq^sϕ(n)

This is exactly equal to the ϕ(n^s+1) – we proven this already

n^sϕ(n) = ϕ(n^s+1)

Let’s replace this in the main equation

c^ϕ(n) = (1+n)^mϕ(n) r^nsϕ(n) mod n^s+1

c^ϕ(n) = (1+n)^mϕ(n) r^ϕ(ns+1) mod n^s+1

Second term vanishes because of Fermat-Euler Theorem.

c^ϕ(n) = (1+n)^mϕ(n) mod n^s+1

Let’s remember the binomial expansion.

---

---

(x+y)ⁿ = C(n, 0)(xⁿ)(y⁰) + C(n, 1)(x^n-1)(y¹) + C(n, 2)(x^n-2)(y²) + …

Now, we need to expand mϕ(n)-th power of (1+n) with binomial expansion. I will use ϕ instead of ϕ(n) in the following calculations to show it simpler.

(1+n)^mΦ = C(mΦ, 0)(1^mΦ)(n⁰) + C(mΦ, 1)(1^mΦ-1)(n¹) + C(mΦ, 2)(1^mΦ-2)(n²) + … mod n^s+1

Base 1 to any power will be 1.

(1+n)^mΦ = C(mΦ, 0)(n⁰) + C(mΦ, 1)(n¹) + C(mΦ, 2)(n²) + … mod n^s+1

The terms C(mΦ, 0) and n⁰ will be 1 as well

(1+n)^mΦ = 1 + C(mΦ, 1)(n¹) + C(mΦ, 2)(n²) + … mod n^s+1

C(mΦ, 1) is equal to mΦ

(1+n)^mΦ = 1 + mΦn + C(mΦ, 2)(n²) + … + C(mΦ, s+1)(n^s+1) + … mod n^s+1

Terms from coefficient n^s+1 will be divisible by the modulo. These can be simplified.

---

---

(1+n)^mΦ = 1 + mΦn + C(mΦ, 2)n² + … + C(mΦ, s)n^s mod n^s+1

In decryption, we are performing this calculation:

L((1+n)^mΦ mod n^s+1)

where logarithm function was

L(x) = (x-1)/n

Replace with the expansion of mΦ(n)-th power

L((1+n)^mΦ mod n^s+1) = L(1 + mΦn + C(mΦ, 2)n² + … + C(mΦ, s)n^s mod n^s+1)

Logarithm function requires decreasing the one and dividing to n

L((1+n)^mΦ mod n^s+1) = (1 + mΦn + C(mΦ, 2)n² + … + C(mΦ, s)n^s – 1)/n mod n^s+1

Plus and minus 1 can be simplified

---

---

L((1+n)^mΦ mod n^s+1) = (mΦn + C(mΦ, 2)n² + … + C(mΦ, s)n^s)/n mod n^s+1

Each item in the dividend has n coefficient. We can get rid of the divisor n.

L((1+n)^mΦ mod n^s+1) = mΦ + C(mΦ, 2)n + … + C(mΦ, s)n^s-1 mod n^s+1

Find the values in modulo n for both sides

L((1+n)^mΦ mod n^s+1) mod n = (mΦ + C(mΦ, 2)n + … + C(mΦ, s)n^s-1 mod n^s+1 ) mod n

We can get rid of the mod n^s+1 because mod n covers it.

L((1+n)^mΦ mod n^s+1) mod n = (mΦ + C(mΦ, 2)n + … + C(mΦ, s)n^s-1 ) mod n

All combination terms have n coefficient. That is why, we can get rid of them all in mod n.

L((1+n)^mΦ mod n^s+1) mod n = mΦ mod n

Now, multiply both sides to multiplicative inverse of totient

---

---

L((1+n)^mΦ mod n^s+1).Φ^-1 mod n = mΦ.Φ^-1 mod n

Multiplication of totient and multiplicative inverse of totient will be 1.

L((1+n)^mΦ mod n^s+1).Φ^-1 mod n = m mod n

In previous steps, we have proven this:

c^ϕ(n) = (1+n)^mϕ(n) mod n^s+1

We can replace the input of logarithm function as ciphertext to the power of totient

L((1+n)^mΦ mod n^s+1).Φ^-1 mod n = m mod n

L(c^Φ).Φ^-1 mod n = m mod n

This is exactly what we did in the decryption. We calculated the logarithm of ciphertext to the power of totient function times multiplicative inverse of totient. We have proven that is identical to message itself.

Conclusion

In conclusion, the world of cryptography and data security is ever-evolving, and the concept of partially homomorphic encryption with Damgard-Jurik is a testament to the ingenuity of researchers and developers in this field. I hope this step-by-step guide has shed light on the inner workings of this powerful encryption technique, enabling you to appreciate its potential applications in protecting sensitive data while allowing for meaningful computations. By delving into the Damgard-Jurik algorithm, you’ve gained valuable insights into its mathematical foundations and practical implementation in Python. As you venture forward in the realm of data security, remember that with great power comes great responsibility, and the ability to perform operations on encrypted data opens up a world of possibilities while emphasizing the need for careful consideration and ethical handling of sensitive information. With this newfound knowledge, you are better equipped to explore and utilize homomorphic encryption in your projects, contributing to the ever-advancing frontiers of secure data processing.

---

---

I pushed the source code of this study into GitHub. You can support this work if you star⭐ its repo.

---

Like this blog? Support me on Patreon

---