Secure multi-party querying over graph databases

Abstract

Over the last twenty years, secure multi-party computation (SMPC) has emerged as an active research area focused on enhancing data privacy. SMPC has found applications in fields such as machine learning, secure voting, and data processing. Most applications of SMPC in the context of databases are integrated with relational data models; however, Not Only SQL (NoSQL) databases, particularly graph databases, have gained significant popularity in various applications. Despite their widespread use, the application of SMPC in the context of graph databases has been minimally explored. This raises the question of whether SMPC queries are limited to relational databases or if they can also operate on other types of databases. This thesis focuses on combining the advantages of SMPC with those offered by graph databases to enable secure multi-party querying. It presents methods for securing multi-party queries on federated graph databases while balancing the trade-off between security and performance. Central to this research is the development of efficient and secure querying methods, allowing multiple parties to collaborate without exposing sensitive data. Our contributions are primarily demonstrated through the Privacy-Preserving Multi-party Querying (PPMQ) framework, which integrates SMPC protocols and is designed to facilitate secure data querying and analysis over distributed graph databases. Initially, we introduced a foundational model called Secure Multi-Party Queries (SMPQ) as a proof of concept for secure multi-party querying tailored to graph databases, building on Conclave [85], a system designed for secure multi-party relational queries that uses JIFF [2] as the backend for SMPC protocols. The findings indicated that while SMPQ offers strong security, it still incurs significant overhead compared to Neo4j Fabric [62] for federated query execution. Further development led to the introduction of PPMQ, which aimed to reduce the overhead associated with the SMPQ model. To achieve this, the architecture of the SMPQ model was reviewed to identify areas for improvement. A major change involved the elimination of the Conclave layer, which added unnecessary complexity and overhead. By removing this layer and connecting directly to JIFF, performance was improved. The system offers two distinct security protocols: a client-based protocol and a server-based protocol. In the client-based protocol, standard SMPC techniques are employed, allowing computations to be performed on data without exposing the data itself. The server-based protocol employs SMPC to facilitate secure data processing and is further enhanced by encrypted hashing, which adds an additional layer of security to prevent data exposure. The results indicate that PPMQ’s execution times and overheads are comparable to those of Neo4j Fabric, while outperforming both SMPQ and Conclave, demonstrating its superior efficiency. This thesis also expands the traditional concept of SMPC to include secure multi-party querying, which is specifically designed to secure traversal queries over federated graph databases. To facilitate these queries, three distinct security protocols have been proposed: client-based, server-based, and a hybrid client/server-based approach. Each protocol presents a different trade-off between data exposure and performance, allowing users to select the most suitable option for their needs. Overall, this research presents a comprehensive framework for secure, efficient multi-party querying over federated graph databases, contributing to the fields of cryptography and data privacy.