Trinity: A Scalable and Forward-Secure DSSE for Spatio-Temporal Range Query

Zhijun Li, Kuizhi Liu, Minghui Xu, Xiangyu Wang, Yinbin Miao, Jianfeng Ma, Xiuzhen Cheng

TL;DR

This paper introduces Trinity, a novel system for secure spatio-temporal range queries on cloud-based location data. Trinity-I offers efficient dynamic updates and scalability, while Trinity-II enhances this with forward security and reduced storage, achieving significant performance improvements over existing methods.

What Problem Does This Paper Address?

Location-based services (LBS) are increasingly popular, but outsourcing spatio-temporal data to cloud providers raises significant privacy concerns. Existing secure data retrieval schemes often struggle with dynamic updates to this data. Some schemes leak information during updates (lacking "forward security"), while others incur prohibitively high costs for adding or removing data, hindering real-world applications. Furthermore, spatio-temporal data grows continuously, making scalability a critical challenge. This paper tackles the need for a secure, efficient, scalable, and forward-secure system for querying dynamic spatio-temporal data in the cloud.

Methods

The paper proposes two schemes: Trinity-I and Trinity-II.

  • Trinity-I: This foundational scheme uses a filter-based approach. It leverages the Hilbert curve to convert 3D spatio-temporal data into a 1D representation, simplifying range queries. It employs a Quotient Filter (a space-efficient variant of Bloom filters) for fast membership testing and supports efficient dynamic updates (addition and deletion). To ensure privacy, it uses Symmetric-key Hidden Vector Encryption (SHVE) for secure query processing. Trinity-I is designed for low-cost dynamic updates and automatic index expansion.
  • Trinity-II: This scheme builds upon Trinity-I, adding enhanced security and efficiency. It introduces "salts" and CPRF (Cryptographic Pseudo-Random Function) techniques to achieve forward security, preventing attackers from inferring information about past queries from new data insertions. Trinity-II also incorporates a verification mechanism to reduce false positives and significantly cut down on storage requirements. This verification process allows for a higher false positive rate in the quotient filter itself, as the final results are validated.

Datasets

The paper evaluates the performance of Trinity-I and Trinity-II using a spatio-temporal dataset from Yelp. This dataset contains 1,007,016 timestamped locations, with some locations appearing multiple times at different timestamps. The authors define the context as a logistics transportation scenario, setting the spatial granularity to 10 meters and the temporal granularity to 5 minutes.

Key Insights and Ideas

  • Hilbert Curve for Dimensionality Reduction: Transforming 3D spatio-temporal data into 1D using Hilbert curves is an effective way to simplify range queries and improve efficiency.
  • Quotient Filters for Scalability and Efficiency: Quotient filters offer a good balance of space efficiency and fast lookups, making them suitable for large-scale spatio-temporal data. Their ability to support efficient deletion is a key advantage over traditional Bloom filters.
  • Forward Security is Crucial for Dynamic Data: The paper highlights that simply encrypting data isn't enough; protecting against information leakage during updates (forward security) is essential for preventing sophisticated attacks like file injection.
  • Verification as a Trade-off for Storage: By introducing a verification step, Trinity-II can tolerate a higher false positive rate in its underlying filter, leading to significantly reduced storage needs without compromising the accuracy of the final results.
  • Synergy of Techniques: The combination of Hilbert curves, quotient filters, SHVE, salting, and CPRF creates a robust system that addresses multiple challenges in secure spatio-temporal data management.

Key Results

  • Storage Reduction: Trinity-II significantly reduces storage requirements by 80% compared to Trinity-I.
  • Retrieval Speed: Trinity-II enables data retrieval at the 1 million-record level in just 0.01 seconds.
  • Update Efficiency: Trinity-II achieves up to 10x update efficiency compared to state-of-the-art methods.
  • Security: Both Trinity-I and Trinity-II are proven to be Indistinguishable under Selective Chosen-Plaintext Attack (IND-SCPA). Trinity-II also provides forward security.
  • Performance Comparison: In experiments, Trinity-I and Trinity-II generally outperformed existing methods like SKSE-II, GRS-II, and DSSESKQ in terms of setup latency, token generation, and search latency, especially at larger data scales. Trinity-II's EDB size was notably more compact.

Limitations and Future Work

  • Forward Security for Deletion: The paper notes that Trinity-II only provides forward security against attacks during the add operation. The leakage caused by the delete operation is not explicitly addressed, and backward security for spatio-temporal data retrieval schemes may require further improvement.
  • Hash Collisions in Trinity-II: The reduced capacity of the quotient filter in Trinity-II (due to storage optimization) can lead to more frequent hash collisions, potentially increasing query and update latency compared to Trinity-I.
  • Future Work: The authors suggest that further improvements in backward security for deletion operations would be beneficial.

Summary updated

Abstract

Cloud-based outsourced Location-based services significantly impact various aspects of daily life but also raise security concerns. Existing secure retrieval schemes for spatio-temporal data exhibit significant shortcomings regarding dynamic updates; they either compromise privacy through information leakage during updates (lacking forward security) or incur excessively high update costs, hindering practical application. To address these limitations, we first propose a basic filter-based spatio-temporal range query scheme Trinity-I that supports low-cost dynamic updates and automatic expansion. Furthermore, to improve security, reduce storage cost, and false positives, we propose a forward secure and verifiable scheme Trinity-II that simultaneously minimizes storage overhead. Formal security analysis demonstrates that both Trinity-I and Trinity-II achieve Indistinguishability under Selective Chosen-Plaintext Attack (IND-SCPA). Finally, extensive experiments demonstrate that our design Trinity-II significantly reduces storage requirements by 80%, enables data retrieval at the 1 million-record level in just 0.01 seconds, and achieves $10\times $ update efficiency than state-of-art.
BibTeX
@article{li2025trinity,
  author = {Zhijun Li and Kuizhi Liu and Minghui Xu and Xiangyu Wang and Yinbin Miao and Jianfeng Ma and Xiuzhen Cheng},
  title = {{Trinity: A Scalable and Forward-Secure DSSE for Spatio-Temporal Range Query}},
  journal = {IEEE Trans. Inf. Forensics Secur.},
  year = {2025},
  url = {https://openreview.net/forum?id=PNUc25scci},
}
Figure