Verifiable Query Processing over Outsourced Social Graph

Xin Yao, Rui Zhang, Dingquan Huang, Yanchao Zhang

Research output: Contribution to journalArticlepeer-review

3 Scopus citations


Social data outsourcing is an emerging paradigm for effective and efficient access to the social data. In such a system, a third-party Social Data Provider (SDP) purchases social network datasets from Online Social Network (OSN) operators and then resells them to data consumers who can be any individuals or entities desiring social data through query interfaces. The SDP cannot be fully trusted and may return forged or incomplete query results to data consumers for various reasons, e.g., in favor of the businesses willing to pay. In this paper, we initiate the study on verifiable query processing over outsourced social graph whereby a data consumer can verify both the integrity and completeness of any query result returned by an untrusted SDP. We propose three schemes for single-attribute queries and another scheme for multi-attribute queries over outsourced social data. The four schemes all require the OSN provider to generate some cryptographic auxiliary information, based on which the SDP can construct a verification object to allow the data consumer to verify the integrity and completeness of the query result. They, however, differ in how the auxiliary information is generated and how the verification object is constructed and verified. Detailed analysis and extensive experiments using a real Twitter dataset confirm the efficacy and efficiency of the proposed schemes.

Original languageEnglish (US)
Pages (from-to)2313-2326
Number of pages14
JournalIEEE/ACM Transactions on Networking
Issue number5
StatePublished - Oct 1 2021


  • Verifiable query processing
  • outsourced social graph
  • security

ASJC Scopus subject areas

  • Software
  • Computer Science Applications
  • Computer Networks and Communications
  • Electrical and Electronic Engineering


Dive into the research topics of 'Verifiable Query Processing over Outsourced Social Graph'. Together they form a unique fingerprint.

Cite this