Partial Homomorphic Encryption implementations one or more of the arthimatic operations. With ElGamal we can implement homomorphic addition. Initially we have a private key of \(x\) and a public key of \(Y=xG\). A cipher is made up of \(C_1 = r.G\) and \(C_2 = rY+M\). If we add 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 \) and \(M=C_2\). From this we can recover the addition of the two message value points. For subtraction, we just add with a negative value.
Homomorphic Encryption With Adding for Elgamal using Kryptology |
Method
With ElGamal we can implement homomorphic addition. Initially we have a private key of \(x\) and a public key of:
\(Y=xG\)
A cipher is made up of:
\(C_1 = r.G\)
and
\(C_2 = rY+M\)
The value of M is then:
\(M=vG\)
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\)
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 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 \(m\) to find the result. This can be done by brute force if the result is relative small, but we can also solve for:
\(res=log_G(R)\)
For this we can use the Baby-step, giant-step method or the Pollard's ρ method.
Coding
The following is an implementation, and where we will use brute force to find the result in a range of -500 to 500:
package main import ( "fmt" "os" "strconv" "github.com/coinbase/kryptology/pkg/core/curves" "github.com/coinbase/kryptology/pkg/verenc/elgamal" ) func main() { val1 := 5 val2 := 4 argCount := len(os.Args[1:]) if argCount > 0 { val1, _ = strconv.Atoi(os.Args[1]) } if argCount > 1 { val2, _ = strconv.Atoi(os.Args[2]) } curve := curves.ED25519() pk, sk, _ := elgamal.NewKeys(curve) x1 := curve.Scalar.New(val1) x2 := curve.Scalar.New(val2) res1, _ := pk.HomomorphicEncrypt(x1) res2, _ := pk.HomomorphicEncrypt(x2) res1 = res1.Add(res2) dec, _ := res1.Decrypt(sk) pk_bytes, _ := pk.MarshalBinary() fmt.Printf("Public Key: %x\n", pk_bytes) sk_bytes, _ := sk.MarshalBinary() fmt.Printf("Private Key: %x\n", sk_bytes) fmt.Printf("Val1: %d\n", val1) val1_bytes, _ := res1.MarshalBinary() fmt.Printf(" Homomorphic encrypted: %x\n", val1_bytes) fmt.Printf("Val2: %d\n", val2) val2_bytes, _ := res2.MarshalBinary() fmt.Printf(" Homomorphic encrypted: %x\n", val2_bytes) fmt.Printf("Result (Homomorphic encrypted): %x\n", dec.ToAffineCompressed()) for i := -1000; i < 1000; i++ { val := curve.Scalar.New(i) Val := curve.Point.Generator().Mul(val) rtn := Val.Equal(dec) if rtn == true { fmt.Printf("Result is %d \n", i) break } } }
A sample run:
Public Key: 206455cb5bcfee7ddcac03700cd6c3c379049d3dfefc630c4c3d6a26fa1021dce70765643235353139 Private Key: 20f9dca488a997ba3f2246a3c3e74314e94e6b10c205a3481f87620e9429ea140c0765643235353139 Val1: 2 Homomorphic encrypted: 20d3a1136ca8a9b1265b84620075f2822a6dbf41ca96f5179bb046cecf6938884e20aee601b1b54aab6ee51b9b0d283b1ca00ae9ea5e710db3d2b4f8ddb20cdc88990765643235353139 Val2: 3 Homomorphic encrypted: 2091ab80e65d829ec799355632c53e98ba1357cc5955d2b9841f46806bcac3f80320f1617a72d85a6d12789a0eb74b14269cfa86b307b94536a5c839b482f10427fb0765643235353139 Result (Homomorphic encrypted): edc876d6831fd2105d0b4389ca2e283166469289146e2ce06faefe98b22548df Result is 5