Welcome to the resource topic for 2024/1756
Title:
\mathsf{Graphiti}: Secure Graph Computation Made More Scalable
Authors: Nishat Koti, Varsha Bhat Kukkala, Arpita Patra, Bhavish Raj Gopal
Abstract: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, \mathsf{Graphiti}, that allows securely realising any graph algorithm. \mathsf{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 \mathsf{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 \mathsf{Scatter} primitive of GraphSC into separate operations of \mathsf{Propagate} and \mathsf{ApplyE}, (ii) designing a novel constant-round approach to realise \mathsf{Propagate}, as well as (iii) designing a novel constant-round approach to realise the \mathsf{Gather} primitive of GraphSC by leveraging the linearity of the aggregation operation. We benchmark the performance of \mathsf{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 10^7. Concretely it improves over the state-of-the-art up to a factor of 1034\times in online run time. Similar to GraphSC by Araki et al., since \mathsf{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\times in online run time when considering an input vector of size 10^7, in comparison to the state-of-the-art in the considered setting.
ePrint: https://eprint.iacr.org/2024/1756
See all topics related to this paper.
Feel free to post resources that are related to this paper below.
Example resources include: implementations, explanation materials, talks, slides, links to previous discussions on other websites.
For more information, see the rules for Resource Topics .