SFTopk: Secure Functional Top-<inline-formula> <tex-math notation="LaTeX">$k$ </tex-math></inline-formula> Query via Untrusted Data Storage

Yao-Tung Tsou, Yung-Li Hu, Yennun Huang, Sy‐Yen Kuo

Abstract

Providing top-$k$ query services is relevant for storage servers which collect valuable files/data and process queries for data owners and mobile users. However, this kind of service could incur severe security concerns, because hackers or even the managers/administrators of the servers may steal important data sets and deceive users into responding to forged or incomplete query results. Therefore, these data sets need to be preserved in privacy, and moreover, the users should have the capability to verify the authenticity and integrity of the query results. As users will demand distinct information with various preferences and time domains in the pragmatic world, the traditional top-$k$ queries are insufficient to satisfy their demands. To solve the problem, we provide the functional top-$k$ queries in multi-dimensional space, such that the users can launch queries on the conjunction and sum of the dimensions/attributes. In this paper, we propose an efficient and effective method, called SFTopk, which addresses more challenging security problems in data privacy and verifiable functional top-$k$ queries in multi-dimensional space. From performance evaluation experiments, it is shown that our proposed method is much more efficient than the prior works in terms of communication overhead and computation cost.

Introduction: The Challenge of Untrusted Cloud Storage

As we outsource more data to third-party storage providers, we face a double-edged sword: scalability versus security. Data owners want to keep their data private, but they also need to search it. Standard encryption makes searching nearly impossible without downloading and decrypting everything.

Furthermore, storage servers are often "untrusted." A malicious or lazy server might return forged data or—more subtly—incomplete results (e.g., returning the "top 10" but skipping the actual #1 to save computation). While existing research has tackled secure "top-$k$" queries, most solutions only work for a single attribute. In the real world, we need functional top-$k$ queries that consider multiple dimensions simultaneously, such as the sum of blood sugar and blood pressure in medical records.

System architecture of SFTopk showing data owners, storage servers, and end users.

Methodology: The SFTopk Framework

The authors propose SFTopk, which combines standard cryptographic tools with a novel data structure to ensure both privacy and verifiability:

  • Standard Tools: It uses AES for file encryption and Order-Preserving Symmetric Encryption (OPSE) for data indices. OPSE allows the server to compare values (to see which is larger) without knowing the actual values.
  • The Novelty: Layered Authenticity (LA) Tree: Traditional Merkle Hash Trees (MHT) only verify data in one dimension. The LA Tree builds an "order-relation graph" that captures multi-dimensional relationships using dominant linkages (where one data point is better than another in all dimensions) and order linkages (descending order in a specific dimension).
  • Verification Mechanism: When a server returns a result, it also sends a set of "verifiable objects" (hashes) and encrypted adjacency lists. The user can reconstruct the verification path to prove the data is authentic and use the adjacency lists to ensure no "better" data points were omitted.
A hierarchical verification structure used to ensure data integrity and completeness.

Performance Evaluation

The paper evaluates SFTopk using realistic data sets designed to simulate practical applications, including Personal Health Records (PHR) (blood sugar, blood pressure, etc.) and Job Seeker Preferences (salary, commuting distance, etc.). The experiments scaled these datasets up to 600 data points across 1 to 3 dimensions.

Key results include:

  • Computation Speed: For a dataset of 300 points with 2 dimensions, SFTopk required roughly 17,974 $\mu s$ for the data owner to process, compared to 30,594 $\mu s$ for previous methods like SPLTopk.
  • Communication Efficiency: SFTopk is significantly leaner; in the same scenario, prior methods required nearly twice the bandwidth compared to SFTopk.
  • Scalability: As the number of dimensions ($m$) increases, SFTopk’s performance advantage grows linearly, whereas prior methods often saw exponential increases in overhead.

Discussion and Future Directions

While SFTopk protects raw data, it relies on Order-Preserving Encryption (OPSE), which inherently leaks the relative order of data points to the server. While this is a necessary trade-off for efficiency, highly sensitive applications might require even stronger privacy-preserving techniques.

Additionally, the current model focuses on static datasets. Future work could explore how the LA Tree handles frequent, real-time data insertions and deletions without requiring a full rebuild of the verification structure.

Summary updated

Abstract

Providing top-k query services is relevant for storage servers which collect valuable files/data and process queries for data owners and mobile users. However, this kind of service could incur severe security concerns, because hackers or even the managers/administrators of the servers may steal important data sets and deceive users into responding to forged or incomplete query results. Therefore, these data sets need to be preserved in privacy, and moreover, the users should have the capability to verify the authenticity and integrity of the query results. As users will demand distinct information with various preferences and time domains in the pragmatic world, the traditional top-k queries are insufficient to satisfy their demands. To solve the problem, we provide the functional top-k queries in multi-dimensional space, such that the users can launch queries on the conjunction and sum of the dimensions/attributes. Some recent works have studied how to preserve data privacy and/or integrity for top-k queries on data storage applications. However, these prior works are limited to traditional top-k queries in preserving data privacy and/or integrity without permitting to systematically process top-k queries over encrypted domain in multi-dimensional space and without providing an efficiently verifiable mechanism for the corresponding query results. In this paper, we propose an efficient and effective method, called SFTopk, which addresses more challenging security problems in data privacy and verifiable functional top-k queries in multi-dimensional space. From performance evaluation experiments, it is shown that our proposed method is much more efficient than the prior works in terms of communication overhead and computation cost.
BibTeX
@inproceedings{tsou2015sftopk,
  author = {Yao-Tung Tsou and Yung-Li Hu and Yennun Huang and Sy‐Yen Kuo},
  title = {{SFTopk: Secure Functional Top-\<inline-formula\> \<tex-math notation="LaTeX"\>$k$ \</tex-math\>\</inline-formula\> Query via Untrusted Data Storage}},
  booktitle = {IEEE Access},
  year = {2015},
  doi = {10.1109/access.2015.2511143},
}
Figure