A Fully-Homomorphic Encryption System for Privacy-Preserving Network-Based Contact Tracing

The Coronavirus outbreak from late 2019--early 2020 came with a number of challenges for humanity. Contact tracing is an important measure to decrease the further spread of the contagion. Traditionally, contact tracing systems are based on phone applications that check proximity with individuals confirmed positive for the virus and alert users of potential risks. The adoption of app-based solutions has been scarce, limiting their effectiveness. The main reasons for low adoption rates are either the majority of the population not being technologically savvy or not willing to have the apps installed on their phones. Additionally, the apps were perceived as posing a privacy risk, further hindering adoption. To overcome these issues, we present a network-based approach to contact tracing that relies on the emergence of 5G network coverage and geo-localization technologies which promise to reach sub-metre accuracy in upcoming years. The proposed system involves the cooperation between Mobile Operators (MO) and Government Agencies (GA). The former is assumed to be able to accurately estimate the locations of their users, while the latter is assumed to know the infection status of a country's citizens. Through exchanging these data, contacts with positive individuals can be detected. As both location data and infection status are highly sensitive, they cannot be exchanged in the clear. To ensure privacy, we propose a system allowing MOs and GA to perform computations directly on encrypted data. The underlying cryptographic scheme of our solution is based on fully-homomorphic encryption techniques that allow computations on encrypted data without knowledge of the decryption key, allowing outsourcing computations even to potentially untrusted parties. Our protocol uses the Cheon-Kim-Kim-Song (CKKS) cryptographic system to compute a score of infection likelihood, given the number of positive individuals in proximity within a given period. As computation of this score in encrypted domain is highly time-consuming, we propose approximations of several key operations performed. In doing so, reductions in computational time are achieved, at the expense of error in values of the score. Through simulations, the error versus computational time trade-off is evaluated. Results show computational times of up to several tens of minutes on a personal computer, with worst-case induced absolute errors of 0.6634.

L'epidemia di Coronavirus dalla fine del 2019 all'inizio del 2020 ha portato una serie di sfide per l'umanità. Il tracciamento dei contatti consente di diminuire l'ulteriore diffusione del contagio. Tradizionalmente, i sistemi di tracciamento si basano su applicazioni telefoniche che verificano la vicinanza con individui positivi al virus e avvisano gli utenti di potenziali rischi. L'adozione di soluzioni basate su app è stata scarsa, limitandone l'efficacia. Le ragioni principali sono la poca esperienza tecnologica di larga parte della popolazione e la poca disponibilità a installare le app sui propri telefoni. Inoltre, le app sono state percepite come un rischio per la privacy, ostacolandone ulteriormente l'adozione. Per superare questi problemi, proponiamo un sistema di tracciamento dei contatti basato sulle tecnologie di localizzazione delle infrastrutture telefoniche (e.g., 5G), che garantiranno un errore sotto al metro nei prossimi anni. Il sistema proposto prevede la cooperazione tra Operatori di telefonia mobile (MO) e Agenzie governative (GA). Si assume che il primo sia in grado di stimare con precisione la posizione dei propri utenti, e il secondo conosca lo stato di infezione dei cittadini di un paese. Attraverso lo scambio di questi dati si possono rilevare i contatti con individui positivi. Poiché sia i dati sulla posizione che lo stato dell'infezione sono altamente sensibili, non possono essere scambiati in chiaro. Per garantire la privacy, proponiamo un sistema che consenta a MO e GA di eseguire calcoli direttamente su dati crittografati. Lo schema crittografico alla base della nostra soluzione, di tipo fully homomorphich, permette calcoli su dati crittografati senza la conoscenza della chiave di decifratura, consentendo l'esternalizzazione dei calcoli anche a parti potenzialmente non attendibili. Il nostro protocollo utilizza il sistema crittografico Cheon-Kim-Kim-Song (CKKS) per calcolare un rischio di infezione, dato il numero di individui positivi nelle vicinanze in un determinato periodo. Data l'elevata complessità del calcolo nel dominio cifrato, proponiamo approssimazioni di diverse operazioni chiave eseguite. In tal modo, si ottengono riduzioni del tempo di calcolo, a scapito dell'errore nei valori del rischio. Attraverso simulazioni, viene valutato il trade-off tra errore e tempo computazionale. I risultati mostrano tempi di calcolo fino a diverse decine di minuti su un personal computer, con errori assoluti indotti nel caso peggiore di 0,6634.