Cryptology ePrint Archive: Report 2019/820

Universal Location Referencing and Homomorphic Evaluation of Geospatial Query

Asma Aloufi and Peizhao Hu and Hang Liu and Sherman S. M. Chow

Abstract: Location data is an important piece of contextual information in location-driven features for geosocial and pervasive computing applications. In this paper, we propose to geo-hash locations using space-filling curves, which are dimension reduction techniques that preserve locality. The proposed location referencing method is agnostic to specific maps or precoded location models and can effectively preserve users’ location privacy based on user preferences. We employ post-quantum-secure encryption on location data and privacy preferences to minimize the risk of data leakage. We also design three algorithms to homomorphically compute geospatial queries on the encrypted location data without revealing either user locations or user preferences. One of the three proposed algorithms reduces the multiplicative depth by more than half; thus, significantly speeding up homomorphic computations. We then present a prototype of the proposed system and algorithms using a somewhat homomorphic encryption scheme and our optimization techniques. A systematic evaluation of the prototype demonstrates its utility in spatial cloaking.

Category / Keywords: applications / Location privacy, Geohashing, Spatial cloaking, Homomorphic encryption

Date: received 14 Jul 2019

Contact author: ama9000 at rit edu

Available format(s): PDF | BibTeX Citation

Note: (Author's version)

Version: 20190716:122446 (All versions of this report)

Short URL:

[ Cryptology ePrint archive ]