Efficient and Verifiable Range Query Scheme for Encrypted Geographical Information in Untrusted Cloud Environments

Zhuolin Mei, Jing Zeng, Caicai Zhang, Shimao Yao, Shunli Zhang, Haibin Wang, Hongbo Li, Jiaoli ShiISPRS Int. J. Geo Inf 2024 · DOI

TL;DR

This paper introduces EVRQ, a novel scheme for secure and verifiable range queries on encrypted geographical data stored in untrusted cloud environments. It addresses privacy concerns and ensures data integrity by employing a map region tree, 0-1 encoding, Bloom filters, and cryptographic multiset accumulators, offering an efficient and trustworthy solution for location-based services.

What Problem Does This Paper Address?

Location-based services (LBS) are increasingly popular, relying on vast amounts of geographical data. To manage storage and computation burdens, data owners often outsource this data to cloud servers. However, this creates significant security and privacy challenges:

  • Data Privacy: Untrusted cloud servers could potentially access and analyze sensitive geographical data, inferring user movements or personal information.
  • Query Privacy: Query requests themselves can reveal user locations and intentions.
  • Data Integrity: Cloud servers might selectively process data to save resources, return incorrect results, or even tamper with the outsourced data.
  • Verification: Ensuring the accuracy and completeness of query results from an untrusted server is difficult.

Existing solutions like order-preserving encryption leak order information, while bucketization methods sacrifice query accuracy. Public-key encryption offers security but often suffers from performance issues, making it unsuitable for real-time LBS applications. This paper aims to bridge this gap by providing a scheme that is efficient, privacy-preserving, and verifiable in untrusted cloud environments.

Methods

The EVRQ scheme is built upon several key cryptographic and data structure techniques:

  • Map Region Tree (MRT): The geographical space is recursively divided into smaller regions (MRs). Each MR at the same level contains a similar number of Points of Interest (POIs), making it difficult for an attacker to infer location privacy from density distribution. This hierarchical structure forms a tree.
  • 0-1 Encoding: This technique converts numerical comparisons into set operations, facilitating efficient range query processing.
  • Hash Functions: Used extensively for generating unique identifiers and ensuring data integrity.
  • Bloom Filter: A probabilistic data structure used for efficient set membership testing, enabling quick verification of whether a query range intersects with a map region.
  • Cryptographic Multiset Accumulator: Used to prove set disjointness, providing a more robust verification mechanism, especially when Bloom filters might have false positives.

The process involves the data owner encrypting POIs and building an MRT index. This index, along with encrypted data, is sent to the cloud. Data users then generate a query token, which the cloud server uses to traverse the MRT index and retrieve relevant encrypted POIs. Crucially, the scheme includes mechanisms for the data user to verify the correctness and integrity of the query process.

Datasets

The paper describes experiments conducted using synthetically generated geographical data. These datasets varied in size, ranging from $2^6$ to $2^{14}$ distinct geographical data points, distributed evenly within map regions of increasing size ($[1,2^3] \times [1,2^3]$ up to $[1,2^7] \times [1,2^7]$). No specific real-world datasets were used or introduced.

Key Insights and Ideas

  • Privacy through Indistinguishable Regions: By ensuring that MRs at the same level have similar POI counts, the scheme prevents attackers from inferring location privacy by analyzing query patterns or data density.
  • Efficient Verification with Combined Techniques: The synergy between Bloom filters (for speed) and cryptographic multiset accumulators (for accuracy) provides a robust and efficient way to verify query results and process integrity, even in untrusted environments.
  • Transforming Comparisons to Set Operations: The use of 0-1 encoding is a clever way to translate spatial range queries into set intersection problems, which are more amenable to cryptographic processing and verification.
  • Balancing Efficiency and Security: The scheme aims to achieve a good balance, avoiding the performance bottlenecks of traditional public-key cryptography while offering stronger security guarantees than order-preserving methods.

Key Results

The experimental results demonstrate the efficiency of the EVRQ scheme:

  • Token Generation: EVRQ shows highly efficient query token generation, with its time increasing linearly with the average length of encodings for queried ranges. In contrast, the MDOPE scheme's token generation time increases exponentially.
  • Range Query: The time for range queries in EVRQ increases linearly with the index height, exhibiting highly efficient performance.
  • Verification: The correctness verification is consistently efficient, with minimal impact from index height. Integrity verification also remains highly efficient due to the speed of hash calculations.
  • Index Construction: While EVRQ's index construction is slower than MDOPE due to the additional verification information (hash values, accumulator values), this is a one-time cost performed offline and does not impact the user experience.

Limitations and Future Work

  • Index Construction Time: The paper acknowledges that EVRQ's index construction is slower than comparable schemes like MDOPE due to the overhead of generating verification information.
  • Bloom Filter False Positives: While mitigated by the cryptographic multiset accumulator, Bloom filters inherently have a low probability of false positives, which could slightly affect verification efficiency in rare cases.
  • Future Work: The paper doesn't explicitly detail future work, but the presented scheme lays a strong foundation for further research into secure and efficient LBS in cloud environments. Potential future directions could include exploring more advanced encryption techniques, optimizing index structures for specific geographical data distributions, or extending the scheme to support more complex query types.

Summary updated

BibTeX
@article{mei2024efficient,
  author = {Zhuolin Mei and Jing Zeng and Caicai Zhang and Shimao Yao and Shunli Zhang and Haibin Wang and Hongbo Li and Jiaoli Shi},
  title = {{Efficient and Verifiable Range Query Scheme for Encrypted Geographical Information in Untrusted Cloud Environments}},
  journal = {ISPRS Int. J. Geo Inf.},
  year = {2024},
  doi = {10.3390/ijgi13080281},
}
Figure