Image for post
Image for post
Photo by Rodion Kutsaev on Unsplash

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 ab. A sample run is [here]:

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]:

Image for post
Image for post

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):

Image for post
Image for post

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:

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.

[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.

Written by

Professor of Cryptography. Serial innovator. Believer in fairness, justice & freedom. EU Citizen. Auld Reekie native. Old World Breaker. New World Creator.

Get the Medium app

A button that says 'Download on the App Store', and if clicked it will lead you to the iOS App store
A button that says 'Get it on, Google Play', and if clicked it will lead you to the Google Play store