Paper 2024/1756

$\mathsf{Graphiti}$: Secure Graph Computation Made More Scalable

Nishat Koti, Technical University of Darmstadt
Varsha Bhat Kukkala, Independent Researcher
Arpita Patra, Indian Institute of Science Bangalore
Bhavish Raj Gopal, Indian Institute of Science Bangalore
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.

Metadata
Available format(s)
PDF
Category
Applications
Publication info
Published elsewhere. Minor revision. ACM CCS 2024
DOI
10.1145/3658644.3670393
Keywords
Secure graph analysissecure computationsecure shuffle
Contact author(s)
koti @ encrypto cs tu-darmstadt de
varshabhat15 @ gmail com
arpita @ iisc ac in
bhavishraj @ iisc ac in
History
2024-10-30: approved
2024-10-28: received
See all versions
Short URL
https://ia.cr/2024/1756
License
Creative Commons Attribution
CC BY

BibTeX

@misc{cryptoeprint:2024/1756,
      author = {Nishat Koti and Varsha Bhat Kukkala and Arpita Patra and Bhavish Raj Gopal},
      title = {$\mathsf{Graphiti}$: Secure Graph Computation Made More Scalable},
      howpublished = {Cryptology {ePrint} Archive, Paper 2024/1756},
      year = {2024},
      doi = {10.1145/3658644.3670393},
      url = {https://eprint.iacr.org/2024/1756}
}
Note: In order to protect the privacy of readers, eprint.iacr.org does not use cookies or embedded third party content.