Homomorphic Subtraction Is So Much More Useful Than Homomorphic Addition?

Homomorphic Subtraction Is So Much More Useful Than Homomorphic Addition? Here’s Paillier Subtraction

Paillier addition is fairly straight forward, and where we multiply the ciphers, but the subtraction operation can be a little sticky. Overall finding delta (V_1-V_2) is probably more useful in homomorphic encryption than adding as we often look for differences in locations or for time stamps. The delta between two locations and for two time stamps is useful in contact tracing, and where we could search encrypted values for a when someone within a give distance and within a given time. For example, if we store distance values in metres (from Bluetooth estimations or GPS co-ordinates) and the time stamps in seconds, we could search for a delta for less than 10 metres and a time delta of less than 60 seconds.

So let’s do the basics. First we generate our encryption keys:

For a basic add operation, we have:

And, so to add encrypted values, we just multiply the ciphers (and using mod n²). Now we need to subtract. For this we divide the ciphers:

and which does a subtraction of the two values. And thus a subtraction is equivalent to a divide operation. For the divide, we need to perform a modular divide operation:

inv_cipher2, _ := crypto.Inv(cipher2, pub.N2)

and which is:

C_2^{-1}=InverseMod(C2,n²)

What we also need to do, is perform this operation when the result is greater than a given threshold:

m=m−n

and where N is (p.q).

Coding

The outline coding using the library from the Kryptography library. We have manually added the public and secret key, but in real-life we would generate with:

pub, sec, _ := paillier.NewKeys()

The code is [here]:

package main

import (
	"fmt"
	"math/big"
	"os"

	crypto "github.com/coinbase/kryptology/pkg/core"
	"github.com/coinbase/kryptology/pkg/paillier"
)

func main() {

	var sec paillier.SecretKey
	var pub paillier.PublicKey

	//	pub, sec, _ := paillier.NewKeys()

	pub.N, _ = new(big.Int).SetString("22203902867524505059996239340306362808852805402888214954381553003002718752808306965243974655390219346481612755387890570991182385566928749760445875916800573782909761881261515602762049819293013811136510263722491329215251675663091154175860620927146517652389408089110716148633480085801107700968384078929774277970426932561081560231010426294975678729992804063220974701278229766883426991469078323539488917623430196595127834729964807458110080684240115196595760172158113810254192728271785178985307185853395355962836026777351498860874006114137632167254987479651229489157192247478252351962954320801263428208801271515398015887801", 10)
	pub.N2 = new(big.Int).Mul(pub.N, pub.N)

	sec.N = pub.N
	sec.N2 = pub.N2
	sec.Lambda, _ = new(big.Int).SetString("11101951433762252529998119670153181404426402701444107477190776501501359376404153482621987327695109673240806377693945285495591192783464374880222937958400286891454880940630757801381024909646506905568255131861245664607625837831545577087930310463573258826194704044555358074316740042900553850484192039464887138985064438949068643503538028104882092520753872226183177268421975002892541203962036580811698912148170624870917841537346985483337432253649017635885024033744586145456966646545432316660152135614842196027111652507352356170725302821683928442675667004336523805058723372589095589316741830468728743532156406225121890756346", 10)
	sec.Totient, _ = new(big.Int).SetString("22203902867524505059996239340306362808852805402888214954381553003002718752808306965243974655390219346481612755387890570991182385566928749760445875916800573782909761881261515602762049819293013811136510263722491329215251675663091154175860620927146517652389408089110716148633480085801107700968384078929774277970128877898137287007076056209764185041507744452366354536843950005785082407924073161623397824296341249741835683074693970966674864507298035271770048067489172290913933293090864633320304271229684392054223305014704712341450605643367856885351334008673047610117446745178191178633483660937457487064312812450243781512692", 10)
	sec.U, _ = new(big.Int).SetString("11108720355657041776647490476262423100273444107890028034525926371450220865341816894255404548947647952186614924131107824022774134150177636593890919577479093776330856863330832621779073688637362125712752218152358601679371477743308049274665882845748928958872854339383876978533793119837835146167726752137945969833510158025058440018805812646143848801020667307117190186323497007267362203459968413761903710129427082211518450427328378521338965975284389455704146581178957343955351641425309976491396722227064973929033480821132777267246266490713852090985090755453080857556125803448778856380844874040092451545474091429770838805", 10)
	//	fmt.Printf("Pub N: %v\n", pub.N)
	//	fmt.Printf("Pub N2: %v\n", pub.N2)
	//	fmt.Printf("Sec: Lambda: %v\n", sec.Lambda)
	//	fmt.Printf("Sec: Totient: %v\n", sec.Totient)
	//	fmt.Printf("U: %v\n", sec.U)

	v1 := "223"
	v2 := "224"
	argCount := len(os.Args[1:])

	if argCount > 0 {
		v1 = os.Args[1]
	}
	if argCount > 1 {
		v2 = os.Args[2]
	}

	val1, _ := new(big.Int).SetString(v1, 10)
	val2, _ := new(big.Int).SetString(v2, 10)

	cipher1, c1, _ := pub.Encrypt(val1)

	cipher2, c2, _ := pub.Encrypt(val2)

	cipher3, _ := pub.Add(cipher1, cipher2)

	inv_cipher2, _ := crypto.Inv(cipher2, pub.N2)

	decrypted1, _ := sec.Decrypt(cipher3)

	cipher4, _ := pub.Add(cipher1, inv_cipher2)
	decrypted2, _ := sec.Decrypt(cipher4)

	fmt.Printf("\na=%s, b=%s\n", val1, val2)

	fmt.Printf("\nEnc(a)=%v, Enc(b)=%v\n", c1, c2)

	fmt.Printf("\n%s + %s = %s\n", val1, val2, decrypted1)
	if decrypted2.Cmp(new(big.Int).Div(pub.N, big.NewInt(2))) > 0 {
		// m = m - n
		fmt.Printf("%s - %s = %s\n", val1, val2, new(big.Int).Sub(decrypted2, pub.N))
	} else {
		fmt.Printf("%s - %s = %s\n", val1, val2, decrypted2)
	}

}

A sample run is [here]:

a=222, b=111

Enc(a)=4123713396782295395546480432454365091781387777982898723536535468749256037452325552832489640391195858176569392634107239750921417316120516938031229258411549347526245631980177840652405286440514767422617309460783160302377914820897903808339593343632276882477846038795699797652970615663245553991979812163282183682372383313317454334993247936145530279834970592622962511555959862047053218310346690716623470297451716605882000379793045350052548920725321297244842969331103633569269175013844021435414525656351516853741068445565513970559033253804865615370468841940729303206288642783869470895102051338404833043453471513957145920170, Enc(b)=15660309568903541632314809324261136277674874195109075429861596962691141435184725906608184997478240600847692798735768142508280427067529029728285016121221459949843879860720983192574465643627259618448454717908027735985759373210047479698210359064024825494863794457679393507259920693777562850992088613711971890223755243178548373739879092987038912299077891149162632696378010991651772987668647751112435744210343009496571473619701364329023883090112656329962060056169092637555076972231479510024440480256964211828423199550837533447615010964855057552710057935709425247696911285536341411257378407094964229391522530434288181349269

222 + 111 = 333
222 - 111 = 111

and for a negative result [here]:

a=101, b=103

Enc(a)=17572475769335828724660310419306063961599006599983059703317448406722823765878987998131328876311265771390170704350016536731220225296695336632684892335874000151961911366095140065531834508752838623631826390107955826415049213525515106479375181389774096320497971032487766649167615677276684798247869919204215983351330224204125488591536739268338001179396600874677502544602744320046146781972144615546146977075296800332072069863143687909907608595799208826528841034961511118984885233081867758015496497566324496647034610292532986586423826942852463574418697259827120721847724835056680145136301376921238673466880181950034919420040, Enc(b)=11484265809690830090329104155012501167666088557047403308853214214731615532084738581125014471253238833593641748516575032368674618252604586041461125528930535975494825662894027264181952286090475591909915338802470448812152594668032187091770436827619951140711628928235157186657368211157447774892105594324649941767948373204608893174274616301327332866870908634676623765848411654436775509531662248869050162068146245960901273518763535612245640093687612398353825923898958382093426373645418655895859863201685704130989647149766669322196892782322778305178480836769048415478549713998276704214920229325525152482896631734311030451471

101 + 103 = 204
101 - 103 = -2

Conclusion

And there you go, addition and subtraction in homomorphic encryption. If you want to learn more about homormorphic encryption, try here:

https://asecuritysite.com/homomorphic/

and more about Krytology here:

https://asecuritysite.com/kryptology