PeGraph : A System for Privacy-Preserving and Efficient Search Over Encrypted Social Graphs

Research output: Journal Publications and Reviews (RGC: 21, 22, 62)21_Publication in refereed journalpeer-review

8 Scopus Citations
View graph of relations


Related Research Unit(s)


Original languageEnglish
Pages (from-to)3179-3194
Journal / PublicationIEEE Transactions on Information Forensics and Security
Online published24 Aug 2022
Publication statusPublished - 2022


With the widespread adoption of cloud computing, it is increasingly popular for online social network (OSN) service providers to leverage the public cloud as a back-end to manage their services for the cloud's well-understood benefits. However, the cloud is also notoriously subject to a wide attack surface, making it an imperative need to embed security in the cloud-backed OSN service from the very beginning. In light of this, in this paper, we design, implement, and evaluate PeGraph, the first system simultaneously allowing private, efficient, and rich queries over encrypted social graphs. PeGraph is aimed at safeguarding the confidentiality of the social graph at the cloud, while preserving the functionality of social search, a key enabler for quality OSN services like friend discovery and user targeting. PeGraph is built from a delicate synergy of insights from social graph modelling and lightweight cryptography such as searchable encryption and additive secret sharing, supporting rich social search queries like exact queries, fuzzy queries, and mixed queries. PeGraph also allows the cloud to obliviously render the encrypted social search results in a ranked order according to their importance, as per users' preferences. Extensive experiments demonstrate that PeGraph can securely process a wide range of practical social search queries within 1 second, over a real-world social graph consisting of millions of entities.

Research Area(s)

  • searchable encryption, secure computation, Social graph search, versatile queries