Making ElGamal Additively Homomorphic with Elliptic Curves
The ElGamal encryption method was defined in 1985 by Tahir ElGamal:
As a discrete logarithm method, we have a private key of x and a public key of Y:
We can implement an additive and scalar multiply homomorphic encryption method by changing the ElGamal method to an elliptic curve implementation. In a standard ElGamal method, we have a secret key of x, and generate our public key with:
Y=x.G
and where G is a base point on the elliptic curve. To encrypt we generate a value scalar value (k) and a message (M). We compute:
A=k.G
B=k.Y+M
To decrypt with the private key (x), we perform:
M=B−x.A
The implementation of this is:
https://asecuritysite.com/elgamal/go_elgamal_ecc
To make homomorphically additive for two messages (M1 and M2) and two random nonce values (k1 and k2), we add the cipher values:
Ar=k1.G+k2.G
Br=k1.Y+k2.Y+M1+M2
The message is recovered with:
M=Br−x.Ar
This works as:
M=Br−x.Ar=k1.Y+k2.Y+M1+M2−x.(k1.G+k2.G)=M1+M2
Here are other methods for PHE:
