Cryptology ePrint Archive: Report 2020/242

Practical and Secure Circular Range Search on Private Spatial Data

Zhihao Zheng and Jiachen Shen and Zhenfu Cao

Abstract: With the location-based services booming, the volume of spatial data inevitably explodes. In order to reduce local storage and computational overhead, users tend to outsource data and initiate queries to the cloud. However, sensitive data or queries may be compromised if cloud server has access to raw data and plaintext token. To cope with this problem, searchable encryption for geometric range is applied. Geometric range search has wide applications in many scenarios, especially the circular range search. In this paper, we propose a practical and secure circular range search scheme (PSCS) to support searching for spatial data in a circular range. With Our scheme, a semi-honest cloud server will return the data for a given circular range correctly without revealing index privacy or query privacy. We propose a polynomial split algorithm which can decompose the inner product calculation neatly. Then, We formally define the security of our scheme and theoretically prove that it is secure under same-closeness-pattern chosen-plaintext attacks (CLS-CPA). In addition, we demonstrate the efficiency and accuracy through analysis and experiments compared with existing schemes.

Category / Keywords: secret-key cryptography / spatial data, cloud server, circular range search, index privacy, query privacy.

Date: received 22 Feb 2020, last revised 24 Feb 2020

Contact author: 460604723 at qq com

Available format(s): PDF | BibTeX Citation

Version: 20200225:203417 (All versions of this report)

Short URL: ia.cr/2020/242


[ Cryptology ePrint archive ]