In today’s rapidly evolving digital landscape, the need for secure data transmission and storage has never been more critical. To address this challenge, encryption techniques have become a cornerstone of modern cybersecurity. Partially Homomorphic Encryption is a fascinating branch of encryption that allows us to perform computations on encrypted data without the need to decrypt it first. In this blog post, we’ll explore the world of Partially Homomorphic Encryption with a practical and illustrative example in Python, featuring the Okamoto-Uchiyama cryptosystem. By the end of this step-by-step guide, you’ll have a clear understanding of how to harness the power of Additively Homomorphic Encryption to protect your sensitive data while still being able to perform meaningful computations securely. Let’s dive into the fascinating realm of cryptography and Python as we unveil the secrets of Okamoto-Uchiyama Partially Homomorphic 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 = 'Okamoto-Uchiyama') # 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 primes p and q
import sympy # generate two primes p = sympy.randprime(1000, 2000) q = sympy.randprime(1000, 2000)
Then, we will calculate the module n which is p squared q.
# modulo n = p*p*q
Thereafter, we are going to generate a base generator g.
# generator g = random.randint(1, n)
As a rule, g to the power of p-1 in modulo p2 must not be identical to 1.
assert pow(g, p-1, p*p) != 1
This rule is always satisfied because of Fermat’s Little Theorem.
ap-1 = 1 mod p
ap-1 ≠ 1 mod p2
Finally, we will calculate the number h which is equal to gn mod n.
h = pow(g, n, n)
So, (n, g, h) will be public keys whereas (p, q) will be private keys.
print(f'public key is {n=}, {g=}, {h=}')
print(f'private key is {p=}, {q=}')
Encryption
We can encrypt a message m in scale [1, p].
# message in modulo p m = 17 m = m % p
Encryption requires to create a random key in {1, 2, …, n-1}
# random integer r = random.randint(1, n-1)
Then, ciphertext will be the generator g to the power of message times generator g to the power of n (which is h) to the power of random integer r in modulo n.
def encrypt(m, r):
return ( pow(g, m, n) * pow(h, r, n) ) % n
c = encrypt(m, r)
Logarithm Function Over Cyclic Group
In decryption, we will need a logarithm function over cyclic group.
L(x) = (x-1) / p
Here, input of this logarithm function must satisfy two rules:
X must be identical to 1 for modulo p
x = 1 mod p
And x and p squared must be coprimes
gcd(x, p2) = 1
def lx(x):
assert x % p == 1
assert math.gcd(x, p*p) == 1
lx = (x - 1)/p
return int(lx)
Hint: we will use Fermat’s Little Theorem to feed inputs to logarithm function to guarantee those rules satisfied always.
Decryption
Decryption requires to calculate two numbers a and b:
a = L( cp-1 mod p2)
b = L( gp-1 mod p2 )
Remember the Fermat’s Little Theorem, please. Basically it says that for any prime number and any integer not divisible by that prime number, when raised to the power of one less than the prime number, equals 1 modulo the prime number.
ap-1 = 1 mod p.
So, we are always feeding numbers identical to 1 in modulo p to logarithm function as inputs. So, two prerequisite rules of logarithm function are always satisfied in this way.
Once, we calculate a and b, then we plaintext will be
m’ = a . (b-1) mod p
def decrypt(c):
a = lx( pow(c, p-1, p*p) )
b = lx( pow(g, p-1, p*p) )
return ( a * pow(b, -1, p) ) % p
m_prime = decrypt(c)
assert m_prime == m
Homomorphic Features
Okamoto–Uchiyama comes with partially homomorphic features. Multiplying the encryption of two messages is equivalent to encryption of their sum.
m1 = 17
r1 = random.randint(1, n-1)
print(f'{m1}, {r1}')
m2 = 23
r2 = random.randint(1, n-1)
print(f'{m2}, {r2}')
c1 = encrypt(m1, r1)
c2 = encrypt(m2, r2)
assert ( c1 * c2 ) % n == encrypt(m1+m2, r1+r2)
assert decrypt(( c1 * c2 ) % n) == m1 + m2
Proof of Its Homomorphic Features
Encryption requires to perform following calculation:
E(m, r) = c = gm hr mod n
So, if we encrypt messages m1 and m2 with random keys r1, r2
E(m1, r1) = c1 = gm1 hr1 mod n
E(m2, r2) = c2 = gm2 hr2 mod n
Now multiply two ciphertexts
c1c2 = gm1 hr1 gm2 hr2 mod n
According to the product rule of exponent rules, when multiplying two exponential terms with the same base, you can combine their exponents by addition.
c1c2 = gm1+m2 hr1+r2 mod n
On the other hand, if we encrypt m1+m2 with random key r1+r2, we will have same result
E(m1+m2, r1+r2) = gm1+m2 hr1+r2 mod n
So, we proven the additively homomorphic features of Okamoto–Uchiyama.
E(m1, r1) * E(m2, r2) = E(m1+m2, r1+r2)
The Math Behind The Cryptosystem
Firstly, we will pick a number x and prime number p. Here, x must be coprime with p2, and it is identical to 1 in modulo p
gcd(x, p2) = 1
x = 1 mod p
We will then define a logarithm function L from the cyclic group.
L(x) = (x-1) / p
Notice that input of this logarithm function x must satisfy the rules gcd(x, p2) = 1 and x = 1 mod p.
Lemma 1: Product Rule of the Logarithm Function Over Cyclic Group
L(ab) mod p = L(a) + L(b)
Proof
L(ab) = (ab – 1) / p
ab – 1 can be written as (a-1)(b-1) + (a-1) + (b-1)
L(ab) = [ (a-1)(b-1) + (a-1) + (b-1) ] / p
L(ab) = [ (a-1)/p ] (b-1) + (a-1)/p + (b-1)/p
(a-1)/p is equal to L(a) and (b-1)/p is equal to L(b)
L(ab) = L(a)(b-1) + L(a) + L(b)
Find the values for modulo p for both sides
L(ab) mod p = L(a)(b-1) + L(a) + L(b) mod p
Please remember the x and L(x) relation. x = 1 mod p. The values a and b are inputs of this logarithm function.
a = 1 mod p
b = 1 mod p
In the expression, we have the term (b-1). This can be represented as:
b – 1 = 0 mod p
L(ab) mod p = L(a) . 0 + L(a) + L(b) mod p
L(ab) = L(a) + L(b) mod p
So, we proven the product rule of the logarithm function on the cyclic group.
Lemma 2: Power Rule of Logarithm Function Over Cyclic Group
L(xm) = m.L(x)
Proof
We proven L(ab) = L(a) + L(b) mod p in Lemma 1. x to the power of m requires to x to itself m times.
xm = x.x.x….x
There are m times x available in the right hand side.
If we find the logarithm function of both sides
L(xm) = L(x.x.x….x)
There are still m times x available in the right hand side.
If we apply the product rule
L(xm) = L(x.x.x….x) = L(x) + L(x) + L(x) + … + L(x) = m.L(x)
So, we proven the power rule of logarithm over cyclic group
Proof of Decryption
In decryption, we are performing following 3 calculations:
a = L (cp-1 mod p2)
b = L (gp-1 mod p2)
m = a. (b-1) mod p
And we were performing following calculation for encryption
c = gm hr mod p
h was caculated as generator g to the power of n
c = gm gnr mod p
Also, n was p2q
c = gm gppqr mod p
Let’s find the (p-1)-th power of ciphertext, because this was done in decryption
cp-1 = (gm gppqr)p-1 mod p
The power of a product rule in exponent rules allows you to distribute an exponent to each term within a product enclosed in parentheses
cp-1 = (gm)p-1 (gppqr)p-1 mod p
Rearranging the order of exponents will not change the result
cp-1 = (gp-1)m (gp.(p-1)pqr) mod p
We were calculating logarithm of ciphertext to. thepower of p-1 for module p squared
a = L(cp-1 mod p2)
Let’s check the second term’s value for p squared
gp.(p-1)pqr mod p2 = ?
Prime power rule of totient states that:
ϕ(pn) = ϕ(p).(pn-1)
So, we can generalize totient of p squared as
ϕ(p2) = ϕ(p).(p2-1)
ϕ(p2) = ϕ(p).p = (p-1).p
gp.(p-1)pqr mod p2 = gϕ(p^2)pqr mod p2 = (gϕ(p^2))pqr mod p2
We see Fermat Euler Theorem this time: gϕ(p^2) = 1 mod p2
gp.(p-1)pqr mod p2 = (1)pqr mod p2 = 1
Let’s turn back to c to the power of p-1
cp-1 = (gp-1)m (gp.(p-1)pqr) mod p
Second term can be simplified
cp-1 = (gp-1)m mod p
Decryption was requiring
m’ = L(cp-1 mod p2) / L(gp-1 mod p2)
Express c to the power of p-1 as the recently found value
m’ = L((gp-1)m mod p2) / L(gp-1 mod p2)
The logarithm power rule states that the logarithm of a number raised to an exponent is equal to the exponent multiplied by the logarithm of the base. We proven this already in Lemma 2.
L(xm) = m.L(x)
If we apply this rule in decryption statement
m’ = L((gp-1)m mod p2) / L(gp-1 mod p2) = m.L(gp-1 mod p2)/L(gp-1 mod p2) = m
So, decryption calculation will give us restored plaintext always. We proven this!
m’ = m
Conclusion
In the realm of modern cybersecurity, the importance of data protection cannot be overstated, and Partially Homomorphic Encryption offers a powerful solution to the age-old dilemma of securing data while retaining its utility. Through this step-by-step exploration of the Okamoto-Uchiyama cryptosystem in Python, we’ve delved into the world of Partially Homomorphic Encryption, demystifying its complexities and making it accessible to those who seek to safeguard their sensitive information. As we conclude our journey, it’s evident that the fusion of cryptography and Python empowers us to fortify our data’s defenses without sacrificing functionality. With this newfound knowledge, you’re better equipped to tackle the challenges of a data-driven world while maintaining the highest standards of security. We hope this guide has provided you with the tools and insights you need to take your data protection to the next level and continue your exploration of the fascinating field of cryptography.
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
