Homomorphic Addition and Subtraction using ElGamal

Prof Bill Buchanan OBE FRSE
2 min readDec 13, 2021

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

--

--

Prof Bill Buchanan OBE FRSE
Prof Bill Buchanan OBE FRSE

Written by Prof Bill Buchanan OBE FRSE

Professor of Cryptography. Serial innovator. Believer in fairness, justice & freedom. Based in Edinburgh. Old World Breaker. New World Creator. Building trust.

No responses yet