Distributed Spatial Search Using Paillier Cryptosystem and a Distributed Ring Algorithm

Abstract

The problem of lack of anonymity and confidentiality can be experienced by those who collect statistical data online as well as those who provide the data. One end may be secure, for example, the one providing data, and yet the other end, for example, the one collecting data, may not be secure. In another scenario, both the data provider and collector may seek anonymity. Preventing the decryption of data provided while providing aggregated results is the best solution for such scenarios. To achieve this, this paper proposes a protocol that puts into application. Homomorphic Encryption and a Distributed Ring algorithm, to ensure data anonymity of both parties involved in a spatial search that is a data provider and a searcher. Firstly, we identify a Homomorphic Encryption technique that can work best for a spatial search by reviewing literature on Homomorphic Encryption techniques. Among the Homomorphic Encryption techniques reviewed were Rivest, Shamir and Adleman (RSA), El Gamal cryptosystem, Goldwasser-Micali cryptosystem, Benaloh cryptosystem, Paillier cryptosystem and Fully Homomorphic Encryption (FHE). After a comprehensive study, Paillier Homomorphic Encryption technique was identified as the best approach to be employed in securing a spatial search. Secondly, we propose a protocol for distributed spatial searching using Paillier cryptosystem and distributed ring algorithm principles. Finally, a proof of concept prototype using the proposed approach was implemented. From initial experiments conducted using the proposed approach, it is evident that the bigger cost comes from the communication over the network and less from the encryption algorithm and protocol itself. A 39.7% overhead when compared to the usefulness of the approach, is outweighed making the solution highly practical and useful.