Efficient private counting of triangles and quadrangles in shared graphs
Trinqet: Private Triangle and Quadrangle Counting over Distributed Graphs
Cryptography and Security
Summary
Graphs split between multiple parties can hold sensitive information, making direct sharing impossible. Counting triangles and quadrangles in these distributed graphs helps understand their structure but must be done without revealing any private connections. The authors present Trinqet, which uses secure methods to count and list these patterns while avoiding unnecessary work by focusing on the graph's sparsity. Their approach keeps data private even against malicious attackers and runs much faster than previous methods.
What this means in practice
- •For network security teams: Analyze communication patterns across organizational boundaries without exposing sensitive link data by securely counting network substructures.
- •For social media platform engineers: Extract community structure features from user graphs shared among partners without compromising user privacy by privately counting triangles and quadrangles.
Authors
Mushtari Sadia, Amrita Roy Chowdhury
Abstract
Triangle and quadrangle counts are core statistics in graph analysis. Yet many real-world graphs are distributed across multiple parties and encode highly sensitive relationships, precluding direct data sharing. Secure multi-party computation (MPC) provides a principled alternative, but introduces a fundamental tension: the protocol must hide the graph's topology, forcing fully data-oblivious operations over all potential edges--while real-world graphs are extremely sparse, making most of this work wasted. We propose Trinqet, a system that resolves this tension through new MPC-friendly algorithms for private triangle and quadrangle detection. Trinqet safely exploits sparsity using a suite of novel techniques that eliminate vast numbers of unnecessary operations while preserving strong security in the malicious threat model. Trinqet supports both counting and enumeration and, in our evaluation, outperforms all five baselines by up to 10^5 in runtime.