A k-Anonymous Location-Based Service Using Fully Homomorphic Encryption

This thesis investigates the potential implementation of a k-anonymization service for geolocation data based on fully homomorphic encryption, with particular attention to the computational cost of generating the anonymized position vector. Fully homomorphic encryption (FHE) allows an untrusted service provider to perform arbitrary computations on encrypted data without learning any information about either the inputs or the outputs of such computations. By taking advantage of this property of FHE, we used the Microsoft SEAL library to develop a k-anonymizer application that takes encoded position data from multiple clients, and returns the smallest region containing at least k users which also contains the requesting client's coordinates. In this context, we also designed a ciphertext-to-plaintext comparison algorithm which, for small plaintexts, is faster than the ciphertext-only alternative in existing literature. In order to analyze the feasibility of such a service in a real context, encoding of the position vectors is based on real world geographical data sourced from Open Street Map. For the same reason, we discuss potential ways to improve the performance of the anonymization service, particularly by comparing different algorithms, and by evaluating the impact of parallelization techniques, such as multi-threading and general-purpose GPU computing. From the results of these experiments, it is possible to conclude that a centralized implementation of the k-anonymization service is feasible when k is considerably smaller than the plaintext modulus of the FHE scheme used.