Verifiable Spatial Range Query Over Encrypted Cloud Data in VANET

With the popularization of the geo-positioning technologies and Location Based Service (LBS), the spatial range query has gained increasing attention in VANET. To eliminate local data storage and computation burden, the data owner outsources his/her spatial data and the processing of range query tasks to location based service providers. However, outsourcing tasks may bring the risk of privacy leakage as location based service providers and clients, including data owner and data users are not in the same trusted domain. Besides, malicious service providers may forge or tamper retrieval results due to interest incentives such as saving storage or computational capacity. Therefore, we first propose and construct the Verifiable Spatial Range Query (VSRQ) scheme in VANET by using the hierarchical cell based encoding method, G-tree and the accumulator. To guarantee the correctness and completeness of search results, we leverage an accumulator-based technology. Then, we develop an improved G-tree to accelerate query processing and extend it to support multi-dimensional range queries. Security analysis shows that basic VSRQ and extension of VSRQ schemes are secure in terms of the privacy of index and confidentiality of spatial data. Extensive experiments further show that, basic (or extension of) VSRQ scheme can achieve result integrity while supporting spatial range query and lower computational and storage burden compared with existing schemes.