  Differentially private triangle counting in graphs is essential for analyzing
connection patterns and calculating clustering coefficients while protecting
sensitive individual information. Previous works have relied on either central
or local models to enforce differential privacy. However, a significant utility
gap exists between the central and local models of differentially private
triangle counting, depending on whether or not a trusted server is needed. In
particular, the central model provides a high accuracy but necessitates a
trusted server. The local model does not require a trusted server but suffers
from limited accuracy. Our paper introduces a crypto-assisted differentially
private triangle counting system, named CARGO, leveraging cryptographic
building blocks to improve the effectiveness of differentially private triangle
counting without assumption of trusted servers. It achieves high utility
similar to the central model but without the need for a trusted server like the
local model. CARGO consists of three main components. First, we introduce a
similarity-based projection method that reduces the global sensitivity while
preserving more triangles via triangle homogeneity. Second, we present a
triangle counting scheme based on the additive secret sharing that securely and
accurately computes the triangles while protecting sensitive information.
Third, we design a distributed perturbation algorithm that perturbs the
triangle count with minimal but sufficient noise. We also provide a
comprehensive theoretical and empirical analysis of our proposed methods.
Extensive experiments demonstrate that our CARGO significantly outperforms the
local model in terms of utility and achieves high-utility triangle counting
comparable to the central model.
