Secure Outsourced Top-k Selection Queries against Untrusted Cloud Service Providers

Xixun Yu, Yidan Hu, Rui Zhang, Zheng Yan, Yanchao Zhang

Research output: Chapter in Book/Report/Conference proceedingConference contributionScientificpeer-review

60 Downloads (Pure)


As cloud computing reshapes the global IT industry, an increasing number of business owners have outsourced their datasets to third-party cloud service providers (CSP), which in turn answer data queries from end users on their behalf. A well known security challenge in data outsourcing is that the CSP cannot be fully trusted, which may return inauthentic or unsound query results for various reasons. This paper considers top-k selection queries, an important type of queries widely used in practice. In a top-k selection query, a user specifies a scoring function and asks for the k objects with the highest scores. Despite several recent efforts, existing solutions can only support a limited range of scoring functions with explicit forms known in advance. This paper presents three novel schemes that allow a user to verify the integrity and soundness of any top-k selection query result returned by an untrusted CSP. The first two schemes support monotone scoring functions, and the third scheme supports scoring functions comprised of both monotonically non-decreasing and non-increasing subscoring functions. Detailed simulation studies using a real dataset confirm the efficacy and efficiency of the proposed schemes and their significant advantages over prior solutions.

Original languageEnglish
Title of host publicationProceedings of IEEE/ACM 29th International Symposium on Quality of Service, IWQOS 2021
Number of pages10
ISBN (Electronic)9781665414944
Publication statusPublished - 26 Aug 2021
MoE publication typeA4 Article in a conference publication
EventInternational Symposium on Quality of Service - Virtual, Online, Tokyo, Japan
Duration: 25 Jun 202128 Jun 2021
Conference number: 29


ConferenceInternational Symposium on Quality of Service
Abbreviated titleIWQOS


Dive into the research topics of 'Secure Outsourced Top-k Selection Queries against Untrusted Cloud Service Providers'. Together they form a unique fingerprint.

Cite this