Implementing Homomorphic Addition With ElGamal and PowerShell
Implementing Homomorphic Addition With ElGamal and PowerShell
Homomorphic encryption provides us with a way to encrypt values and then to be able to process them. Let’s say we have Bob the Data Processor and Alice the Consumer. With this, Alice could encrypt the values that she has with her public key, and then Bob can process these values with mathematical operations and then give the result back to Alice, who will then decrypt the result.
For given methods, such as for RSA and ElGamal, we can have partial homomorphic encryption (PHE), and where we implement a few of the arithmetic operations. For example, ElGamal naturally supports multiplication and division:
https://asecuritysite.com/powershell/elgamal_ps2
But what about addition and subtraction? Well, with a tweak, we can modify ElGamal to support addition and subtraction.
Homomorphic addition using the ElGamal method
With ElGamal encryption, initially, Bob creates his public key by selecting a g value and a prime number (p) and then selecting a private key (x). He then computes Y which is:
His public key is (Y,g,p) and he will send this to Alice. Alice then creates a message (M) and selects a random value k. She then computes a and b:
Bob then receives these and decrypts with:
This works because:
Now with additive homomorphic encryption, we change the encryption to be:
Notice that instead of:
we now have:
The result of the decryption then gives:
Then just need to brute force the resulting value to find a value which matches g^i. The working out is:
and then:
The modification (for values of v1 and v2) is simply [here]:
function encrypt($g, $p, $n, $message) {
$k=getRandom $p $n
$a = [BigInt]::ModPow($g, $k, $p)
$s = [BigInt]::ModPow($Y, $k, $p)
$b = ([BigInt]::Multiply([BigInt]::ModPow($g,$message,$p), $s)) % $p
return $a,$b
}We then search the result for possible values of M1+M2. An example of a search for the solution to v_r is [here]:
for($i = 0; $i -lt 2000; $i++){
$val = [BigInt]::ModPow($g, $i, $p)
if ($val -eq $dec) {
"Found it at ",$i
}
}One of the great advantages of using Python is that it automatically deals with Big Integers. We thus do not need any special data type and can just operate on them as if they were normal integer types. The coding is [here]:
function inverse_mod([BigInt] $a,[BigInt] $p){
# res = a^{-1} (mod p)
$val = [BigInt]0
$nt = [BigInt]1
$r = $p
$nr = $a
while ($nr -ne [BigInt]0) {
$q = [BigInt]::Divide($r,$nr)
$val_temp = $nt
$nt = [BigInt]::Subtract($val,[BigInt]::Multiply($q,$nt))
$val = $val_temp
$val_temp = $nr
$nr = [BigInt]::Subtract($r, [BigInt]::Multiply($q,$nr))
$r = $val_temp
}
if ($r -gt 1) {return -1}
if ($val -lt 0) {$val = [BigInt]::Add($val,$p)}
return $val
}
function getg([BigInt] $p){
$One = [BigInt] 1
$Two = [BigInt] 2
$etotient = [BigInt]::Subtract($p, $One)
$g = 3
$e = [BigInt]::Divide($etotient,$Two)
while([BigInt]::ModPow($g, $e, $p) -ne $etotient ){
$g = [BigInt]::Add($g, $Two)
}
return $g
}
function getRandom([BigInt]$p, [BigInt]$n) {
$rngValue = [System.Security.Cryptography.RNGCryptoServiceProvider]::new()
$bytesb = [byte[]]::new($n / 8)
$rngValue.GetBytes($bytesb)
$r = ([BigInt]::new($bytesb)) % $p
if($r -le [BigInt]::Zero ) {$r = [BigInt]::Add($r, $p) }
return $r
}
function encrypt($g, $p, $n, $message) {
$k=getRandom $p $n
$a = [BigInt]::ModPow($g, $k, $p)
$s = [BigInt]::ModPow($Y, $k, $p)
$b = ([BigInt]::Multiply([BigInt]::ModPow($g,$message,$p), $s)) % $p
return $a,$b
}
function decrypt($a, $b, $x, $p) {
$aval = [BigInt]::ModPow($a, $x, $p)
$aval_inv = inverse_mod $aval $p
$d = ([BigInt]::Multiply($aval_inv, $b)) % $p
return $d
}
function getPublic($x,$p) {
$g = getg $p
$Y = [BigInt]::ModPow($g, $x, $p)
return $Y,$g
}
function homomorphic_multiply($a1, $b1, $a2, $b2, $p) {
$a=($a1*$a2) % $p
$b=($b1*$b2) % $p
return ($a,$b)
}
$val1 = 123
$val2 = 2
try {
if ($Args.Count -gt 0) {
$val1=[BigInt]::new($Args[0])
}
} catch {
"Value needs to be an integer"
}
try {
if ($Args.Count -gt 1) {
$val2=[BigInt]::new($Args[1])
}
} catch {
"Value needs to be an integer"
}
$p = [BigInt]::Pow(2,255)-19
$n = 2048
"Val 1="+$val1
"Val 2="+$val2
$x = getRandom $p $n
"`nPrivate key: "+$x
"Prime: "+$p
$Y,$g= getPublic $x $p
"`nPublic key (Y,p,g)=",$Y, $p, $g
"`nCiphers:"
$a1,$b1=encrypt $g $p $n $val1
$a2,$b2=encrypt $g $p $n $val2
"a1="+$a1
"b1="+$b1
"a2="+$a2
"b2="+$b2
$a,$b = homomorphic_multiply $a1 $b1 $a2 $b2 $p
"`na="+$a
"b="+$b
$dec= decrypt $a $b $x $p
"`nDecrypted: "+$dec
for($i = 0; $i -lt 2000; $i++){
$val = [BigInt]::ModPow($g, $i, $p)
if ($val -eq $dec) {
"Found it at ",$i
}
}A sample run [here]:
Val 1=122
Val 2=2
Private key: 16496812066134065352625747472431048288924849722938781306291469136192341310617
Prime: 57896044618658097711785492504343953926634992332820282019728792003956564819949
Public key (Y,p,g)=
10181055631240001498380079590645796407907449551245607221580762986291822458513
57896044618658097711785492504343953926634992332820282019728792003956564819949
7
Ciphers:
a1=10683448160690312695903244142859159167196832848399627598185619780860843103655
b1=29565732844083454590782749218550092150527299920473543898530475724679885512953
a2=6300632463557400620506301727408004927474052872412783504636039628803464194321
b2=20391216365291122522128715970521496974634521886392909313929976995199849611635
a=28969447010372225719227707968760417392846872864645938324494322608338679198059
b=49509907940320866650685151338206303107363684561638631895244856535289000021012
Decrypted: 12584846349149963361443117732271090738781900948954492858144986148904760879551
Found it at
124
Subtraction
For subtraction, we modify with:
Conclusions
ElGamal methods are now being used in a range of homomorphic and zero-knowledge proof methods and are generally much less processor intensive than fully homomorphic encryption (FHE) methods. If you want to know more about ElGamal encryption, try here:
https://asecuritysite.com/elgamal/
and for PowerShell here: