Homomorphic Encryption With ElGamal: Multiply/Divide
Homomorphic Encryption With ElGamal: Multiply/Divide
There are some encryption methods which allow us to process encrypted values. In this way we can process using certain mathematical operations on cipher values, and end up with the result when we decrypt. For example, if we encrypt a value of 4 and a value of 3 with a public key we get:
Epub(4), Epub(3)
If we now multiply these values we get:
Res=Epub(4)xEpub(3)
If we now decrypt the result (Res) with the private key, and the answer is 12, we have performed a multiplication on the encrypted values. RSA is one method that we can perform a multiplication and division — and is defined as a partial homomorphic encryption (PHE) method. Another method we can use to multiply and divide is ElGamal. If you are interested, here is the method [here]:
Basically, we compute the cipher values (a,b) for both integer values, and then multiply the a values and multiply the b values. The decryption process is then just the same as with a single value. The Python code for this is [here]:
from Crypto.Util.number import *
from Crypto import Random
import Crypto
import random
import libnum
import sys
import hashlib
def get_generator(p: int):
while True:
# Find generator which doesn't share factor with p
generator = random.randrange(3, p)
if pow(generator, 2, p) == 1:
continue
if pow(generator, p, p) == 1:
continue
return generator
bits=512
v1=10
v2=5
if (len(sys.argv)>1):
v1=int(sys.argv[1])
if (len(sys.argv)>2):
v2=int(sys.argv[2])
if (len(sys.argv)>3):
bits=int(sys.argv[3])
p = Crypto.Util.number.getPrime(bits, randfunc=Crypto.Random.get_random_bytes)
g = get_generator(p)
x = random.randrange(3, p)
Y = pow(g,x,p)
print (f"v1={v1}\nv2={v2}\n")
print (f"Public key:\ng={g}\nY={Y}\np={p}\n\nPrivate key\nx={x}")
k1=random.randrange(3, p)
a1=pow(g,k1,p)
b1=(pow(Y,k1,p)*v1) % p
k2=random.randrange(3, p)
a2=pow(g,k2,p)
b2=(pow(Y,k2,p)*v2) % p
a=(a1*a2) %p
b=(b1*b2) %p
print (f"\nEncrypted (v1)\na={a1}\nb={b1}")
print (f"\nEncrypted (v2)\na={a2}\nb={b2}")
print (f"\nAfter homomorphic encryption\na={a}\nb={b}")
v_r=(b*libnum.invmod(pow(a,x,p),p)) % p
print ("\nResult: ",v_r )
A sample run for 60-bit primes [here]:
v1=10
v2=34
Prime bits=60
Public key:
g=734346575755555349
Y=367696589006816172
p=787202037707659571
Private key
x=466969224259741451
Encrypted (v1)
a=171786812841192100
b=205804868040016564
Encrypted (v2)
a=386907419641951
b=555231043574564515
After homomorphic encryption
a=517494939977277643
b=122169903164151101
Result: 340
and for 512-bit primes [here]:
v1=10
v2=34
Prime bits=512
Public key:
g=8143276510945862903726899010946453352368246037588233668858647939048592064448296379316202897800777572011261165184623718638604176725317075197852662427009971
Y=4036066775608911770318535628872852093954186164714891230739728500000442235422764661965454186485169246795597160536201319116895828209213748417456634811496755
p=8276436424627097844279806651535284202794565931984967257652906091651975134147784049024443110703788096521343755165238592060445205116555193791668423955788697
Private key
x=3641828277990357129253695677788899199819696409841725267468082793950274408089723651791350897062221540559581908855742232672134142378636151756855993640643953
Encrypted (v1)
a=5473512104637383138114214167877113510078121588900413262698073730306083495610466265490125911938322073438921888510888794132358999239891267304838984034891739
b=3901101614138791175915445047296716202421468443144080986953751151719877932795907037622303723387585414650690688773853403818596992448661795913713275607938738
Encrypted (v2)
a=6654007609621371566586914715832413587775028592857082401880519204469314724862089741988042575178604059538938068699201974017514269882186122528789679186250736
b=2790367683990053260728224798008463510631092789025408027595512770673017449283772442784289419623194986157305960906953653537533140438011143795670371101036543
After homomorphic encryption
a=2034564617453654600203090756818743491290801466060687470205982549419515944685909896063217489472357096360570125165150803657598520017933395641000565048118608
b=7295692488792908890576489938431846190650202029157972650749178323522777654779347960767847709291706628677409522591878620522572453548059415120601121785702462
Result: 340
Dividing cipher values
For division, we take the inverse of the values:
This is implemented as an inverse mod p operation:
a=a1*libnum.invmod(a2,p)
b=b1*libnum.invmod(b2,p)
The coding is [from here]:
from Crypto.Util.number import *
from Crypto import Random
import Crypto
import random
import libnum
import sys
import hashlib
def get_generator(p: int):
while True:
# Find generator which doesn't share factor with p
generator = random.randrange(3, p)
if pow(generator, 2, p) == 1:
continue
if pow(generator, p, p) == 1:
continue
return generator
bits=512
v1=10
v2=5
if (len(sys.argv)>1):
v1=int(sys.argv[1])
if (len(sys.argv)>2):
v2=int(sys.argv[2])
if (len(sys.argv)>3):
bits=int(sys.argv[3])
p = Crypto.Util.number.getPrime(bits, randfunc=Crypto.Random.get_random_bytes)
g = get_generator(p)
x = random.randrange(3, p)
Y = pow(g,x,p)
print (f"v1={v1}\nv2={v2}\nPrime bits={bits}\n")
print (f"Public key:\ng={g}\nY={Y}\np={p}\n\nPrivate key\nx={x}")
k1=random.randrange(3, p)
a1=pow(g,k1,p)
b1=(pow(Y,k1,p)*v1) % p
k2=random.randrange(3, p)
a2=pow(g,k2,p)
b2=(pow(Y,k2,p)*v2) % p
a=(a1*libnum.invmod(a2,p)) %p
b=(b1*libnum.invmod(b2,p)) %p
print (f"\nEncrypted (v1)\na={a1}\nb={b1}")
print (f"\nEncrypted (v2)\na={a2}\nb={b2}")
print (f"\nAfter homomorphic encryption\na={a}\nb={b}")
v_r=(b*libnum.invmod(pow(a,x,p),p)) % p
print ("\nResult: ",v_r )
A sample run is [here]:
v1=100
v2=20
Prime bits=60
Public key:
g=1087707651693241366
Y=704660499192052783
p=1146577655890546777
Private key
x=592385358090421952
Encrypted (v1)
a=282866651352294704
b=556096439266923943
Encrypted (v2)
a=538074508197394015
b=16459668815452760
After homomorphic encryption
a=1139345043832659778
b=379372869650003628
Result: 5
Conclusions
Our data world must change, and we must move into a world where all our data is encrypted, and where we can make decisions on it, without revealing the actual value.