Privacy-preserving computation on graph-structured data

© 2019 Leyla RoohiThere are many examples of graph-structured data, like records of friendships in social networks, travel patterns in transport networks and communications meta-data in telecommunication networks, and many more. In such data, people are represented as nodes and their interactions as edges. Graphs can provide valuable information about people and their connections, however privacy disclosure of performing or releasing graph analysis is a major open challenge. Naive techniques such as anonymisation on edges and nodes have been shown to fall short: heuristically anonymised graphs still leak significant structural information that can be used to match individuals and recover sensitive information. In this thesis, we address important privacy disclosure scenarios while accessing graph databases in a cloud or in-house storage system. First, we propose a method for privately storing data on the cloud by leveraging secure multi-party computation that does not rely on trusting the cloud/processing servers. Second, we introduce a differentially private framework for joint computation by two parties on graph databases in performing efficient and accurate computation of node importance. Finally we contribute more efficient protocol design that overcomes the challenges of computation and communication complexity to compute egocentric betweenness centrality under differential privacy in multi-party settings. Remarkably our protocol incurs negligible utility loss as the number of parties scale and achieves strong privacy protections with practical runtime requirements