Maintained by
Fengwei Wang, Hui Zhu, Rongxing Lu, Fen Liu, Cheng Huang and Hui Li
Xidian University
266 Xinglong Section of Xifeng Road, Xi'an, Shaanxi 710126, China


This paper proposes an efficient scheme, named CPSS, to perform privacy-preserving proximity detection based on chiphertext of convex polygon spatial search. We consider a scenario where users have to submit their location and search information to the social application server for accessing proximity detection service of location-based social applications (LBSAs). With proximity detection, users can choose any polygon area on the map and search whether their friends are within the select region. Since the location and search information of users are sensitive, submitting these data over plaintext to the social application server raises privacy concerns. Hence, we propose a novel method, with which users can access proximity detection without divulging their search and location information. Specifically, the data of a user is blurred into chipertext in client, thus no one can obtain the sensitive information except the user herself/himself. We prove that the scheme can defend various security threats and validate our scheme using a real LBS dataset. Also, we show that our proposed CPSS is highly efficient in terms of computation complexity and communication overhead.

  System Model

  Proximity detection with polygon spatial query

Conceptual architecture of proximity detection.


Orientation of point p and polygon vertexes.

  Proposed scheme

CPSS scheme.


The evaluation demo for CPSS.

  Computation complexity of CPSS

(a) Computation cost of QU vs PDCP.

(b) Computation cost of UF vs PDCP.

  Communication overhead of CPSS

Communication overhead vs PDCP.

  Demo Download

Demo Download:  
Demo File SHA256: B148B00393A8C1B773C578B9E61D8433538500EC076ECB4AE98CD4EAFD84A8C0
For Source Code:    zhuhui@xidian.edu.cn