Homomorphic Addition and Subtraction using ElGamal

The next few years are likely to see an increase in the usage of homomorphic encryption, and where we can perform arithmetic operations on…

Homomorphic Addition and Subtraction using ElGamal

The next few years are likely to see an increase in the usage of homomorphic encryption, and where we can perform arithmetic operations on encrypted data. For example, we can perform searches on data, without actually revealing the contents of the data elements. Some methods proposed are partially homomorphic, and which can implement one or more arithmetic methods, but not all of them. In this case, we will look at the ElGamal method, and implement a simple program to add and subtract values in a homomorphic way.

ElGamal method

With the ElGamal encryption method, we can implement homomorphic addition and subtraction. Initially, we have a private key of x and a public key of:

Y=x.G

and where G is the base point on the curve. A cipher is made up of:

C1=r.G

and

C2=r.Y+M

The value of M is then:

M=v.G

and where v is the integer value that we want to operate on. To decrypt we basically take the private key (x) and compute:

S = x. C_1

and then recover the message with:

M = C_2-S

Adding

If we add two ciphertext values (created from two random numbers of r_1 and r_2), we get:

C_1=r_1 G+r_2 G=(r_1+r_2)G

and:

C_2=r_1 Y+r_2 Y+M_1+M_2=(r_1+r_2)Y+(M_1+M_2)

When we decrypt, we create:

S=x C_1=x(r_1+r_2)G=(r_1+r_2)xG=(r_1+r_2)Y

and:

M=C_2−S=(r_1+r_2)Y+M_1+M_2=M_1+M_2−((r_1+r_2)Y)=M_1+M_2

We then get a point on the elliptic curve that relates to our result (res.G), and need to find res. We must search for the point to recover the result. The problem we have is:

R=res.G

and we need to recover res to find the result. This can be done by brute force if the result is relatively small, but we can also solve for:

res=log_G(R)

For this, we can use the Baby-step, giant-step method or Pollard’s ρ method.

The following is an implementation, and where we will use brute force to find the result in a range of -500 to 500 [here]:

A sample run [here]:

Public Key: 206455cb5bcfee7ddcac03700cd6c3c379049d3dfefc630c4c3d6a26fa1021dce70765643235353139
Private Key: 20f9dca488a997ba3f2246a3c3e74314e94e6b10c205a3481f87620e9429ea140c0765643235353139
Val1: 2
 Homomorphic encrypted: 20d3a1136ca8a9b1265b84620075f2822a6dbf41ca96f5179bb046cecf6938884e20aee601b1b54aab6ee51b9b0d283b1ca00ae9ea5e710db3d2b4f8ddb20cdc88990765643235353139
Val2: 3
 Homomorphic encrypted: 2091ab80e65d829ec799355632c53e98ba1357cc5955d2b9841f46806bcac3f80320f1617a72d85a6d12789a0eb74b14269cfa86b307b94536a5c839b482f10427fb0765643235353139
Result (Homomorphic encrypted): edc876d6831fd2105d0b4389ca2e283166469289146e2ce06faefe98b22548df
Result is 5