Implementation of a privacy preserving KNN algorithm based on FHE

Abstract

Fully homomorphic encryption (FHE) is an encryption technique that allows computation to be performed on encrypted data without the need to decrypt it first. This has the potential to revolutionize data security and privacy, and ongoing research is focused on improving its efficiency and practicability. One limitation of FHE schemes is that, typically, they only support additions and multiplications. More complex operations, such as real number comparison, require careful design of new algorithms. In this project, we explore a recent approach based on polynomial composition for comparing two real numbers in a homomorphically encrypted setting. We study how this method can be used to sort an array of real numbers using FHE. We then apply these concepts to design and implement a fully homomorphic version of the popular Machine Learning algorithm known as k-nearest neighbours (KNN). To implement the FHE KNN algorithm, we use the CKKS scheme and the OpenFHE library, an open-source software library developed in C++. Finally, we analyse the computational performance of our implementation to evaluate its efficiency, depending on the dataset size and the number of neighbours. Our results indicate that the time complexity increases exponentially with the dataset size. Reasonable computation times are achievable for small datasets, with up to 16 training samples.

El xifratge totalment homomòrfic (FHE) és una tècnica d’encriptació que permet realitzar càlculs sobre dades encriptades sense necessitat de desencriptar-les prèviament. Això té el potencial de revolucionar la seguretat i privacitat de les dades, i la investigació en curs es centra en millorar la seva eficiència i practicabilitat. Una limitació dels esquemes basats en FHE és que, generalment, només permeten sumes i multiplicacions. Operacions mes complexes, com la comparació de nombres reals, requereixen un disseny meticulós de nous algoritmes. En aquest projecte, explorem una proposta recent basada en la composició de polinomis per comparar dos nombres reals en un entorn de xifratge homomòrfic. Estudiem com aquest mètode pot ser utilitzat per ordenar un conjunt de nombres reals utilitzant FHE. A continuació, apliquem aquests conceptes per dissenyar i implementar una versió totalment homomòrfica de l’algorisme popular d’aprenentatge automàtic conegut com a knearest neighbours (KNN). Per implementar l’algorisme de KNN amb FHE, utilitzem l’esquema CKKS i la llibreria OpenFHE, una llibreria de programari de codi obert desenvolupada en C++. Finalment, analitzem el rendiment computacional de la nostra implementació per avaluar-ne l’eficiència, en funció de la mida del conjunt de dades i del nombre de veïns. Els nostres resultats indiquen que la complexitat temporal augmenta exponencialment amb la mida del conjunt de dades. Obtenim temps de càlcul raonables per a conjunts de dades petits, amb fins a 16 mostres d’entrenament.

El cifrado totalmente homomórfico (FHE) es una técnica de encriptación que permite realizar cálculos sobre datos encriptados sin necesidad de desencriptarlos previamente. Esto tiene el potencial de revolucionar la seguridad y privacidad de los datos, y la investigación en curso se centra en mejorar su eficiencia y practicabilidad. Una limitación de los esquemas basados en FHE es que, generalmente, solo permiten sumas y multiplicaciones. Operaciones más complejas, como la comparación de dos números reales, requieren un diseño meticuloso de nuevos algoritmos. En este proyecto, exploramos una propuesta reciente basada en la composición de polinomios para comparar dos números reales en un entorno de cifrado homomórfico. Estudiamos como este método puede ser usado para ordenar un conjunto de números reales usando FHE. A continuación, aplicamos estos conceptos para diseñar e implementar una versión totalmente homomórfica del popular algoritmo de aprendizaje automático conocido como knearest neighbours (KNN). Para implementar el algoritmo de KNN con FHE, utilizamos el esquema CKKS y la librería OpenFHE, una librería de software de código abierto desarrollada en C++. Finalmente, analizamos el rendimiento computacional de nuestra implementación para evaluar su eficiencia, en función del tamaño del conjunto de datos y del número de vecinos. Nuestros resultados indican que la complejidad temporal aumenta exponencialmente con el tamaño del conjunto de datos. Obtenemos tiempos de cálculo razonables para conjuntos de datos pequeños, con hasta 16 muestras de entrenamiento.