GraphSE$^2$: An Encrypted Graph Database for Privacy-Preserving Social Search
This addresses privacy concerns for users of social network services by enabling secure social search, though it is incremental as it builds on existing encrypted database and graph query techniques.
The paper tackles the problem of data breaches in online social networks by proposing GraphSE^2, an encrypted graph database that preserves social search functionality, and demonstrates its practicality by efficiently querying a social graph with a million users on Azure Cloud.
In this paper, we propose GraphSE$^2$, an encrypted graph database for online social network services to address massive data breaches. GraphSE$^2$ preserves the functionality of social search, a key enabler for quality social network services, where social search queries are conducted on a large-scale social graph and meanwhile perform set and computational operations on user-generated contents. To enable efficient privacy-preserving social search, GraphSE$^2$ provides an encrypted structural data model to facilitate parallel and encrypted graph data access. It is also designed to decompose complex social search queries into atomic operations and realise them via interchangeable protocols in a fast and scalable manner. We build GraphSE$^2$ with various queries supported in the Facebook graph search engine and implement a full-fledged prototype. Extensive evaluations on Azure Cloud demonstrate that GraphSE$^2$ is practical for querying a social graph with a million of users.