In an age where data privacy and security are paramount, encryption plays a pivotal role in safeguarding sensitive information. One fascinating area of encryption is homomorphic encryption, which allows computations to be performed on encrypted data without the need for decryption. Today, we embark on a journey to explore this intricate world by delving into a step-by-step tutorial on Partially Homomorphic Encryption, focusing on the Benaloh cryptosystem. Fear not if these terms sound complex; we’ll break it down into manageable pieces and build our understanding from the ground up, all while implementing it in Python, starting from scratch. By the end of this blog post, you’ll not only have a grasp of the fundamentals but also a working example to demonstrate the power of Additively Homomorphic Encryption with Benaloh. So, let’s dive in and unravel the secrets of this intriguing cryptographic technique!
🐍 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 = 'Benaloh') # 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
Similar to RSA and Paillier, we are going to generate two primes p and q. We can test the primeness of this pair with sympy module.
import sympy p = 10007 q = 191 assert sympy.isprime(p) assert sympy.isprime(q)
Then, we will calculate the n and Φ values. Φ refers to the Euler’s Totient Function which counts the positive integers that coprime to n.
n = p*q phi = (p-1)*(q-1)
Block size
Benaloh cryptosystem requires to generate a block size r in the key generation step. This should be:
- Random integer in scale of [0, n]
- Must divide p-1 without remainder
- Must be coprime with (p-1)/r
- Must be coprime with (q-1)
According to these rules, block size generation function can be generalized as:
def generate_block_size():
while True:
r = random.randint(2, n)
if (
# r should divide p-1 without remainder
(p-1) % r == 0
# r and (p - 1) / r must be coprimes
and gcd(r, int((p - 1) / r)) == 1
# r and q-1 must be coprimes
and gcd(r, q - 1)
) == 1:
break
return r
Public and private keys
We are going to generate a public key y:
- Must be coprime with n
- If its prime factors are p = {p0, p1, … pi}, then the following rule must be satisfied for all these factors
yΦ/pi mod n != 1
Then, we will calculate the private key x as:
x = yΦ/r mod n
This must not be equal to 1.
x != 1
According to these rules, y and x keys can be implemented as:
def generate_keys():
while True:
r = generate_block_size()
y = random.randint(2, n)
if gcd(y, n) != 1:
continue
# to guarantee correct decryption
prime_factors = sympy.factorint(r).keys()
decryption_guaranteed = True
for prime_factor in prime_factors:
# none of r's prime factor should satisfy the condition
if pow(y, int(phi/prime_factor), n) == 1:
decryption_guaranteed = False
if decryption_guaranteed is False:
# regenerate keys
continue
x = pow(y, int(phi/r), n)
if x != 1:
break
return r, x, y
# ------------------------
r, x, y = generate_keys()
Finally, y, r and n will be public keys whereas p, q, phi and x will be private keys.
Plaintext
We will be able to encrypt messages member of Zr. In other words, plaintext must be less than block size r. If it is greater, then we should find its value in modulo r.
m = 17
if m >= r:
print(f"Warning! plaintext {m} should be member of Z_{r} but it is greater.")
m = m % r
print(f"So, it is restored to {m}")
Encryption
Encryption requires to generate a random key u that must be coprime with n.
while True:
u = random.randint(1, n)
if gcd(u, n) == 1:
break
Then, encryption will be done with the following formula
( ym mod n x ur mod n ) mod n
This can be implemented as
def encrypt(m, u):
return (pow(y, m, n) * pow(u, r, n)) % n
c = encrypt(m, u)
assert gcd(c, n) == 1
Ciphertext must be coprime with n.
Decryption
Decryption requires to solve the following.
m = log x (cΦ/r mod n)
This can be represented as
xm = cΦ/r mod n
To solve this discrete logarithm problem, we need to perform a brute force attack even though we are not the attacker!
def decrypt(c):
a = pow(c, int(phi/r), n)
md = 0
while True:
if pow(x, md, n) == a:
break
md = md + 1
return md
# ---------------------
m_prime = decrypt(c)
Proof
Let’s investigate the variable a in the decryption process
a = cΦ/r mod n
Ciphertext was calculates as ymur
a = (ymur)Φ/r mod n
We are able to move the power Φ/r into the terms in the parenthesis:
a = (ym)Φ/r(ur)Φ/r mod n
Power of the base u has r in both dividend and divisor. So, this can be simplified.
a = (ym)Φ/r(u)Φ mod n
Moving Φ/r to the inside of parenthesis and moving m to the outside of parenthesis will not change the result
a = (yΦ/r)m(u)Φ mod n
Private key x was calculated as yΦ/r
a = (x)m(u)Φ mod n
Finally, according to the Fermat Euler Theorem, uΦ mod n = 1 if and only if u and n are coprimes. We guarantee that u and n are coprimes in the key generation step.
a = xm mod n
When decrypter side (let’s say Alice) calculates a = cΦ/r mod n, then she will have the exact value of xm mod n. She also knows the private key x because she generated this. She tries to extract m from known x and xm with brute force method.
TBH, this is annoying because we have to solve a discrete logarithm problem to decrypt messages in this cryptosystem.
Homomorphic Features
Benaloh cryptosystem is partially homomorphic with respect to the addition.
m1 = 10 % r u1 = random.randint(0, n) c1 = encrypt(m1, u1) m2 = 17 % r u2 = random.randint(0, n) c2 = encrypt(m2, u2) assert (c1 * c2) % n == encrypt(m1+m2, u1*u2) assert decrypt((c1 * c2) % n) == (m1+m2) % r
Proof of Homomorphic Features
Remember the encryption formula:
c = ymur mod n
So, if we encrypt messages m1 and m2, with random keys u1 and u2:
c1 = ym1ur1 mod n
c2 = ym2ur2 mod n
Let’s find the multiplication of those too ciphertexts:
c1c2 = ym1ur1ym2ur2 mod n
According to the multiplication of exponent with same bases, we can represent this as:
c1c2 = ym1ym2ur1ur2 mod n
c1c2 = ym1+m2ur1+r2 mod n
On the other hand, if we encrypt m1+m2 with random key u1+u2, then we will have exactly the same value!
Conclusion
In closing, we’ve embarked on a journey into the world of Partially Homomorphic Encryption with the Benaloh cryptosystem, starting from scratch and working our way through the intricacies of this powerful encryption technique. Along the way, we’ve learned how to encrypt and manipulate data securely, preserving its privacy while still deriving meaningful results. As technology continues to evolve, the importance of encryption in protecting our sensitive information becomes ever more evident. The knowledge and skills you’ve gained in this tutorial can serve as a solid foundation for further exploration into the fascinating field of cryptography. By embracing the power of encryption, you contribute to a safer digital world where privacy and security remain paramount. So, as you reflect on your journey through this tutorial, remember that you now possess the tools to apply Partially Homomorphic Encryption with Benaloh, creating a more secure and privacy-conscious digital landscape. Continue to explore, innovate, and make the digital realm a safer place for all.
I pushed the source code of this study into GitHub. You can support this work if you star⭐ the repo.
Like this blog? Support me on Patreon
