Secure multi-party computation techniques enable in-depth analysis on joint graphs that inherently encompass comprehensive topology information and extended attributes, while preserving data privacy. In the two-party setting, existing approaches suffer from inefficiencies due to redundant secure sorting or costly secure shuffling operations required for secure message passing. Some works improve efficiency by relaxing security assumptions, either through differential privacy or by introducing helper parties.

Encrypted matrix-vector multiplication is a fundamental component of a variety of applications that involve data privacy concerns. Current algorithms utilizing fully homomorphic encryption (FHE) generally use batching to enhance computational efficiency while neglecting the sparsity of the matrices, a characteristic that exists naturally in many practical situations. Alternatively, porting plaintext algorithms that skip zero elements to address sparsity may fail to utilize batching and introduce additional privacy concerns.

Ego-centric queries, focusing on a target vertex and its direct neighbors, are essential for various applications. Enabling such queries on graphs owned by mutually distrustful data providers without breaching privacy holds promise for more comprehensive results. In this paper, we propose GORAM, a graph-oriented data structure that enables efficient ego-centric queries on federated graphs with strong privacy guarantees. GORAM leverages secure multiparty computation (MPC) and ensures that no information about the graphs or the querying keys is exposed during the process. For practical performance, GORAM partitions the federated graph and constructs an Oblivious RAM (ORAM )-inspired index atop these partitions. This design enables each ego-centric query to process only a single partition, which can be accessed fast and securely. Utilizing GORAM, we develop a prototype querying engine on a real-world MPC framework. We then conduct a comprehensive evaluation using five commonly used queries similar to the LinkBench workload description [11] on both synthetic and real-world graphs. Our evaluation shows that all five queries can be completed in just 58.1 milliseconds to 35.7 seconds, even on graphs with up to 41.6 million vertices and 1.4 billion edges. To the best of our knowledge, this represents the first instance of processing billion-scale graphs with practical performance on MPC.