Graphiti: Secure Graph Computation Made More Scalable

Privacy-preserving graph analysis allows performing computations on graphs that store sensitive information, while ensuring all the information about the topology of the graph as well as data associated with the nodes and edges remains hidden. The current work addresses this problem by designing a highly scalable framework, Graphiti, that allows securely realising any graph algorithm. Graphiti relies on the technique of secure multiparty computation (MPC) to design a generic framework that improves over the state-of-the-art framework of GraphSC by Araki et al. (CCS’21). The key technical contribution is that Graphiti has round complexity independent of the graph size, which in turn allows attaining the desired scalability. Specifically, this is achieved by (i) decoupling the Scatter primitive of GraphSC into separate operations of Propagate and ApplyE, (ii) designing a novel constant-round approach to realise Propagate, as well as (iii) designing a novel constant-round approach to realise the Gather primitive of GraphSC by leveraging the linearity of the aggregation operation. We benchmark the performance of Graphiti for the application of contact tracing via BFS for 10 hops and observe that it takes less than 2 minutes when computing over a graph of size 107. Concretely it improves over the state-of-the-art up to a factor of 1034× in online run time. Similar to GraphSC by Araki et al., since Graphiti relies on a secure protocol for shuffle, we additionally design a shuffle protocol secure against a semi-honest adversary in the 2-party with a helper setting. Given the versatility of shuffle protocol, the designed solution is of independent interest. Hence, we also benchmark the performance of the designed shuffle where we observe improvements of up to 1.83× in online run time when considering an input vector of size 107, in comparison to the state-of-the-art shuffle protocol in the considered setting.