In the realm of cryptography, data security and privacy have become paramount concerns. As we increasingly rely on digital communication and storage, safeguarding sensitive information has never been more critical. One of the tools that plays a pivotal role in this domain is homomorphic encryption, a cryptographic technique that enables computations on encrypted data without the need to decrypt it first. While most partially homomorphic encryption algorithms focus on preserving the properties of addition or multiplication, we are about to delve into a fascinating and relatively unique encryption scheme known as Goldwasser-Micali. What sets Goldwasser-Micali apart is its exceptional homomorphic property – it operates exclusively on the Exclusive OR (XOR) operation. In this blog post, we will guide you through a step-by-step journey into the world of partially homomorphic encryption with Goldwasser-Micali, implemented using Python. By the end of this tutorial, you’ll not only gain a better understanding of this extraordinary encryption technique but also be equipped with the knowledge to implement it in your own projects. So, let’s embark on this cryptographic adventure to discover the power of XOR in the realm of 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 = 'Goldwasser-Micali') # define plaintexts m1 = 17 m2 = 23 # calculate ciphertexts c1 = cs.encrypt(m1) c2 = cs.encrypt(m2) # performing homomorphic xor on ciphertexts assert cs.decrypt(c1 ^ c2) == m1 ^ m2
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 most of cryptosystem, this requires to pick two large primes p and q
# pick two primes import sympy p = 101 q = 113 assert sympy.isprime(p) assert sympy.isprime(q)
Modulo will be the multiplication of those primes
n = p*q
Then, cryptosystem requires to pick a non-residue x such that its Legendre symbols must satisfy (x/p) = (x/q) = -1.
# find non-residue x
while True:
x = random.randint(1, n-1)
if (
math.gcd(x, n) == 1
and jacobi_symbol(x, p) == -1
and jacobi_symbol(x, q) == -1
):
break
print(f'non-residue x: {x}')
Hence, its Jacobi symbol will satisfy (x/n) = 1 because (x/n) = (x/p)(x/q) = (-1)(-1) = 1
assert jacobi_symbol(x, n) == 1
Encryption
Cryptosystem allows you to encrypt bits. We will basically perform calculation:
ci = r2xmi mod n
where r is a random integer, mi is the i-th bit of the plaintext m, and ci is the encrypted value of i-th bit of plaintext m.
Random integer must be co-prime to n.
def generate_random():
'''
Generate random that co-prime to n
Returns:
random number (int)
'''
while True:
r = random.randint(1, n)
if math.gcd(r, n) == 1:
break
return r
The following function will encrypt a bit value for a random integer r.
def encrypt_bit(b: int, r: int):
'''
Encrypt a bit
Args:
b (int): 0 or 1
r (int): random integer that co-prime to n
Returns:
encrypted bit (int)
'''
return ( pow(r, 2, n) * pow(x, b, n) ) % n
Finally, we will convert our integer m to binary and call the encrypt_bit function
def encrypt(m):
'''
Encrypt an integer message
Args:
m (int): plaintest
Returns:
ciphertext (int)
'''
m_binary = bin(m)[2:]
# number of bits
k = len(m_binary)
c = []
for i in range(0, k):
mi = int(m_binary[i])
ri = generate_random()
ci = encrypt_bit(mi, ri)
c.append(ci)
return c
This can be tested as
m = 17 c = encrypt(m)
For my case, plaintext (17)10 = (10001)2 was encrypted for x=6479 as
E(mi=1, ri=3388) = 4672 E(mi=0, ri=8860) = 986 E(mi=0, ri=9709) = 4714 E(mi=0, ri=8961) = 9066 E(mi=1, ri=2975) = 7500
So, ciphertext c = [4672, 986, 4714, 9066, 7500]
Decryption
We are going to process each ci value. If it is a quadratic residue, then mi = 0 otherwise mi = 1. Even though this sentence can be understood as complex, actually it is not.
Where ci is the encrypted value of i-th bit, we are going to find the each ciphertext’s equivalent for modulo p and q
xp = ci mod p
xq = ci mod q
Then, we will check the following conditions.
xp(p-1)/2 mod p == 1
xq(q-1)/2 mod q == 1
If they are satisfied, then plaintext is 0, otherwise it is 1.
def decrypt(c: list):
'''
Decrypt a ciphertext
Args:
c (list): ciphertext - encrypted bits of plaintext
Returns:
plaintext (int)
'''
m_binaries = []
for i in c:
xp = i % p
xq = i % q
if pow(xp, int((p-1)/2), p) == 1 and pow(xq, int((q-1)/2), q) == 1:
m_binaries.append('0')
else:
m_binaries.append('1')
m_binary = ''.join(m_binaries)
return int(m_binary, 2)
Homomorphic Features
Goldwasser-Micali comes with exceptional homomorphic features with respect to the exclusive OR gate or shortly XOR.
args = [
[0, 0],
[0, 1],
[1, 0],
[1, 1]
]
for b1, b2 in args:
r1 = generate_random()
r2 = generate_random()
c1 = encrypt_bit(b1, r1)
c2 = encrypt_bit(b2, r2)
assert ( c1 * c2 ) % n == encrypt_bit(b1+b2, r1*r2)
b1_xor_b2 = b1 ^ b2
assert decrypt([( c1 * c2 ) % n]) == b1_xor_b2
Proof of Homomorphic Features
E(b, r) = r2xb mod n
where b is the bit value, r is a random integer and x is non-residue number.
If we encrypt two different bits b1 and b2 with random keys r1 and r2
E(b1, r1) = r12xb1 mod n
E(b2, r2) = r22xb2 mod n
Now, multiply these two ciphertexts
E(b1, r1).E(b2, r2) = r12xb1r22xb2 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.
E(b1, r1).E(b2, r2) = r12r22xb1xb2 mod n
E(b1, r1).E(b2, r2) = r12r22 xb1+b2 mod n
Also, according to the power of power rule of exponent rules, you raise an exponent to another exponent, you can simply multiply the exponents together to find the new exponent.
E(b1, r1).E(b2, r2) = (r1r2)2 xb1+b2 mod n
On the other hand, if we encrypt b1+b2 with random key r1xr2, we will have same result
E(b1+b2, r1r2) = (r1r2)2 xb1+b2 mod n
So, thise proves the additively homomorphic features of the cryptosystem over bits.
E(b1, r1).E(b2, r2) = E(b1+b2, r1r2)
Encryption function expects bit values for input b. Addition on bits is performed for modulo 2. This makes cryptosystem homomorphic with respect to the XOR instead of addition. So, it is better to show the homomorphic features as:
E(b1, r1).E(b2, r2) = E(b1⊕b2, r1r2)
Conclusion
In the ever-evolving landscape of cybersecurity and data protection, the Goldwasser-Micali partially homomorphic encryption algorithm stands out as a remarkable and somewhat unique solution. With its exclusive focus on the XOR operation, this encryption scheme opens up new possibilities for secure computations on sensitive data without compromising privacy. As we conclude our journey through the intricacies of Goldwasser-Micali in Python, we’ve equipped ourselves with a valuable tool to tackle real-world data security challenges.
By grasping the inner workings of this encryption method, we empower ourselves to build more secure and privacy-preserving applications that can handle operations on encrypted data without the need for decryption. As technology continues to advance, our commitment to data protection and privacy must evolve as well, and Goldwasser-Micali’s XOR homomorphism offers an exciting and effective avenue to achieve these goals.
We hope this tutorial has illuminated the potential of Goldwasser-Micali and inspired you to explore the vast world of cryptography, contributing to a more secure and private digital future.
I pushed the source code of this study to GitHub. You can support this work if you star⭐ its repo.
Like this blog? Support me on Patreon
