Secure Undirected-Graph Computation Towards Efficiency and Scalability

Collaborative analysis on graph data from diverse sources has shown great promise in finance, social networking, and predictive modeling. However, efficiently collaborative graph-data computations involving different parties while ensuring data privacy pose a significant challenge. To address this issue, we introduce a novel secure undirected-graph message passing (SUMP) protocol, which is specially optimized for secure analysis of undirected graph data. Our SUMP algorithm adopts a newly designed encoding paradigm to reduce the processing overhead in existing algorithms. The data scale in processing is reduced by around 2× in our SUMP algorithm compared to existing works. We apply SUMP to implement a graph-analysis framework, Top-k common neighbors (TKCN), which facilitates analyzing the relationships related to entities in graphs. To further optimize the efficiency and scalability, we adopt fewer and more efficient secure binary operations, differently from numerous expensive secure comparison operations in existing implementations. Our evaluations on real-world datasets demonstrate that, our SUMP algorithm accelerates the state-of-the-art by 1.99×. Our secure TKCN implementation achieves a speed up by 700× over the state-of-the-art on large-scale datasets.