Paper 2019/820

Universal Location Referencing and Homomorphic Evaluation of Geospatial Query

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


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.

Note: (Author's version)

Available format(s)
Publication info
Preprint. MINOR revision.
Location privacyGeohashingSpatial cloakingHomomorphic encryption
Contact author(s)
ama9000 @ rit edu
2019-07-16: received
Short URL
Creative Commons Attribution


      author = {Asma Aloufi and Peizhao Hu and Hang Liu and Sherman S.  M.  Chow},
      title = {Universal Location Referencing and Homomorphic Evaluation of Geospatial Query},
      howpublished = {Cryptology ePrint Archive, Paper 2019/820},
      year = {2019},
      note = {\url{}},
      url = {}
Note: In order to protect the privacy of readers, does not use cookies or embedded third party content.