Solving Location Privacy For COVID-19 Contract Tracing With Homomorphic Encryption

Solving Location Privacy For COVID-19 Contact Tracing With Homomorphic Encryption

The next few years will see the rise of homomorphic encryption and lattice encryption, and especially in protecting sensitive information. With partial homomorphic encryption (PHE) we can perform a few operations, such as with Pallier and where we can add two ciphered values [here]. But with full homomorphic encryption (FHE) we can perform add, subtract, multiply and divide. In this way, we can operate on encrypted values with our arithmetic operators, and then decrypt them to value the result of the operation.

One of the best methods around is HEAAN (Homomorphic Encryption for Arithmetic of Approximate Numbers) and which defines a homomorphic encryption (HE) library proposed by Cheon, Kim, Kim and Song (CKKS). CKKS uses approximate arithmetics over complex numbers, and where we take inputs of a and b and then encrypt them, and then subtract the encrypted values, and finally a result of a−b. A sample run is [here]:

HEAAN parameters : logN = 10, logQ = 30, levels = 8 (270 bits), logPrecision = 13, logScale = 30, sigma = 3.190000 

Input: 3.200000-7.300000
Cipher: &{[0xc00012b500 0xc00012b520] 0xc0000962c0 30 0xc00012b540 true false}

Decrypted: -4.10

I will not go into the detail of the method, but let’s see how it could be used in infection contact tracking. It uses the method of EPIC [1] [here]:

First Alice defines data in time stamps, and stores homomorphically encrypted timestamps for her location:

E(TIME1)a E(Location1)a
E(TIME2)a E(Location2)a
E(TIME3)a E(Location2)a

and where E(TIME1)a is the homomorphically encrypted timestamp value, and E(Location)a is the homomorphically encrypted location information. Now Alice and Bob upload their homomorphically encrypted time stamp and location information to the HA (Health Authority), and who stores these values:

E(TIME1)a E(Location1)a
E(TIME2)a E(Location2)a
E(TIME3)a E(Location2)a
E(TIME1)b E(Location1)b
E(TIME2)b E(Location2)b
E(TIME3)b E(Location2)b

The HA cannot tell either the time stamp or the location information. Alice is now identified as having COVID-19, and the server can identify her encrypted values and runs a homomorphic difference on the timestamps and location:

Alice — — — — — — — — — — Bob — — — — — — — — Time dif Location diff
E(TIME1)a E(Location1)a -> E(TIME1)b E(Location1)b +100 +5
E(TIME2)a E(Location2)a -> E(TIME2)b E(Location2)b +20 +3
E(TIME3)a E(Location2)a -> E(TIME3)b E(Location2)b -1 +1

Here the HA cannot tell where Bob and Alice were and at what time, but they can tell that there was a match for a one-second difference and where they were one metre away from each other. In this way, Bob could be informed of a possible infection. Other information too is stored and which can be used for the matching process, such as the device type, the SSID of the wireless access point that they connect to, and the RSSI (Received Signal Strength Indication):

In the following, I have used floating-point values, but it will work just as well with the integer values that would be used in time stamps. So let’s try the difference between a timestamp of ”1587000036" (04/16/2020 1:20am) and b=”1587000037":

And the code is here:

Conclusions

The method describes allows us to keep both contacts and location private, but allows users to match to those they have been in contact with.

Reference

[1] Altuwaiyan, T., Hadian, M., & Liang, X. (2018, May). EPIC: Efficient Privacy-Preserving Contact Tracing for Infection Detection. In 2018 IEEE International Conference on Communications (ICC) (pp. 1–6). IEEE.