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…
