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

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.