# CARGO: Crypto-Assisted Differentially Private Triangle Counting without
Trusted Servers

Shang Liu  Kyoto University
<EMAIL_ADDRESS>Yang Cao  Hokkaido University
<EMAIL_ADDRESS>Takao Murakami  Jinfei Liu  Institute of Statistical
Mathematics
<EMAIL_ADDRESS>Zhejiang University, ZJU-Hangzhou GSTIC
<EMAIL_ADDRESS>Masatoshi Yoshikawa  Osaka Seikei University
<EMAIL_ADDRESS>
###### Abstract

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.

###### Index Terms:

differential privacy, cryptography, triangle counting, untrusted server

##  I Introduction

Graph data analysis is gaining popularity in various fields such as social
networks, transportation systems, and protein forecasting due to its
widespread presence. In graph analysis, triangle counting[1] is a crucial
component for downstream tasks, including clustering coefficient [2],
transitivity ratio [3], and structural similarity [4]. However, triangle
counting involves sensitive individual information that could be leaked
through the results of the process [5]. Differential privacy (DP) [6, 7] has
been widely used to provide formal privacy protection. Existing works on
differentially private triangle counting [8, 9, 10, 11, 12, 13] are mainly
based on two DP models depending on the trust assumption of the server:
_central differential privacy_ (CDP), which requires a trusted server, and
_local differential privacy_ (LDP), which is preferable since it does not rely
on a trusted server.

However, there is a significant utility gap between CDP-based [8, 9, 10] and
LDP-based [14, 11, 12, 13] of differentially private triangle counting,
depending on whether or not there is a trusted server needed. In particular,
CDP-based triangle counting models (as shown in Fig. 1(a)) need a trusted
server to collect the whole graph before executing differentially private
graph analysis. For a graph with $n$ users and a privacy budget $\varepsilon$,
the squared error of the central model is at most
$O(\frac{d_{max}^{2}}{\varepsilon^{2}})$, where $d_{max}$ is the maximum
degree in a graph. In contrast, existing LDP-based triangle counting models
(as shown in Fig. 1(c)) do not require a trusted server. Instead, each user
perturbs its sensitive information using an LDP mechanism and sends noisy data
to the untrusted server. The server then aggregates the data and releases a
noisy triangle count. However, LDP-based triangle counting models incur more
error of
$O(\frac{e^{\varepsilon}}{(e^{\varepsilon}-1)^{2}}(d_{max}^{3}n+\frac{e^{\varepsilon}}{\varepsilon^{2}}d_{max}^{2}n))$
(refer to Table 2 in [11] as the state-of-the-art LDP-based triangle counting
protocol), which is much larger than that of CDP-based models, especially,
when $n$ is large.

Figure 1: A comparison among CDP-based model, LDP-based model and CARGO. (a)
CDP-based model relies on a trusted server and achieves a high accuracy, e.g.,
$O(\frac{d_{max}^{2}}{\varepsilon^{2}})$ error; (c) LDP-based model removes a
trusted server but introduces more error, i.e.,
$O(\frac{e^{\varepsilon}}{(e^{\varepsilon}-1)^{2}}(d_{max}^{3}n+\frac{e^{\varepsilon}}{\varepsilon^{2}}d_{max}^{2}n))$;
(b) Our CARGO achieves a good utility like CDP-based model, i.e.,
$O(\frac{d_{max}^{\prime 2}}{\varepsilon^{2}})$, but without a trusted server
like LDP-based model, where $\varepsilon,n,d_{max},d_{max}^{\prime}$ denote
the privacy budget, number of users, true maximum degree, and noisy maximum
degree, respectively.

In this paper, we propose a crypto-assisted differentially private triangle
counting system (CARGO) that (1) achieves the high-utility triangle counting
of the central model (2) without a trusted server like the local model. Our
goal is to calculate the triangles in a graph, where each node represents a
user and each edge denotes the relationship between users, while protecting
each user’s neighboring information (i.e., edges). Our system is inspired by
recent studies [15, 16, 17, 18, 19, 20, 21, 22] that employ cryptographic
techniques to bridge the utility gap between LDP and CDP models. However,
these systems are specifically designed to process tabular data [15, 16, 17]
or gradients in federated learning [18, 19, 20] but not graph data. Designing
secure and private methods for counting triangles requires new principles due
to the high sensitivity of triangle counting and the limited view of local
users for a global graph. As shown in Fig. 1(b), CARGO establishes a trust
boundary for local data by leveraging cryptographic primitives and distributed
differential privacy instead of injecting LDP noise, allowing for high-utility
triangle counting comparable to that of CDP-based models (see more details in
section III-A). We now elaborate on our key contributions:

Similarity-based projection. We propose a novel local projection method to
reduce the sensitivity of the triangle counting while preserving more
triangles. A significant obstacle in achieving differential privacy in
counting triangles is the high sensitivity of triangle queries, leading to
more noises needed for differentially private results. The basic idea to
address this in a central setting [10, 23] is to project (i.e., truncate) the
original graph into a bounded graph. The previous local graph projection
method via randomly deleting edges [11] tries to reduce the sensitivity but
results in much projection loss. Our similarity-based projection method relies
on the significant fact that node degrees of a triangle are pretty similar to
each other [24]. We prioritize deleting the edges with the least possibility
of constructing triangles, which results in preserving more triangles. It is
worth noting that this simple yet efficient local projection algorithm can
also be used to improve the utility of locally private triangle counting
(details in Section III-C).

ASS-based triangle counting. We introduce a novel triangle counting algorithm
based on an additive secret sharing (ASS) technique [25]. Local users often
face difficulties in calculating triangle counts due to their limited view of
the global graph. This limitation prevents them from seeing the third edges
between others. The state-of-the-art triangle counting method [11] attempts to
address this problem in untrusted settings by including an additional round of
interaction. However, there is still a significant gap in utility compared to
the central model. We propose a secure triangle counting method based on the
ASS method with high accuracy. A triangle exists in a graph if three edges of
a triple exist simultaneously. Namely, the multiplication of three bits in a
matrix is equal to 1. We introduce a protocol for multiplying three secret
values, which allows us to securely and accurately compute the triangle counts
while protecting sensitive neighboring information (details in Section III-D).

Distributed perturbation. We present a distributed perturbation method by
combining additive secret sharing [25] and distributed noise generation [26,
27, 28]. The previous state-of-the-art crypto-assisted differential privacy
(crypto-assisted DP) method [16] randomizes the private value by adding two
instances of Laplace noise, which leads to significant loss of utility. Our
distributed perturbation adds minimal but sufficient noise to the local user
data. This partial noise is insufficient to provide an LDP guarantee but the
aggregated noise is enough to provide a CDP protection. Furthermore, secret
sharing ensures that two untrusted servers only see encoded values beyond
other information. And the final aggregated noise can provide
$\varepsilon$-Edge Distributed Differential Privacy (DDP) guarantee (details
in Section III-E).

Comprehensive theoretical and empirical analysis. We provide a comprehensive
theoretical analysis of our proposed protocols, including utility, privacy,
and time complexity. In particular, we provide the upper-bounds on the
estimation error for triangle counting and find that CARGO can significantly
reduce the estimation error of local models. Additionally, we prove that our
proposed CARGO satisfies $\varepsilon$-Edge DDP (details in Section IV).
Finally, several experiments have been conducted to demonstrate that our CARGO
achieves high-utility triangle counts comparable to central models, and
significantly outperforms local models by at least an order of 5 in utility
(details in Section V).

##  II Preliminaries

###  II-A Problem Statement

####  II-A1 Graphs and Triangle Counting

In our work, we consider an undirected graph with no additional attributes on
nodes or edges, which can also be represented as $G=(V,E)$, where
$V=\\{v_{1},...,v_{n}\\}$ is the set of nodes, and $E\subseteq V\times V$ is
the set of edges. Each local user $v_{i}$ owns one adjacent bit vector
$A_{i}=\\{a_{i1},...,a_{in}\\}$ that records the neighboring information,
where $a_{ij}=1,j\in[n]$ if and only if edge $\langle v_{i},v_{j}\rangle\in
E$. The adjacent bit vectors of all local users compose a symmetric adjacency
matrix $A=\\{A_{1},A_{2},...,A_{n}\\}$. A triangle in a graph $G$ consists of
three nodes where each node connects to the other two nodes. Table I
summarizes the major notations used in this paper.

TABLE I: Summary of Notations. Notation | Definition
---|---
$G=(V,E)$ |  Graph with nodes $V$ and edges $E$
$n$ | Number of users
$v_{i}$ |  $i$-th node in $V$
$d_{i}$ |  Node degree of $v_{i}$
$A$ | Adjacent matrix
$A_{i}$ |  Adjacent bit vector of $v_{i}$
$D$ | True degree set
$D^{\prime}$ | Noisy degree set
$d_{max}$ | True maximum degree
$d_{max}^{\prime}$ | Noisy maximum degree
$\triangle$ | Sensitivity of triangle counting
$T$ | True number of triangles
$T^{\prime}$ | Noisy number of triangles

####  II-A2 Trust Assumptions

Our system includes $n$ users and two servers, as illustrated in Fig. 2. We
assume that two servers are _semi-honest_ and _non-colluding_. This is a
common assumption in cryptographic systems, such as [16, 29, 30, 18], and can
be enforced via strict legal bindings. Semi-honest implies that they follow
the protocol instructions honestly but may be curious about additional
information. Non-colluding means that they do not disclose any information to
each other beyond what is allowed by the defined protocol. Furthermore, we
assume that there are no corrupt users, and each user has a private channel
with each server to share sensitive information confidentially. We also assume
that any parties beyond the system, such as servers, analysts, or other
individuals, are adversaries who are computationally constrained.

####  II-A3 Utility metrics

We use two common utility metrics to evaluate our methods, including $l_{2}$
loss (e.g., squared error) like [31, 32], and relative error as with [33, 34].
To be specific, let $T^{\prime}$ be a private estimation of the true triangles
$T$. The $l_{2}$ loss function maps the true number of triangles $T$ and the
private estimation $T^{\prime}$ to the $l_{2}$ loss, which can be denoted by:
$l_{2}(T,T^{\prime})=(T-T^{\prime})^{2}$. When $T$ is large, the $l_{2}$ loss
may also be large. Thus, we also compute the relative error in our
experiments. The relative error is defined as:
$re(T,T^{\prime})=\frac{|T-T^{\prime}|}{T}$, where $T\neq$ 0.

###  II-B Differential Privacy on Graphs

Differential privacy (DP) [6, 7] has become a standard for privacy protection,
which can formalized in Definition 1. Based on different trusted assumptions,
DP can be divided into two types: _central differential privacy_ (CDP) and
_local differential privacy_ (LDP).

######  Definition 1 (Differential Privacy [6]).

Let $n$ be the number of users. Let $\varepsilon>0$ be the privacy budget. Let
$\mathcal{X}$ be the set of input data for each user. A randomized algorithm
$\mathcal{M}$ with domain $\mathcal{X}^{n}$ satisfies $\varepsilon$-DP, iff
for any neighboring databases $D,D^{\prime}\in\mathcal{X}^{n}$ that differ in
a single datum and any subset $S\subseteq Range(\mathcal{M})$,

$Pr[\mathcal{M}(D)\in S]\leq e^{\epsilon}Pr[\mathcal{M}(D^{\prime})\in S]$

In this work, we use the global sensitivity [6] to achieve the DP. The global
sensitivity considers the maximum difference between query results on two
neighboring databases.

Edge DP. As a graph consists of nodes and edges, there are two definitions
when DP is applied to either of them: _edge differential privacy_ (Edge DP)
[35] and _node differential privacy_ (Node DP) [35]. Edge DP guarantees the
output of a randomized mechanism does not reveal whether any friendship
information (i.e., edge) exists in a graph $G$; whereas Node DP hides the
existence of one user (e.g., node) along with her adjacent edges. Node DP
provides a stronger privacy guarantee since it protects not only edge
information but also node information. But Node DP brings much more error than
Edge DP. Considering our privacy goal (protecting the neighboring information)
and higher accuracy requirement, we choose to use Edge DP in our work like [8,
11, 14, 12, 13].

Definition 2 and Definition 3 give the formal definition of Edge CDP and Edge
LDP respectively. Edge LDP assumes that two edges $\langle v_{i},v_{j}\rangle$
and $\langle v_{j},v_{i}\rangle$ between user $v_{i}$ and $v_{j}$ are
different secrets [11].

######  Definition 2 (Edge CDP [36]).

Let $\varepsilon>0$ be the privacy budget. A randomized algorithm
$\mathcal{M}$ with domain $\mathcal{G}$ satisfies $\varepsilon$-Edge CDP, iff
for any two neighboring graphs $G,G^{\prime}\in\mathcal{G}$ that differ in one
edge and any subset $S\subseteq Range(\mathcal{M})$,

$Pr[\mathcal{M}(G)\in S]\leq e^{\epsilon}Pr[\mathcal{M}(G^{\prime})\in S]$

######  Definition 3 (Edge LDP [37]).

Let $\varepsilon>0$ be the privacy budget. For any $i\in[n]$, let
$\mathcal{M}_{i}$ be a randomized algorithm of user $v_{i}$. $\mathcal{M}_{i}$
satisfies $\varepsilon$-Edge LDP, iff for any two neighboring adjacent bit
vectors $A_{i}$ and $A_{i}^{\prime}$ that differ in one edge and any subset
$S\subseteq Range(\mathcal{M}_{i})$,

$Pr[\mathcal{M}_{i}(A_{i})\in S]\leq
e^{\epsilon}Pr[\mathcal{M}_{i}(A_{i}^{\prime})\in S]$

Edge DDP. Combining DDP [26, 27, 28] with standard Edge CDP (Definition 2), we
introduce an Edge Distributed Differential Privacy (Edge DDP) for protecting
triangle counting in CARGO. The formal definition is as follows:

######  Definition 4 (Edge DDP).

Let $\varepsilon>0$ be the privacy budget. Let $r_{i}$ be a distributed noise
generated by user $v_{i}$. A randomized algorithm $M$ with randomness over the
joint distribution of $\bm{r}$:=$(r_{1},...,r_{n})$ satisfies
$\varepsilon$-Edge DDP, iff for any neighboring graphs $G$ and $G^{\prime}$
that differ in one edge, for any output $y\in range(\mathcal{M})$,

$Pr[\mathcal{M}(G)=y]\leq e^{\varepsilon}Pr[\mathcal{M}(G^{\prime})=y]$

Note that both $\varepsilon$-Edge LDP (Definition 3) and $\varepsilon$-Edge
DDP (Definition 4) protect one edge with privacy budget $\varepsilon$. The
difference is that Edge LDP is for the local model, whereas Edge DDP is for
the crypto-assisted DP model. We use Edge LDP to prove Edge DDP for the entire
process of our CARGO.

###  II-C Additive Secret Sharing

In two-party additive secret sharing (ASS) [25], a private value is split into
two secret shares that can be used to construct the true value, like [38, 39,
40]. Each value is represented as an $l$-bit integer in the ring
$\mathbb{Z}_{2^{l}}$, and cannot reveal any information about the private
value. In this paper, we denote a secret share of $x$ by $\langle x\rangle$.
To additively share a secret value $x$, a random number
$r\in\mathbb{Z}_{2^{l}}$ is generated. Then the shares for parties $S_{1}$ and
$S_{2}$ can be represented as $\langle x\rangle_{1}=r$ mod $2^{l}$, $\langle
x\rangle_{2}=(x-r)$ mod $2^{l}$, respectively, where $\langle x\rangle=\langle
x\rangle_{1}+\langle x\rangle_{2}$. The basic operations naturally supported
in the ASS domain include addition and multiplication. Given two shared values
$\langle x\rangle$ and $\langle y\rangle$, each party $S_{i\in\\{1,2\\}}$
receives $\langle x\rangle_{i}$ and $\langle y\rangle_{i}$. Each party $S_{i}$
locally computes $\langle u\rangle_{i}$ = $\langle x\rangle_{i}$ \+ $\langle
y\rangle_{i}$. Then, the addition can be securely computed by aggregating
$\langle u\rangle_{1}$ and $\langle u\rangle_{2}$, i.e., $u=\langle
u\rangle_{1}+\langle u\rangle_{2}=\langle x\rangle_{1}$ \+ $\langle
x\rangle_{2}+\langle y\rangle_{1}+\langle y\rangle_{2}=x+y$. The
multiplication of two shared values may be complex. It needs one-round
communication of the Beaver triple, which can be prepared offline.

Figure 2: CARGO system.

##  III Cargo System

###  III-A Design principle

Our main idea is to let the users and two servers collaboratively compute
secret shares of the true triangle counts securely and add distributed
differentially private noise without requiring any trusted servers. The
previous crypto-assisted differentially private data analysis protocols [15,
16, 17, 18, 19, 20] are designed for the general tabular data. The high
sensitivity of triangle counting and the limited view of local users for a
global graph make these protocols less effective for private graph data
analysis. Furthermore, Crypt$\varepsilon$ [16], a state-of-the-art crypto-
assisted DP protocol, employs two non-colluding and untrusted servers to
independently add Laplace noise twice, resulting in twice the utility loss
compared to CDP models. To this end, we first design a novel local projection
based on triangle homogeneity to reduce the high sensitivity from $O(n)$ to
$O(d_{max}^{\prime})$ while preserving more triangles as much as possible.
Then, we propose a secure protocol for counting triangles using additive
secret sharing techniques, which enables users and two servers to
collaboratively calculate the secret shares of true triangle counts $T$, i.e.,
$\langle T\rangle_{1}$ and $\langle T\rangle_{2}$. We then introduce a
distributed perturbation algorithm that adds minimal yet sufficient noise to
triangles for privacy preservation. To safeguard the privacy of the partial
noise, users do not directly transmit it to the server. Each user encodes the
noise using additive secret sharing and then distributes it to the servers.
The servers integrate this encoded noise into their secret shares of the
triangle counts. By aggregating these shares, the servers can compute the
differentially private triangle counts accurately.

###  III-B Framework

Fig. 2 shows CARGO’s system architecture. CARGO involves two kinds of
entities: local users and two non-colluding servers. The local user $v_{i}$,
$i\in[n]$ ($n$ = number of users in a graph), owns the sensitive friendship
information which is represented as an adjacent bit vector. At the beginning,
local users interact with one of the servers for the private estimation of
maximum degree $d_{max}^{\prime}$. The local user then projects the original
adjacent bit vector into $d_{max}^{\prime}$-bounded adjacent bit vector (step
①). Next, the local user secretly shares her adjacent bit vector to two
servers and each server computes the secret share of the true triangle counts
(step ②). Subsequently, the local user generates a distributed noise and
secretly shares it with two servers. Two servers sum up their own shares of
the noise, and add aggregated noise into the share of the triangle counts,
respectively. In other words, each server obtains the secret share of the
noisy triangle counts personally. The final aggregation of two shares is equal
to the noisy triangle counts of the entire graph, which satisfies
$\varepsilon$-Edge Distributed DP (step ③).

Main Steps. Algorithm 1 presents the overall protocol of CARGO system, which
consists of three main steps:

Algorithm 1 Overall protocol of CARGO system

0: $G$ represented as adjacent lists $A=\\{A_{1},...,A_{n}\\}$,
---
True degree set $D=\\{d_{1},...,d_{n}\\}$,
Privacy budget $\varepsilon=\varepsilon_{1}+\varepsilon_{2}$

0: Noisy triangle count $T^{\prime}$

1: Initialize: $T=\varnothing$ Step 1: Similarity-based Projection

2: $(D^{\prime},d_{max}^{\prime})\leftarrow\mathsf{Max}(D,\varepsilon_{1})$
$\triangleright$ Algorithm 2

3: $\hat{A}\leftarrow\mathsf{Project}(A,D,D^{\prime},d_{max}^{\prime})$
$\triangleright$ Algorithm 3 Step 2: ASS-based Triangle Counting

4: $\langle T\rangle\leftarrow\mathsf{Count}(\hat{A})$ $\triangleright$
Algorithm 4Step 3: Distributed Perturbation

5: $T^{\prime}\leftarrow\mathsf{Perturb}(\langle
T\rangle,d_{max}^{\prime},\varepsilon_{2})$ $\triangleright$ Algorithm 5

6: return $T^{\prime}$

Step 1: _Similarity-based Projection_. Graph projection is the key technique
to reduce the global sensitivity from $O(n)$ to $O(\theta)$, where $\theta$ is
the projection parameter. Here, we set $\theta$ as the maximum degree
$d_{max}$ to avoid removing edges from an adjacent bit vector (e.g., to avoid
the loss of utility). However, there is no prior knowledge about the maximum
degree. CARGO recalls a $\mathsf{Max}(.)$ function (Algorithm 2) to privately
compute a noisy maximum degree $d_{max}^{\prime}$ that is approximately equal
to $d_{max}$, as shown in Table V. Next, each user transforms the original
adjacent bit vector into a $d_{max}^{\prime}$-bounded adjacent bit vector
using a $\mathsf{Project}()$ function (Algorithm 3). Previous local projection
method via randomly deleting edges [11] results in much projection loss. We
propose a similarity-based projection method by leveraging the triangle
homogeneity (Observation 1). During the projection, the user deletes the edges
with the least possibility of constructing triangles, and thus more triangles
are preserved (see more details in Section III-C).

Step 2: _ASS-based Triangle Counting_. Next, the true triangle count can be
computed based on the projected adjacent bit vector. The main challenge in
triangle counting is that each user has a limited view of a global graph. In
other words, local users cannot see the third edge between others. The
previous state-of-the-art two-round triangle counting method [11] in untrusted
settings leads to more errors. We propose an ASS-based triangle counting
method for securely and accurately calculating the triangle count. Each user
encodes each bit in its adjacent bit vector via additive secret sharing and
sends it to two sever. Each server obtains the secret share of the triangle
count and knows nothing about the true result. CARGO recalls a
$\mathsf{Count}()$ function (Algorithm 4) to calculate the number of triangle
counts securely and accurately via Additive Secret Sharing (ASS) (refer to
Section III-D for more details).

Step 3: _Distributed Perturbation_. After accurately calculating the shares of
triangle counts, CARGO employs a $\mathsf{Perturb}()$ function (Algorithm 5)
to privately estimate the triangle count of a graph. The previous state-of-
the-art crypto-assisted DP method [16] guarantees differential privacy by
incorporating two instances of Laplace noise, which results in a significant
loss of utility. We propose a distributed perturbation method by combining the
additive secret sharing and distributed noise. Each user first generates a
minimal but sufficient noise. Since such a small amount of noise is unable to
provide enough privacy guarantees compared with LDP, we employ ASS to let each
user split the generated noise into two secrets and share them with two
servers, respectively. The servers, in turn, are unable to decipher any
information about the noise independently. By merging the shared noise with
the shared triangle count, each server acquires a secret share of the noisy
triangle count. The final computation of the noisy triangle count, safeguarded
under $\varepsilon$-Edge Distributed DP by aggregating two shared noisy
results (details in Section III-E).

Extension to Node DP. CARGO can be extended to Node DP by revising Algorithm 2
and Algorithm 5. The main change is from the sensitivity updates. To be
specific, given the number of nodes $n$, in Algorithm 2, any change of one
node will influence the other $(n-1)$ node degrees in the worst case. Thus,
the sensitivity of $\mathsf{Max}$ is $O(n)$ when we use Node DP. Similarly,
the sensitivity of $\mathsf{Perturb}$ in Algorithm 5 becomes
$O\binom{d_{max}^{\prime}}{2}$. Although our algorithm $\mathsf{Project}$ can
reduce the high sensitivity from $O\binom{n}{2}$ to
$O\binom{d_{max}^{\prime}}{2}$, there are still much more utility loss than
Edge DP. Therefore, how to reduce the high sensitivity of Node DP while
preserving more triangles is the focus of future work.

Algorithm 2 $\mathsf{Max}$: private estimation of $d_{max}$

0: True degree set $D=\\{d_{1},...,d_{n}\\}$,
---
Privacy budget $\varepsilon_{1}$

0: Noisy maximum degree $d_{max}^{\prime}$

1: Initialize: $D^{\prime}=\varnothing$

2: for $i=1$ to $n$ do

3: $d_{i}^{\prime}\leftarrow d_{i}+\mathsf{Lap}(\frac{1}{\varepsilon_{1}})$

4: $D^{\prime}\leftarrow D^{\prime}\cup\\{d_{i}^{\prime}\\}$

5: Send $d_{i}^{\prime}$ to untrusted server

6: Server:
$d_{max}^{\prime}\leftarrow\mathsf{max}(d_{1}^{\prime},...,d_{n}^{\prime})$

7: return ($D^{\prime},d_{max}^{\prime}$)

###  III-C Similarity-based Projection

####  III-C1 Private Estimation of the Maximum Degree

In this work, we assign the maximum degree $d_{max}$ as the projection
parameter $\theta$ just like [11, 23], primarily for two main reasons. On the
one hand, as shown in Table IV, $d_{max}$ is much smaller than the number $n$
of users in real-world graphs, which can significantly reduce the sensitivity.
On the other hand, it avoids deleting neighboring friends from an adjacent
list ideally; i.e., it avoids the utility loss during the projection. In the
untrusted scenario, however, each user knows no about $d_{max}$ since it has a
limited view of the global graph. To handle this, local users privately
compute $d_{max}$ with the leverage of the server’s global view. Specifically,
as shown in Algorithm 2, each user $v_{i}$ first adds
$\mathsf{Lap(\frac{1}{\varepsilon_{1}})}$ to her node degree $d_{i}$. Here, we
use Edge LDP (Definition 3), and the sensitivity is one since two edges
$\langle v_{i},v_{j}\rangle$ and $\langle v_{j},v_{i}\rangle$ between user
$v_{i}$ and $v_{j}$ are different secrets [11], and any change of one edge
will influence one node degree. Then each user sends noisy degree
$d_{i}^{\prime}$ to the untrusted server. In CARGO, one of two parties $S_{1}$
and $S_{2}$ can be used for computing $d_{max}^{\prime}$. Finally, the server
computes the max value of the noisy degree sequence
$\\{d_{1}^{\prime},...,d_{n}^{\prime}\\}$ as $d_{max}^{\prime}$, and sends
$d_{max}^{\prime}$ back to local users. We denote this algorithm by
$\mathsf{Max}$.

####  III-C2 Local Graph Projection

Figure 3: Limitation of random deletion. Assume that $d_{max}^{\prime}$ is
equal to 3, if user $v_{4}$ (or $v_{5}$) projects the adjacent list by
deleting the edge $\langle v_{4},v_{5}\rangle$, all triangles in a graph will
be removed.  Figure 4: Local graph projection. Assume that $d_{max}^{\prime}$
is equal to 2, user $v_{2}$ projects the adjacent bit vector by deleting the
edge $\langle v_{2},v_{1}\rangle$ and edge $\langle v_{2},v_{5}\rangle$.

After obtaining the estimation of the maximum degree $d_{max}^{\prime}$, each
user $v_{i}$ transforms the original adjacent bit vector $A_{i}$ into a
$d_{max}^{\prime}$-bounded adjacent bit vector $\hat{A_{i}}$ via the graph
projection. Although there have been some works involving graph projection
methods [41, 11, 23, 8], they do not perform in the triangle counting within
untrusted settings very well. For instance, the most related work is that
Imola et al. [11] implements graph projection via randomly deleting edges in
untrusted settings. However, this random projection possibly deletes key edges
involved in many triangles. For example, in Fig. 3, if user $v_{4}$ randomly
deletes the edge $\langle v_{4},v_{5}\rangle$ to bound the adjacent list, all
triangles in a graph will disappear.

We propose a similarity-based projection for reducing the global sensitivity
in untrusted scenarios. The main target of our methods is that the high global
sensitivity can be reduced while more triangles can be preserved after the
projection. As illustrated in Fig. 4, if $d_{i}>d_{max}^{\prime}$, user
$v_{i}$ will delete $(d_{i}-d_{max}^{\prime})$ friends from her adjacent bit
vector. The candidates to be deleted are selected based on significant
knowledge in the following observation:

Algorithm 3 $\mathsf{Project}$: Similarity-based Projection

0: Adjacent matrix $A$ of a graph
---
True degree set $D=\\{d_{1},...,d_{n}\\}$
Noisy degree set $D^{\prime}=\\{d_{1}^{\prime},...,d_{n}^{\prime}\\}$
Noisy maximum degree $d_{max}^{\prime}$

0: Projected adjacent matrix $\hat{A}$

1: for each user $v_{i},i\in[1,n]$ in a graph do

2: if $d_{i}>d_{max}^{\prime}$ then

3: Initialize: $ds=[0]*n,\hat{A_{i}}=\varnothing$

4: for $j=1$ to $n$ do

5: if $A_{ij}==1$ then

6: $ds[j]\leftarrow\mathsf{DS}(d_{i},d_{j}^{\prime})$

7: Sort $ds$ in ascending order

8: $\hat{ds}\leftarrow ds[1:d_{max}^{\prime}]$

9: for $j=1$ to $n$ do

10: if $ds[j]$ in $\hat{ds}$ then

11: $\hat{A_{i}}\leftarrow\hat{A_{i}}\cup\\{1\\}$

12: else

13: $\hat{A_{i}}\leftarrow\hat{A_{i}}\cup\\{0\\}$

14: else if $d_{i}\leq d_{max}^{\prime}$ then

15: $\hat{A_{i}}\leftarrow A_{i}$

16: return $\hat{A}$

######  Observation 1 (Triangle Homogeneity [24]).

Node degrees of a triangle are quite similar to each other in a graph (i.e.,
social and interaction graphs).

Durak et al. [24] demonstrate this observation through experiments conducted
on graphs from various scenarios. According to Observation 1, a significant
number of triangles can be preserved by selecting nodes with a high degree of
similarity. This is an intuition behind our proposed local graph projection
method in triangle counting. The degree similarity between two nodes is
quantified as outlined in Definition 5. It is important to note that Equation
1 reflects the relative difference in degrees between two nodes. Consequently,
a lower value of $DS(d_{1},d_{2})$ indicates a higher degree of similarity
between the nodes.

######  Definition 5 (Degree Similarity).

Given two node degrees $d_{1}$ and $d_{2}$ in a graph, the degree similarity
between them is computed by

$DS(d_{1},d_{2})=\frac{|d_{1}-d_{2}|}{d_{1}}$ (1)

Algorithm 3 shows the details of our local graph projection method. It takes
as input the adjacent matrix of a graph, true degree set $D$, noisy degree set
$D^{\prime}$, and noisy maximum degree $d_{max}^{\prime}$. If
$d_{i}>d_{max}^{\prime}$, each user $v_{i}$ first initializes an array $ds$
with size $n$ and an empty set $\hat{A_{i}}$, where $ds$ records degree
similarities and $\hat{A_{i}}$ is the projected adjacent bit vector (line 3).
Then user $v_{i}$ computes the degree similarities between $d_{i}$ and all her
friends based on Definition 5, and records the similarities using the array
$ds$ (line 5). Here, the neighboring node degrees are noisy degrees that have
been calculated in $\mathsf{Max}$ function (Algorithm 2). Then the array $ds$
is sorted in ascending order (line 6), and then the top $d_{max}^{\prime}$
elements are sliced and stored into the array $\hat{ds}$ (line 7). After that,
user $v_{i}$ traverses each neighboring friend $v_{k},k\in[n]$ and checks the
degree similarity $ds[k]$ between them. If the element $ds[k]$ is in
$\hat{ds}$, the bit ‘1’ will be added into $\hat{A_{i}}$; the bit ‘0’ will be
added otherwise (line 9-12). If $d_{i}\leq d_{max}^{\prime}$, the projected
adjacent bit vector $\hat{A_{i}}$ will be set as the original vector $A_{i}$.
The final answer is the projected adjacent matrix $\hat{A}$. We denote this
algorithm by $\mathsf{Project}$.

###  III-D Additive Secret Sharing-based Triangle Counting

Our triangle counting strategy is based on an intriguing fact that a triangle
exists if three neighboring edges of a triple exist simultaneously, namely,
$a_{ij}\times a_{ik}\times a_{jk}=1$, where $i,j,k\in[1,n]$. The challenge
lies in computing the multiplication of three adjacent bits while preserving
the privacy of neighboring information. We seek help from the multiplication
of secret values using additive secret sharing. However, existing protocols
[38, 39] mainly focus on multiplying two secret values, which cannot be
directly employed for triangle counting.

Algorithm 4 $\mathsf{Count}$: ASS-based Triangle Counting

0: Projected adjacent matrix $\hat{A}=\\{\hat{A_{1}},...,\hat{A_{n}}\\}$
---

0: Secret shares of triangle count $\langle T\rangle$

1: Initialize: $\langle T\rangle_{1}=\langle T\rangle_{2}=0$

2: for $i=1$ to $n$ do

3: for $j=i+1$ to $n$ do

4: for $k=j+1$ to $n$ do

5: Initialize:  $w=xyz,o=xy,p=xz,q=yz$
---
$\langle x\rangle_{1},\langle y\rangle_{1},\langle z\rangle_{1},\langle
w\rangle_{1},\langle o\rangle_{1},\langle p\rangle_{1},\langle
q\rangle_{1}\rightarrow S_{1}$
$\langle x\rangle_{2},\langle y\rangle_{2},\langle z\rangle_{2},\langle
w\rangle_{2},\langle o\rangle_{2},\langle p\rangle_{2},\langle
q\rangle_{2}\rightarrow S_{2}$

6: Server $S_{1}$: $\langle e\rangle_{1}=\langle a_{ij}\rangle_{1}-\langle
x\rangle_{1}$
---
$\langle f\rangle_{1}=\langle a_{ik}\rangle_{1}-\langle y\rangle_{1}$
$\langle g\rangle_{1}=\langle a_{jk}\rangle_{1}-\langle z\rangle_{1}$

7: Server $S_{2}$: $\langle e\rangle_{2}=\langle a_{ij}\rangle_{2}-\langle
x\rangle_{2}$
---
$\langle f\rangle_{2}=\langle a_{ik}\rangle_{2}-\langle y\rangle_{2}$
$\langle g\rangle_{2}=\langle a_{jk}\rangle_{2}-\langle z\rangle_{2}$

8: Server $S_{1}$ and $S_{2}$ communicate and obtain: $e=\langle
e\rangle_{1}+\langle e\rangle_{2}$, $f=\langle f\rangle_{1}+\langle
f\rangle_{2}$, $g=\langle g\rangle_{1}+\langle g\rangle_{2}$

9: Server $S_{1}$: $u_{1}=\langle w\rangle_{1}+\langle xy\rangle_{1}g+\langle
xz\rangle_{1}f+\langle yz\rangle_{1}e$
---
$+\langle x\rangle_{1}fg+\langle y\rangle_{1}eg+\langle z\rangle_{1}ef$

10: Server $S_{2}$: $u_{2}=\langle w\rangle_{2}+\langle xy\rangle_{2}g+\langle
xz\rangle_{2}f+\langle yz\rangle_{2}e$
---
$+\langle x\rangle_{2}fg+\langle y\rangle_{2}eg+\langle z\rangle_{2}ef+efg$

11: Server $S_{1}$: $\langle T\rangle_{1}\leftarrow\langle T\rangle_{1}+u_{1}$

12: Server $S_{2}$: $\langle T\rangle_{2}\leftarrow\langle T\rangle_{2}+u_{2}$

13: $\langle T\rangle\leftarrow\\{\langle T\rangle_{1},\langle
T\rangle_{2}\\}$

14: return $\langle T\rangle$

Motivated by this, we propose a secure multi-party triangle counting protocol
that executes the multiplication of three secret values utilizing additive
secret sharing. Given three secret values $a,b,c$, our goal is to compute the
multiplication of these three secrets while not leaking anything about
secrets, namely, $d=a\times b\times c$. Like the multiplication of two
secrets, two servers precompute Multiplication Groups (MGs) via oblivious
transfer [42, 43]. MGs refer to a set of shared values:$x,y,z,w,o,p,q$, where
$w=x\times y\times z,o=x\times y,p=x\times z,q=y\times z$. Each value is
represented as an $l$-bit integer in the ring $\mathbb{Z}_{2^{l}}$. In offline
phase, server $S_{1}$ receives $\langle x\rangle_{1},\langle
y\rangle_{1},\langle z\rangle_{1},\langle w\rangle_{1},\langle
o\rangle_{1},\langle p\rangle_{1},\langle q\rangle_{1}$, and server $S_{2}$
receives $\langle x\rangle_{2},\langle y\rangle_{2},\langle
z\rangle_{2},\langle w\rangle_{2},\langle o\rangle_{2},\langle
p\rangle_{2},\langle q\rangle_{2}$. After having shares of MGs, the
multiplication is performed as follows:

  1. 1.

Server $S_{i}$ $(i\in\\{1,2\\})$ computes $\langle e\rangle_{i}=\langle
a\rangle_{i}-\langle x\rangle_{i},$
$\langle f\rangle_{i}=\langle b\rangle_{i}-\langle y\rangle_{i},$ and $\langle
g\rangle_{i}=\langle c\rangle_{i}-\langle z\rangle_{i}$

  2. 2.

Both server $S_{1}$ and $S_{2}$ communicate to reconstruct $e,f,$ and $g$.

  3. 3.

Server $S_{i}$ computes its secret share of the multiplication result as:
$\langle d\rangle_{i}=\langle w\rangle_{i}+\langle xy\rangle_{i}g+\langle
xz\rangle_{i}f+\langle yz\rangle_{i}e+\langle x\rangle_{i}fg+\langle
y\rangle_{i}eg+\langle z\rangle_{i}ef+(i-1)efg$

######  Theorem 1.

Our proposed multiplication of three secret values is correct.

_Proof of Theorem 1_. $d=\langle d\rangle_{1}+\langle d\rangle_{2}=\langle
w\rangle_{1}+\langle xy\rangle_{1}g+\langle xz\rangle_{1}f+\langle
yz\rangle_{1}e+\langle x\rangle_{1}fg+\langle y\rangle_{1}eg+\langle
z\rangle_{1}ef+\langle w\rangle_{2}+\langle xy\rangle_{2}g+\langle
xz\rangle_{2}f+\langle yz\rangle_{2}e+\langle x\rangle_{2}fg+\langle
y\rangle_{2}eg+\langle z\rangle_{2}ef+efg$
$=w+xyg+xzf+yze+xfg+yeg+zef+efg$.
Then, we put $e=a-x,f=b-y,g=c-z$ into above equation and obtain $d=a\times
b\times c$.∎

Algorithm 4 shows how to securely calculate the secret shares of true triangle
count based on our proposed multiplication protocol of three secret shares. It
takes as input a projected graph that is represented as an adjacent matrix
$\hat{A}=\\{\hat{A_{1}},...,\hat{A_{n}}\\}$. It traverses all possible
triangle triples by computing $u=a_{ij}\times a_{ik}\times a_{jk}$. If $u=1$,
these three nodes and three edges constitute a triangle; otherwise not. Note
that we reduce the repeat computation by only $u=a_{ij}\times a_{ik}\times
a_{jk}(i<j<k)$. Each user secretly shares each bit of its adjacent bit vector
to two servers. Currently, server $S_{1}$ obtains $\langle a_{ij}\rangle_{1}$
and $S_{2}$ owns $\langle a_{ij}\rangle_{2}$, where $i,j\in[1,n]$. For each
possible triangle, it first initializes the multiplication groups including
$x,y,z,w,o,p,q$, where $w=x\times y\times z,o=x\times y,p=x\times z,q=y\times
z$. The multiplication groups can be precomputed in the offline phase and then
shared with two servers (line 5). After that, server $S_{1}$ computes $\langle
e\rangle_{1}=\langle a_{ij}\rangle_{1}-\langle x\rangle_{1}$, $\langle
f\rangle_{1}=\langle a_{ik}\rangle_{1}-\langle y\rangle_{1}$, $\langle
g\rangle_{1}=\langle a_{jk}\rangle_{1}-\langle z\rangle_{1}$. Server $S_{2}$
computes $\langle e\rangle_{2}=\langle a_{ij}\rangle_{2}-\langle
x\rangle_{2}$, $\langle f\rangle_{2}=\langle a_{ik}\rangle_{2}-\langle
y\rangle_{2}$, $\langle g\rangle_{2}=\langle a_{jk}\rangle_{2}-\langle
z\rangle_{2}$ (line 6-7). Next, two servers communicate and reconstruct $e,f,$
and $g$. It is worth noting that secret values are masked with random values
$x,y,z$, and thus any server knows nothing about $a_{ij},a_{ik},a_{jk}$. Then,
server $S_{1}$ computes the secret share of the current triangle, namely,
$u_{1}$. Server $S_{2}$ computes the secret share of the current triangle,
namely, $u_{2}$ (line 9-10). $S_{1},S_{2}$ adds $u_{1},u_{2}$ into $\langle
T\rangle_{1}$ and $\langle T\rangle_{2}$, respectively. Finally, each server
obtains the secret share of the true triangle counting, namely, $\langle
T\rangle_{1}$ and $\langle T\rangle_{2}$. The server cannot know any
information about true triangle count $T$ from $\langle T\rangle_{1}$ or
$\langle T\rangle_{2}$. The final answer of Algorithm 4 is the secret shares
of true triangles. We denote this algorithm by $\mathsf{Count}$.

Algorithm 5 $\mathsf{Perturb}$: Distributed Perturbation

0: Secret share of triangle count $\langle T\rangle$,
---
Noisy maximum degree $d_{max}^{\prime}$,
Privacy budget $\varepsilon_{2}$

0: Noisy triangle count $T^{\prime}$

1: for each user $v_{i}$, $i\in[1,n]$ do

2: $Gam_{1}=\mathsf{Gamma}(n,\frac{d_{max}^{\prime}}{\varepsilon_{2}})$

3: $Gam_{2}=\mathsf{Gamma}(n,\frac{d_{max}^{\prime}}{\varepsilon_{2}})$

4: $\gamma_{i}=(Gam_{1}-Gam_{2})$

5: Split $\gamma_{i}$ into two secret shares
$\gamma_{i}=\langle\gamma_{i}\rangle_{1}+\langle\gamma_{i}\rangle_{2}$

6: Send $\langle\gamma_{i}\rangle_{1},\langle\gamma_{i}\rangle_{2}$ to two
servers $S_{1},S_{2}$$\langle\gamma_{i}\rangle_{1}\rightarrow S_{1}$,
$\langle\gamma_{i}\rangle_{2}\rightarrow S_{2}$

7: Server $S_{1}$:  Aggregate $n$ shared distributed
---
$\langle\gamma\rangle_{1}=\sum_{i=1}^{n}\langle\gamma_{i}\rangle_{1}$

8: Server $S_{2}$:  Aggregate $n$ secret shares
---
$\langle\gamma\rangle_{2}=\sum_{i=1}^{n}\langle\gamma_{i}\rangle_{2}$

9: Server $S_{1}$:  Compute the secret share of $T^{\prime}$
---
$\langle T^{\prime}\rangle_{1}=\langle T\rangle_{1}+\langle\gamma\rangle_{1}$

10: Server $S_{2}$:  Compute the secret share of $T^{\prime}$
---
$\langle T^{\prime}\rangle_{2}=\langle T\rangle_{2}+\langle\gamma\rangle_{2}$

11: Server $S_{1},S_{2}$: Communicate and compute $T^{\prime}=\langle
T^{\prime}\rangle_{1}+\langle T^{\prime}\rangle_{2}$

12: return $T^{\prime}$

###  III-E Distributed Perturbation

Upon computing the true triangle count $T$, we can add DP noise into the
triangle count, in order to guarantee that the final output is differentially
private. The state-of-the-art crypto-assisted differential privacy model [16]
adds two instances of Laplace noise to the query result in tabular data
analysis. However, the additional round randomization brings more noise than
the CDP model. We propose a distributed perturbation method by combining the
additive secret sharing [25, 38, 39] and distributed noise generation method
[26, 27, 28]. Each user first generates sufficient but minimal noise and then
sends it to two servers. Since such a noise is also sensitive, we employ
additive secret sharing to encode the noise and share them with two servers,
respectively. The server can not obtain any information about each added noise
and the final noisy triangle count is protected under $\varepsilon$-Edge
Distributed DP. The Laplace mechanism has been widely used for protecting the
triangle counting in CDP or LDP model [8, 11, 13], and a key property of
Laplace distribution, namely, infinite divisibility [44, 28] (as presented in
Lemma 1), allows us to simulate the Laplace noise by summing up $n$ other
random variables from independent identically distribution.

######  Lemma 1 (Infinite Divisibility [44]).

Let $Lap(\lambda)$ denote a random variable that is sampled from a Laplace
distribution with _PDF_
$f(x,\lambda)=\frac{1}{2\lambda}e^{\frac{|x|}{\lambda}}$. Then the
distribution of $Lap(\lambda)$ is infinitely divisible; i.e., $Lap(\lambda)$
can be expressed as the sum of an arbitrary number of independent and
identically distributed (i.i.d.) random variables. Specifically, for arbitrary
integer $n\geq 1$,

$Lap(\lambda)=\sum_{i=1}^{n}[Gam_{1}(n,\lambda)-Gam_{2}(n,\lambda)],$ (2)

where $Gam_{1}(n,\lambda)$ and $Gam_{2}(n,\lambda)$ are independent Gamma
distributed random variables with densities as follows,

$Gamma(x,n,\lambda)=\frac{(1/\lambda)^{1/n}}{\Gamma(1/n)}x^{\frac{1}{n}-1}e^{-\frac{x}{\lambda}},$
(3)

where $\Gamma$ is the Gamma function, such that
$\Gamma(\beta)=\int_{0}^{\infty}x^{\beta-1}e^{-x}dx$.

Algorithm 5 contains the details of perturbing the triangle count using
distributed noise. It takes as input the encoded triangle count $\langle
T\rangle=\\{\langle T\rangle_{1},\langle T\rangle_{2}\\}$, noisy maximum
degree $d_{max}^{\prime}$, and privacy budget $\varepsilon_{2}$. According to
Lemma 1, one $Lap(.)$ random variable can be obtained by summing up $2n$
random variables. Each user $v_{i}$ samples two random variables $Gam_{1}$ and
$Gam_{2}$ from $\mathsf{Gamma}$ distribution, and then obtains a partial noise
by computing $\gamma_{i}=(Gam_{1}-Gam_{2})$ (line 2-4). To avoid the size of
noise, each user encodes $\gamma_{i}$ using additive secret sharing, i.e.,
$\gamma_{i}=\langle\gamma_{i}\rangle_{1}+\langle\gamma_{i}\rangle_{2}$, and
then sends the shares to two servers (line 5-6). Server $S_{1},S_{2}$ collects
all secret shares of the partial noise and aggregates them as:
$\langle\gamma\rangle_{1}=\sum_{i=1}^{n}\langle\gamma_{i}\rangle_{1}$ and
$\langle\gamma\rangle_{2}=\sum_{i=1}^{n}\langle\gamma_{i}\rangle_{2}$,
respectively (line 7-8). Each server adds the secret share of noise into the
share of triangle count, namely, $\langle T^{\prime}\rangle_{1}=\langle
T\rangle_{1}+\langle\gamma\rangle_{1}$ and $\langle
T^{\prime}\rangle_{2}=\langle T\rangle_{2}+\langle\gamma\rangle_{2}$ (line
9-10). After communicating with each other, server $S_{1},S_{2}$ can obtain
the final noisy triangle counting result $T^{\prime}$. This algorithm is
denoted by $\mathsf{Perturb}$.

##  IV Theoretical Analysis

###  IV-A Security and Privacy Analysis

####  IV-A1 Security Analysis

We first analyze the security of our proposed Algorithm 4 and Algorithm 5.
Following the simulation-based paradigm [45], we prove the security guarantee
by giving a simulator, ensuring that simulator’s view and each server’s real
view are computationally indistinguishable.

######  Definition 6.

Let $\Pi$ denote the protocol in the semi-honest and non-colluding scenario.
Let $\mathsf{view}_{S_{i}}^{\Pi}$ be the view of the server $S_{i}$. Let
$\mathsf{Sim}_{S_{i}}$ be the view of a simulator. The execution of $\Pi$ is
secure if $\mathsf{view}_{S_{i}}^{\Pi}$ and $\mathsf{Sim}_{S_{i}}$ are
computationally indistinguishable, namely,
$\mathsf{view}_{S_{i}}^{\Pi}\approx\mathsf{Sim}_{S_{i}}$.

######  Theorem 2.

Given the security of additive secret sharing, our Algorithm 4 and Algorithm 5
are secure according to Definition 6.

For multiplication in Algorithm 4 and addition in Algorithm 5 via additive
secret sharing, the random split of secret values guarantees that both the
simulator view and the real view are identical. Each server obtains no
information about user’s sensitive information, where the information leakage
from aggregation result is bounded and qualified via formal DP (refer to
_Privacy Analysis_).

####  IV-A2 Privacy Analysis

Then, we present privacy guarantee of Algorithm 2 and Algorithm 1.

######  Theorem 3.

Algorithm 2 satisfies $\varepsilon_{1}$-Edge LDP.

_Proof of Theorem 3_. Let $A_{i}$ and $A_{i}^{\prime}$ be two neighboring
adjacent lists that differ in one edge, and $d_{i}$ and $d_{i}^{\prime}$ be
their node degrees respectively. Clearly, $|d_{i}-d_{i}^{\prime}|=1$. Let the
noise $x$ and $x^{\prime}$ are two random values drawn from
$Lap(\frac{1}{\varepsilon_{1}})$, the probability of outputting the same noisy
degree $d^{\prime}$ can be bounded by:

$\displaystyle\frac{Pr[d^{\prime}=d_{i}+x]}{Pr[d^{\prime}=d_{i}^{\prime}+x^{\prime}]}=\frac{Pr[x=d^{\prime}-d_{i}]}{Pr[x^{\prime}=d^{\prime}-d_{i}^{\prime}]}$
$\displaystyle=$
$\displaystyle\frac{e^{-\varepsilon_{1}.|d^{\prime}-d_{i}|}}{e^{-\varepsilon_{1}.|d^{\prime}-d_{i}^{\prime}|}}=e^{\varepsilon_{1}.(|d^{\prime}-d_{i}^{\prime}|-|d^{\prime}-d_{i}|)}\leq
e^{\varepsilon_{1}|d_{i}-d_{i}^{\prime}|}=e^{\varepsilon_{1}},$

which proves that $d_{i}$ satisfies $\varepsilon_{1}$-Edge LDP. Then,
according to the post-processing property [6], Algorithm 2 satisfies
$\varepsilon_{1}$-Edge LDP.∎

######  Theorem 4.

Algorithm 1 satisfies ($\varepsilon_{1}+\varepsilon_{2}$)-Edge DDP (Definition
4).

TABLE II: Summary of Theoretical Results. | $\mathsf{CentralLap_{\triangle}}$ | CARGO | $\mathsf{Local2Rounds_{\triangle}}$
---|---|---|---
Server | Trusted | Untrusted | Untrusted
Privacy |  $\varepsilon$-Edge CDP |  ($\varepsilon_{1}+\varepsilon_{2}$)-Edge DDP |  $\varepsilon$-Edge LDP
Utility | $O(\frac{d_{max}^{2}}{\varepsilon^{2}})$ | $O(\frac{d_{max}^{\prime 2}}{\varepsilon_{2}^{2}})$ | $O(\frac{e^{\varepsilon}}{(e^{\varepsilon}-1)^{2}}(d_{max}^{3}n+\frac{e^{\varepsilon}}{\varepsilon^{2}}d_{max}^{2}n))$
Time Complexity | $O(1)$ | $O(n^{3})$ | $O(n^{2}+nd_{max}^{2})$

_Proof of Theorem 4_. Algorithm 1 uses two privacy budgets: $\varepsilon_{1}$
in $\mathsf{Max}$ and $\varepsilon_{2}$ in $\mathsf{Perturb}$. By Theorem 3,
$\mathsf{Max}$ provides $\varepsilon_{1}$-Edge LDP. Below, we analyze the
privacy of $\mathsf{Perturb}$.

Let $G$ and $G^{\prime}$ be two neighboring graphs that differ in one edge,
and $T(G)$ and $T(G^{\prime})$ are their corresponding triangle counts
respectively. The sensitivity of triangle counting is denoted by
$|T(G)-T(G^{\prime})|=\triangle$. Let $\langle T\rangle_{1}$ and $\langle
T\rangle_{2}$ be two secret shares for true triangle count $T$. Then, we have

$T(G)=\langle T\rangle_{1}+\langle T\rangle_{2}$, $T(G^{\prime})=\langle
T^{\prime}\rangle_{1}+\langle T^{\prime}\rangle_{2}$

Let $r=\\{r_{1},...,r_{n}\\}$ and
$r^{\prime}=\\{r_{1}^{\prime},...,r_{n}^{\prime}\\}$ be two sets of
distributed noise from
$Gam_{1}(n,\frac{\triangle}{\varepsilon_{2}})-Gam_{2}(n,\frac{\triangle}{\varepsilon_{2}})$.
Let $x$ and $x^{\prime}$ be two random variables sampled from
$Lap(\frac{\triangle}{\varepsilon_{2}})$ distribution. According to the
infinite divisibility of $Laplace$ distribution (Lemma 1), $x$ and
$x^{\prime}$ can be denoted by:

$x=r_{1}+...+r_{n}$, $x^{\prime}=r_{1}^{\prime}+...+r_{n}^{\prime}$

The probability of outputting the same noisy triangle count $\widetilde{T}$
can be bounded by:

$\displaystyle\frac{Pr[\widetilde{T}=\langle T\rangle_{1}+\langle
T\rangle_{2}+(r_{1}+...+r_{n})]}{Pr[\widetilde{T}=\langle
T^{\prime}\rangle_{1}+\langle
T^{\prime}\rangle_{2}+(r_{1}^{\prime}+...+r_{n}^{\prime})]}$ $\displaystyle=$
$\displaystyle\frac{Pr[\widetilde{T}=T+(r_{1}+...+r_{n})]}{Pr[\widetilde{T}=T^{\prime}+(r_{1}^{\prime}+...+r_{n}^{\prime})]}$
$\displaystyle=$
$\displaystyle\frac{Pr[\widetilde{T}=T(G)+x]}{Pr[\widetilde{T}=T(G^{\prime})+x^{\prime}]}=\frac{Pr[x=\widetilde{T}-T(G)]}{Pr[x^{\prime}=\widetilde{T}-T(G^{\prime})]}$
$\displaystyle=$
$\displaystyle\frac{e^{\frac{-\varepsilon_{2}.|\widetilde{T}-T(G)|}{\triangle}}}{e^{\frac{-\varepsilon_{2}.|\widetilde{T}-T(G^{\prime})|}{\triangle}}}=e^{\frac{\varepsilon_{2}.(|\widetilde{T}-T(G^{\prime})|-|\widetilde{T}-T(G)|)}{\triangle}}$
$\displaystyle\leq$ $\displaystyle
e^{\frac{\varepsilon_{2}|T(G)-T(G^{\prime})|}{\triangle}}=e^{\varepsilon_{2}}$

Thus, $\mathsf{Perturb}$ provides $\varepsilon_{2}$-Edge DDP. As described in
Section II-B, both $\varepsilon$-Edge LDP and $\varepsilon$-Edge DDP protect
one edge with privacy budget $\varepsilon$. Thus, the entire process of
Algorithm 1 provides ($\varepsilon_{1}+\varepsilon_{2}$)-Edge DDP. ∎

###  IV-B Utility Analysis

The utility error of CARGO is mainly from the projection loss in Algorithm 3
and perturbation error in Algorithm 5.

######  Theorem 5 (Projection Loss).

Let $T(G)$ and $\hat{T}(G,d_{max}^{\prime})$ be the triangle count before and
after projection respectively. The projection parameter is set as the noisy
maximum degree $d_{max}^{\prime}$. Then, for any $d_{max}^{\prime}\geq 0$ and
$G$,

$\mathbb{E}[l_{2}^{2}(T(G),\hat{T}(G,d_{max}^{\prime}))]=(T(G)-\hat{T}(G,d_{max}^{\prime}))^{2}$

######  Theorem 6 (Perturbation Error).

Let $T^{\prime}(G,\varepsilon_{2},d_{max}^{\prime})$ and

$\hat{T}(G,d_{max}^{\prime})$ be the triangle count before and after
perturbation, respectively. Then, for any privacy budget $\varepsilon_{2}\geq
0$, noisy maximum degree $d_{max}^{\prime}\geq 0$, and graph $G$,

$\mathbb{E}[l_{2}^{2}(T^{\prime}(G,\varepsilon_{2},d_{max}^{\prime}),\hat{T}(G,d_{max}^{\prime}))]=O(\frac{d_{max}^{\prime
2}}{\varepsilon_{2}^{2}})$

_Proof of Theorem 6_. According to the well-known bias-variance decomposition
[46], the expected $l_{2}$ loss consists of the bias and variance, which can
be written as follows:

$\displaystyle\mathbb{E}[l_{2}^{2}(T^{\prime}(G,\varepsilon_{2},d_{max}^{\prime}),\hat{T}(G,d_{max}^{\prime}))]$
$\displaystyle=$
$\displaystyle(\mathbb{E}[T^{\prime}(G,\varepsilon_{2},d_{max}^{\prime})]-\hat{T}(G,d_{max}^{\prime}))^{2}+\mathbb{V}[T^{\prime}(G,\varepsilon_{2},d_{max}^{\prime})]$

Since the mean of Laplacian noise $Lap(\frac{\triangle}{\varepsilon_{2}})$ is
0, the estimation $T^{\prime}(G,\varepsilon_{2},d_{max}^{\prime})$ is
unbiased. Then, the expected $l_{2}$ loss will be equal to the variance, which
can be formalized as:

$\displaystyle\mathbb{E}[l_{2}^{2}(T^{\prime}(G,\varepsilon_{2},d_{max}^{\prime}),\hat{T}(G,d_{max}^{\prime}))]=\mathbb{V}[T^{\prime}(G,\varepsilon_{2},d_{max}^{\prime})]$
$\displaystyle=$
$\displaystyle\mathbb{V}[Lap(\frac{d_{max}^{\prime}}{\varepsilon_{2}})]=O(\frac{d_{max}^{\prime
2}}{\varepsilon_{2}^{2}})$ ∎

In fact, after empirical analysis, we find that $d_{max}^{\prime}\approx
d_{max}$, as presented in Table V. Specifically, we find that
$l_{2}^{2}(d_{max}^{\prime},d_{max})<0.009d_{max}$, where $d_{max}$ is the
true maximum degree. In addition, $d_{max}^{\prime}\geq d_{max}$ holds in most
cases, which means that there is no deletion of edges during a projection and
$\mathbb{E}[l_{2}^{2}(T(G),\hat{T}(G,d_{max}^{\prime}))]=0$. For a convenient
comparison, we omit the projection loss in theoretical analysis. Thus, our
CARGO attains the expected $l_{2}$ loss of $O(\frac{d_{max}^{\prime
2}}{\varepsilon_{2}^{2}})$, where $\varepsilon_{2}=0.9\varepsilon$ in our
setting.

_Discussion_. It is worth noting that the private maximum degree is the upper
bound of local sensitivity, and there are some pros and cons. On the one hand,
it provides a privacy guarantee for the worst case at the expense of utility.
For instance, if we only consider bipartite graphs, the result of triangle
counting is always 0. The local sensitivity is 0 while the maximum degree can
be very large, which leads to much error. Recently, some works [47, 48]
utilize the smooth sensitivity (SS) and residual sensitivity (RS) for common
graph queries, which can achieve constant noise. Furthermore, we compare the
value of $d_{max}^{\prime}$ with values of SS and RS in Table 1 in [47], as
presented in Table III. We find that $d_{max}^{\prime}$ can be larger than SS
and RS in some graphs, for example, CondMat and HepTh, which means that our
approach can add much more noise than SS and RS. On the other hand, our
$d_{max}^{\prime}$ uses the Laplace distribution and the expected $l_{2}$ loss
(= variance) is finite. However, considering that RS can be regarded as an
instantiation of SS [47], both SS and RS draw noise from a Cauchy
distribution, which has an infinite variance.

###  IV-C Time Complexity

Let $n$ and $d_{max}$ denote the number of users and the maximum degree,
respectively. In CARGO, the time complexity of $\mathsf{Max}$ in Algorithm 2
is $O(n)$. Then, the time complexity of $\mathsf{project}$ in Algorithm 3 is
$O(nd_{max})$ since one user needs to compute degree similarities (Lemma 5)
between her and her all neighboring users. Next, the time complexity of
$\mathsf{Count}$ in Algorithm 4 is $O(n^{3})$. This is because CARGO needs to
traverse all triples to justify if three edges of a triple exist
simultaneously. Finally, the time complexity of $\mathsf{Perturb}$ in
Algorithm 5 is $O(n)$, and the time complexity of secret sharing and
aggregation is also $O(n)$. Thus, the time complexity of our CARGO is
$O(n^{3})$.

Summary of Theoretical Results. Table II summarizes the theoretical results
compared with the state-of-the-art methods, namely,
$\mathsf{CentralLap_{\triangle}}$ [11] and $\mathsf{Local2Rounds_{\triangle}}$
[11]. The results of $\mathsf{CentralLap_{\triangle}}$ and
$\mathsf{Local2Rounds_{\triangle}}$ have been analyzed (refer to Table 2 in
[11]). On the one hand, CARGO can achieve a high-utility triangle count
comparable to $\mathsf{CentralLap_{\triangle}}$, but it does not necessarily
have a trusted server. On the other hand, CARGO outperforms much better than
$\mathsf{Local2Rounds_{\triangle}}$ in terms of utility.

TABLE III: Comparison between SS, RS, and $d_{max}^{\prime}$.

Graph | CondMat | AstroPh | HepPh | HepTh | GrQc
---|---|---|---|---|---
$d_{max}^{\prime}$ | 560 | 1,008 | 984 | 130 | 162
SS | 489 | 1,050 | 1,350 | 102 | 183
RS | 493 | 1,054 | 1,354 | 205 | 222

  * 1

Privacy budget $\varepsilon=1$

##  V Experimental Evaluation

In this section, we conduct experiments to answer the following questions:

  * •

Q1: What is the utility-privacy trade-off of our CARGO compared with the
state-of-the-art CDP-based and LDP-based protocols?

  * •

Q2: How does our similarity-based projection method ($\mathsf{Project}$
algorithm) outperform the existing projection method?

  * •

Q3: How much running time does our CARGO take compared with competitors?

###  V-A Experimental Setting

(a) Facebook

(b) Wiki

(c) HepPh

(d) Enron

Figure 5: The $l_{2}$ loss of triangle counting with $\varepsilon$ varying
from 0.5 to 3.

(a) Facebook

(b) Wiki

(c) HepPh

(d) Enron

Figure 6: The relative error of triangle counting with $\varepsilon$ varying
from 0.5 to 3.

(a) Facebook

(b) Wiki

Figure 7: The $l_{2}$ loss of triangle counting with different $n$.

(a) Facebook

(b) Wiki

Figure 8: The relative error of triangle counting with different $n$.

We use four real-world graph datasets from SNAP [49], and all graphs are
preprocessed into undirected and symmetric graphs. These graphs are from
different domains and have different scales. Table IV presents more details
about each graph $G$, including the number of nodes $|V|$, the number of edges
$|E|$, the true maximum degree $d_{max}$, and domains that graphs belong to.
For each algorithm, we evaluate the $l_{2}$ loss and relative error while
varying the number of users $n$ and privacy budget $\varepsilon$. The default
values of $n$ and $\varepsilon$ are $2\times 10^{3}$ and $2$, respectively.
Usually, triangle counting needs more privacy budget than the other
information (i.e., $d_{max}$) [11, 12]. Thus, we set
$\varepsilon_{1}=0.1\varepsilon$ for publishing noisy maximum degree
$d_{max}^{\prime}$ and $\varepsilon_{2}=0.9\varepsilon$ for perturbing
triangles.

Competitors. To justify the utility-privacy tradeoff of our CARGO system, we
compare it with the state-of-the-art CDP and LDP methods: (1)
$\mathsf{CentralLap_{\triangle}}$[11], an algorithm for triangle counting
using $\mathsf{Laplace}$ mechanism in CDP. (2)
$\mathsf{Local2Rounds_{\triangle}}$[11], a two-round algorithm for counting
triangles in LDP. To verify the performance of our local projection algorithm
(i.e., $\mathsf{Project}$ in Section III-C), we compare it with the existing
projection method in LDP (i.e., $\mathsf{GraphProjection}$ in [11]).

###  V-B Experimental Results

Utility-privacy trade-off. We evaluate Q1 by comparing the accuracy of our
CARGO with that of the aforementioned state-of-the-art LDP and CDP methods
when the privacy budget $\varepsilon$ varies from 0.5 to 3. We also evaluate
the accuracy of our $\mathsf{Max}$ algorithm in Section III-C that privately
estimates the noisy maximum degree $d_{max}^{\prime}$. As shown in Table V,
$d_{max}^{\prime}$ approaches the true maximum degree $d_{max}$ in Table IV.
For each graph, the average of relative error between $d_{max}$ and
$d_{max}^{\prime}$ is less than 1%. Thus, we allow an additional round to
estimate $d_{max}^{\prime}$ in our experiments.

Fig. 5 and Fig. 6 present that CARGO significantly outperforms
$\mathsf{Local2Rounds_{\triangle}}$ in all cases. For example, Fig. 5(a) shows
that for CARGO, $\varepsilon=3$ results in $l_{2}$ loss of 1.09$\times 10^{5}$
as compared to an error of 3.33$\times 10^{8}$ achieved by
$\mathsf{Local2Rounds_{\triangle}}$. Fig. 5(c) illustrates that for
$\varepsilon=3$, CARGO owns a $l_{2}$ loss of 82 while
$\mathsf{Local2Rounds_{\triangle}}$ has an error of 1.22$\times 10^{6}$.
Similarly, in Fig. 6(a), CARGO gives a relative error of only 2.11$\times
10^{-3}$ when $\varepsilon=3$. In contrast,
$\mathsf{Local2Rounds_{\triangle}}$ has a relative error of 0.48. Fig. 6(c)
shows that $\mathsf{Local2Rounds_{\triangle}}$ has a relative error of 28.6
while CARGO only has an error of 3.37$\times 10^{-2}$ for $\varepsilon=3$.
Thus, CARGO improves the $\mathsf{Local2Rounds_{\triangle}}$ significantly.

Another observation is that the error of CARGO is around $1\times\sim 2\times$
larger than that of $\mathsf{CentralLap_{\triangle}}$ for most of cases. With
the increase of $\varepsilon$, the error gap between CARGO and
$\mathsf{CentralLap_{\triangle}}$ roughly decreases. For example, in Fig.
6(a), CARGO has a relative error of 2.29$\times 10^{-2}$ as
$\mathsf{CentralLap_{\triangle}}$ has an error of 8.10$\times 10^{-3}$ when
$\varepsilon=0.5$. Similarly, when $\varepsilon=3$, Fig. 6(a) also shows that
the relative error of CARGO is 2.11$\times 10^{-3}$ when
$\mathsf{CentralLap_{\triangle}}$ owns a relative error of 1.35$\times
10^{-3}$. This is intuitive because an additional round for privately
estimating $d_{max}$ ($\mathsf{Max}$ algorithm) leads to a little error (as
shown in Table V), influencing the overall utility. On the other hand,
increasing $\varepsilon$ improves the accuracy of $\mathsf{Max}$. Therefore,
the error of CARGO is not significantly larger than that of
$\mathsf{CentralLap_{\triangle}}$.

Fig. 8 and Fig. 8 show that CARGO outperforms
$\mathsf{Local2Rounds_{\triangle}}$ and achieves the high accuracy comparable
to $\mathsf{CentralLap_{\triangle}}$ while varying $n$ ($\varepsilon=2$).
Here, we just present the results of two graphs due to the limited space. To
be specific, in Fig. 7(a), the $l_{2}$ loss of CARGO is 9.68$\times 10^{5}$
when $n=4000$. In contrast, $\mathsf{Local2Rounds_{\triangle}}$ owns an
$l_{2}$ loss of 6.8 $\times 10^{10}$. Furthermore, in Fig. 8(b), CARGO has a
relative error of 6.59$\times 10^{-3}$ when $\mathsf{CentralLap_{\triangle}}$
has an error of 3.64$\times 10^{-3}$ for $n=4000$. Therefore, CARGO
significantly outperforms $\mathsf{Local2Rounds_{\triangle}}$ and performs
similarly to $\mathsf{CentralLap_{\triangle}}$.

Local graph projection. Next, we evaluate Q2 by performing a comparative
analysis between our local projection method ($\mathsf{Project}$) and the
existing projection method in local settings ($\mathsf{GraphProjection}$). We
set projection parameter $\theta$ from 10 to 1000, and compute the projection
loss by comparing triangle counts before and after projection. Fig. 9 and Fig.
10 show that $\mathsf{Project}$ owns better utility than the baseline
$\mathsf{GraphProjection}$ in all cases. On the other hand, when $\theta$
increases, the projection loss for both of them decreases and the improvement
of $\mathsf{Project}$ becomes more significant. For example, in Fig. 9(a), the
$l_{2}$ loss of $\mathsf{GraphProjection}$ is 1.01$\times$ larger than that of
$\mathsf{Project}$ when $\theta=10$; In contrast, for $\theta=1000$, the
$l_{2}$ loss of $\mathsf{Project}$ is at least 8$\times$ less than that of
$\mathsf{GraphProjection}$. This is roughly consistent with our theoretical
analysis in Section III-C. Namely, randomly deleting edges in
$\mathsf{GraphProjection}$ is likely to remove some key edges that involve in
many triangles, losing many triangles in a graph.

TABLE IV: details of graph datasets. Graph | $|V|$ | $|E|$ | $d_{max}$ | Domain
---|---|---|---|---
Facebook | 4,039 | 88,234 | 1,045 | social network
Wiki | 7,115 | 103,689 | 1,167 | vote network
HepPh | 12,008 | 118,521 | 982 | citation network
Enron | 36,692 | 183,831 | 2,766 | communication network
TABLE V: Noisy maximum degrees under various $\varepsilon$. Graph $\varepsilon$ | 0.5 | 1 | 1.5 | 2 | 2.5 | 3
---|---|---|---|---|---|---
Facebook | 1079 | 1063 | 1047 | 1037 | 1052 | 1047
Wiki | 1153 | 1166 | 1173 | 1213 | 1155 | 1167
HepPh | 967 | 1013 | 975 | 983 | 979 | 981
Enron | 2834 | 2764 | 2754 | 2777 | 2767 | 2762

Running time. Finally, we evaluate Q3 by testing the performance of CARGO and
competitors while changing $n$. Due to limited space, we only present the
results of two graphs. Fig. 12 and Fig. 12 show the execution time over
Facebook and Wiki, respectively. We can observe that the time cost of all
methods grows with graph size $n$ increases, which is consistent with our
theoretical analysis in Section IV. The running time of
$\mathsf{Local2Rounds_{\triangle}}$ is approximately 2$\times$ higher than
that of $\mathsf{CentralLap_{\triangle}}$. This is because
$\mathsf{Local2Rounds_{\triangle}}$ needs an additional round for collecting a
noisy global graph. Another important observation is that CARGO needs more
time overhead than the other two methods. For example, in Fig. 12, CARGO takes
the time of 485s while $\mathsf{Local2Rounds_{\triangle}}$ takes 0.235s and
$\mathsf{CentralLap_{\triangle}}$ only takes 0.105s. After further evaluation,
we find that most of time overhead in CARGO is from the computation of secure
triangle counting, namely, $\mathsf{Count}$ in Algorithm 4. As shown in Fig.
12, the execution time of $\mathsf{Count}$ accounts for at least 90% of
overall running time. This is because CARGO needs to traverse all triples and
the time complexity of triangle counting is up to $O(n^{3})$.

Summary of Experimental Results. In summary, our answers to three questions at
the start of Section V are as follows. Q1: Our CARGO outperforms significantly
than $\mathsf{Local2Rounds_{\triangle}}$ and achieves comparative accuracy to
$\mathsf{CentralLap_{\triangle}}$ without a trusted server. Q2: Our
$\mathsf{Project}$ algorithm significantly reduces the projection loss
compared with the existing $\mathsf{GraphProjection}$. Q3: The running time of
CARGO is higher than that of other methods and most of computation overhead is
from $\mathsf{Count}$.

(a) Facebook

(b) Wiki

(c) HepPh

(d) Enron

Figure 9: The $l_{2}$ loss of projection loss with various parameters.

(a) Facebook

(b) Wiki

(c) HepPh

(d) Enron

Figure 10: The relative error of projection loss with various parameters.

Figure 11: Running time on Facebook.

Figure 12: Running time on Wiki.

##  VI Related Works

###  VI-A Triangle Counting in DP

Differentially private triangle counting has been widely studied, and previous
works are mainly based on either central DP (CDP) or local DP (LDP).

Triangle Counting in CDP. Existing works related to triangle counting in the
central model mainly focus on how to reduce the global sensitivity. Ding et
al. [8] propose novel projection methods, namely, two edge-deletion strategies
(DL and DS) for triangle counts distributions (histogram of triangle counts
and cumulative histogram of triangle counts) while satisfying Node DP. Karwa
et al. [9] give a differentially private algorithm for releasing the triangle
counts based on the higher-order local sensitivity, which adds less noise than
methods with global sensitivity. Kasiviswanathan et al. [10] develop
algorithms for private graph analysis under Node DP. They design a projection
operator that projects the input graph into a bounded-degree (low-degree)
graph, resulting in a lower sensitivity. However, these works assume that
there is a trusted server that owns the entire graph data. This,
unfortunately, may not be practical in many applications due to the risk of
privacy leaks [50].

Triangle Counting in LDP. Triangle counting in LDP has recently attracted much
attention. The main challenge is from the complex inter-dependencies involving
multiple people. For example, each user cannot see edges between other users.
Imola et al. [11] propose a two-round interaction for triangle counts to
handle the above challenge. However, local randomization aggregates many
errors and two-round interaction brings additional communication overhead. Sun
et al. [12] assume that each user has an extended view, and thus each user can
see the third edges between others. But this assumption may not hold in many
graphs, and we make a minimal assumption where each user only knows her
friends. Also, locally added noise in this work influences the utility
significantly.

In a nutshell, there is an apparent tradeoff between in CDP and in LDP in
terms of privacy and utility while counting triangles.

###  VI-B Crypto-assisted DP

The approach of using cryptographic tools to enhance the utility of
differential privacy (we call it as crypto-assistend DP) has been studied in
the literature[15, 18, 19, 20, 16, 17, 22, 21]. He et al. [15] compose
differential privacy and two-party computation for private record linkage
while ensuring three desiderata: correctness, privacy, and efficiency. Bohler
et al. proposed Crypt$\varepsilon$ [16] is a system and a programming
framework for supporting a rich class of state-of-the-art DP programs, and it
achieves the accuracy of CDP without a trusted server. Honeycrisp [17]
combines cryptographic techniques and differential privacy for answering
periodic queries, which can sustainably run queries like the one from Apple’s
deployment while protecting user privacy in the long run. Some works such as
[18, 19, 20, 21] combine cryptography and differential privacy for federated
learning, reducing the injected noise without sacrificing privacy. Fu et al.
[22] proposes a crypto-assisted differentially private framework for
hierarchical count histograms under untrusted servers. These protocol,
therefore, achieve nearly the same accuracy as CDP models with untrusted
servers.

Although the crypto-assisted DP model has been applied to tabular data [15,
16, 17, 22] and gradients in federated learning [18, 19, 20, 21],
characteristics of graph data, such as high-dimensional and inter-correlated,
lead to more challenges as discussed in Section I. To our knowledge, our work
is the first work for triangle counting using crypto-assisted DP model.

##  VII Conclusions

To conclude, we propose the first crypto-assisted differentially private graph
analysis framework, CARGO, which achieves high-utility triangle counting
comparable to CDP-based models but without requiring a trusted server like
LDP-based models. Through theoretical and experimental analysis, we verify the
privacy and utility achieved by our framework.

## Acknowledgment

This work was supported by JST SPRING (No. JPMJSP2110), JST CREST (No.
JPMJCR21M2), JSPS KAKENHI (No. JP22H00521, JP22H03595, JP21K19767), and
JST/NSF Joint Research SICORP (No. JPMJSC2107). Jinfei Liu is the
corresponding author.

## References

  * [1] C. Seshadhri and S. Tirthapura, “Scalable subgraph counting: the methods behind the madness,” in _Companion Proceedings of The 2019 World Wide Web Conference_ , 2019, pp. 1317–1318.
  * [2] M. E. Newman, “Random graphs with clustering,” _Physical review letters_ , vol. 103, no. 5, p. 058701, 2009.
  * [3] T. Schank and D. Wagner, “Approximating clustering coefficient and transitivity.” _Journal of Graph Algorithms and Applications_ , vol. 9, no. 2, pp. 265–275, 2005.
  * [4] T. GOLDSMITH, “Assessing structural similarity of graphs,” _Pathfinder Associative Networks: Studies in Knowledge Organization_ , pp. 75–87, 1990.
  * [5] C.-H. Tai, P. S. Yu, D.-N. Yang, and M.-S. Chen, “Privacy-preserving social network publication against friendship attacks,” in _Proceedings of the 17th ACM SIGKDD international conference on Knowledge discovery and data mining_ , 2011, pp. 1262–1270.
  * [6] C. Dwork, A. Roth _et al._ , “The algorithmic foundations of differential privacy,” _Foundations and Trends® in Theoretical Computer Science_ , vol. 9, no. 3–4, pp. 211–407, 2014.
  * [7] N. Li, M. Lyu, D. Su, and W. Yang, “Differential privacy: From theory to practice,” _Synthesis Lectures on Information Security, Privacy, & Trust_, vol. 8, no. 4, pp. 1–138, 2016.
  * [8] X. Ding, S. Sheng, H. Zhou, X. Zhang, Z. Bao, P. Zhou, and H. Jin, “Differentially private triangle counting in large graphs,” _IEEE Transactions on Knowledge and Data Engineering_ , vol. 34, no. 11, pp. 5278–5292, 2021.
  * [9] V. Karwa, S. Raskhodnikova, A. Smith, and G. Yaroslavtsev, “Private analysis of graph structure,” _Proceedings of the VLDB Endowment_ , vol. 4, no. 11, pp. 1146–1157, 2011.
  * [10] S. P. Kasiviswanathan, K. Nissim, S. Raskhodnikova, and A. Smith, “Analyzing graphs with node differential privacy,” in _Theory of Cryptography: 10th Theory of Cryptography Conference, TCC 2013, Tokyo, Japan, March 3-6, 2013. Proceedings_. Springer, 2013, pp. 457–476.
  * [11] J. Imola, T. Murakami, and K. Chaudhuri, “Locally differentially private analysis of graph statistics.” in _USENIX Security Symposium_ , 2021, pp. 983–1000.
  * [12] H. Sun, X. Xiao, I. Khalil, Y. Yang, Z. Qin, H. Wang, and T. Yu, “Analyzing subgraph statistics from extended local views with decentralized differential privacy,” in _Proceedings of the 2019 ACM SIGSAC Conference on Computer and Communications Security_ , 2019, pp. 703–717.
  * [13] J. Imola, T. Murakami, and K. Chaudhuri, “Communication-efficient triangle counting under local differential privacy,” in _31st USENIX Security Symposium (USENIX Security 22)_ , 2022, pp. 537–554.
  * [14] Q. Ye, H. Hu, M. H. Au, X. Meng, and X. Xiao, “Lf-gdpr: A framework for estimating graph metrics with local differential privacy,” _IEEE Transactions on Knowledge and Data Engineering_ , vol. 34, no. 10, pp. 4905–4920, 2020.
  * [15] X. He, A. Machanavajjhala, C. Flynn, and D. Srivastava, “Composing differential privacy and secure computation: A case study on scaling private record linkage,” in _Proceedings of the 2017 ACM SIGSAC Conference on Computer and Communications Security_ , 2017, pp. 1389–1406.
  * [16] A. Roy Chowdhury, C. Wang, X. He, A. Machanavajjhala, and S. Jha, “Crypt$\varepsilon$: Crypto-assisted differential privacy on untrusted servers,” in _Proceedings of the 2020 ACM SIGMOD International Conference on Management of Data_ , 2020, pp. 603–619.
  * [17] E. Roth, D. Noble, B. H. Falk, and A. Haeberlen, “Honeycrisp: large-scale differentially private aggregation without a trusted core,” in _Proceedings of the 27th ACM Symposium on Operating Systems Principles_ , 2019, pp. 196–210.
  * [18] X. Gu, M. Li, and L. Xiong, “Precad: Privacy-preserving and robust federated learning via crypto-aided differential privacy,” _arXiv preprint arXiv:2110.11578_ , 2021.
  * [19] T. Stevens, C. Skalka, C. Vincent, J. Ring, S. Clark, and J. Near, “Efficient differentially private secure aggregation for federated learning via hardness of learning with errors,” in _31st USENIX Security Symposium (USENIX Security 22)_ , 2022, pp. 1379–1395.
  * [20] S. Truex, N. Baracaldo, A. Anwar, T. Steinke, H. Ludwig, R. Zhang, and Y. Zhou, “A hybrid approach to privacy-preserving federated learning,” in _Proceedings of the 12th ACM workshop on artificial intelligence and security_ , 2019, pp. 1–11.
  * [21] L. Sun and L. Lyu, “Federated model distillation with noise-free differential privacy,” in _Proceedings of the Thirtieth International Joint Conference on Artificial Intelligence, IJCAI_ , 2021, pp. 1563–1570.
  * [22] C. Fu, H. Li, J. Lou, and J. Cui, “Dp-horus: Differentially private hierarchical count histograms under untrusted server,” in _Proceedings of the 31st ACM International Conference on Information & Knowledge Management_, 2022, pp. 530–539.
  * [23] W.-Y. Day, N. Li, and M. Lyu, “Publishing graph degree distribution with node differential privacy,” in _Proceedings of the 2016 International Conference on Management of Data_ , 2016, pp. 123–138.
  * [24] N. Durak, A. Pinar, T. G. Kolda, and C. Seshadhri, “Degree relations of triangles in real-world networks and graph models,” in _Proceedings of the 21st ACM international conference on Information and knowledge management_ , 2012, pp. 1712–1716.
  * [25] A. Shamir, “How to share a secret,” _Communications of the ACM_ , vol. 22, no. 11, pp. 612–613, 1979.
  * [26] E. Shi, H. Chan, E. Rieffel, R. Chow, and D. Song, “Privacy-preserving aggregation of time-series data,” in _Annual Network & Distributed System Security Symposium (NDSS)_. Internet Society., 2011.
  * [27] G. Ács and C. Castelluccia, “I have a dream!(differentially private smart metering).” in _Information hiding_ , vol. 6958. Springer, 2011, pp. 118–132.
  * [28] S. Goryczka and L. Xiong, “A comprehensive comparison of multiparty secure additions with differential privacy,” _IEEE transactions on dependable and secure computing_ , vol. 14, no. 5, pp. 463–477, 2015.
  * [29] A. Patra, T. Schneider, A. Suresh, and H. Yalame, “Aby2. 0: Improved mixed-protocol secure two-party computation.” in _USENIX Security Symposium_ , 2021, pp. 2165–2182.
  * [30] D. Rathee, M. Rathee, N. Kumar, N. Chandran, D. Gupta, A. Rastogi, and R. Sharma, “Cryptflow2: Practical 2-party secure inference,” in _Proceedings of the 2020 ACM SIGSAC Conference on Computer and Communications Security_ , 2020, pp. 325–342.
  * [31] T. Murakami and Y. Kawamoto, “Utility-optimized local differential privacy mechanisms for distribution estimation,” in _28th USENIX Security Symposium (USENIX Security 19)_ , 2019, pp. 1877–1894.
  * [32] T. Wang, J. Blocki, N. Li, and S. Jha, “Locally differentially private protocols for frequency estimation,” in _26th USENIX Security Symposium (USENIX Security 17)_ , 2017, pp. 729–745.
  * [33] R. Chen, G. Acs, and C. Castelluccia, “Differentially private sequential data publication via variable-length n-grams,” in _Proceedings of the 2012 ACM conference on Computer and communications security_ , 2012, pp. 638–649.
  * [34] V. Bindschaedler and R. Shokri, “Synthesizing plausible privacy-preserving location traces,” in _2016 IEEE Symposium on Security and Privacy (SP)_. IEEE, 2016, pp. 546–563.
  * [35] M. Hay, C. Li, G. Miklau, and D. Jensen, “Accurate estimation of the degree distribution of private networks,” in _2009 Ninth IEEE International Conference on Data Mining_. IEEE, 2009, pp. 169–178.
  * [36] S. Raskhodnikova and A. Smith, “Differentially private analysis of graphs,” _Encyclopedia of Algorithms_ , 2016.
  * [37] Z. Qin, T. Yu, Y. Yang, I. Khalil, X. Xiao, and K. Ren, “Generating synthetic decentralized social graphs with local differential privacy,” in _Proceedings of the 2017 ACM SIGSAC Conference on Computer and Communications Security_ , 2017, pp. 425–438.
  * [38] P. Mohassel and Y. Zhang, “Secureml: A system for scalable privacy-preserving machine learning,” in _2017 IEEE symposium on security and privacy (SP)_. IEEE, 2017, pp. 19–38.
  * [39] M. S. Riazi, C. Weinert, O. Tkachenko, E. M. Songhori, T. Schneider, and F. Koushanfar, “Chameleon: A hybrid secure computation framework for machine learning applications,” in _Proceedings of the 2018 on Asia conference on computer and communications security_ , 2018, pp. 707–721.
  * [40] S. Zheng, Y. Cao, and M. Yoshikawa, “Secure shapley value for cross-silo federated learning,” _Proceedings of the VLDB Endowment_ , vol. 16, no. 7, pp. 1657–1670, 2023.
  * [41] S. Liu, Y. Cao, T. Murakami, and M. Yoshikawa, “A crypto-assisted approach for publishing graph statistics with node local differential privacy,” in _2022 IEEE International Conference on Big Data (Big Data)_ , 2022, pp. 5765–5774.
  * [42] M. O. Rabin, “How to exchange secrets with oblivious transfer,” _Cryptology ePrint Archive_ , 2005.
  * [43] J. Kilian, “Founding crytpography on oblivious transfer,” in _Proceedings of the twentieth annual ACM symposium on Theory of computing_ , 1988, pp. 20–31.
  * [44] S. Kotz, T. Kozubowski, and K. Podgórski, _The Laplace distribution and generalizations: a revisit with applications to communications, economics, engineering, and finance_. Springer Science & Business Media, 2001, no. 183.
  * [45] Y. Lindell, “How to simulate it–a tutorial on the simulation proof technique,” _Tutorials on the Foundations of Cryptography: Dedicated to Oded Goldreich_ , pp. 277–346, 2017.
  * [46] K. P. Murphy, _Machine learning: a probabilistic perspective_. MIT press, 2012.
  * [47] W. Dong and K. Yi, “A nearly instance-optimal differentially private mechanism for conjunctive queries,” in _Proceedings of the 41st ACM SIGMOD-SIGACT-SIGAI Symposium on Principles of Database Systems_ , 2022, pp. 213–225.
  * [48] W. Dong and K. Yi, “Residual sensitivity for differentially private multi-way joins,” in _SIGMOD/PODS’21: Proceedings of the 2021 International Conference on Management of Data_ , 2021.
  * [49] J. Leskovec and A. Krevl, “SNAP Datasets: Stanford large network dataset collection,” http://snap.stanford.edu/data, Jun. 2014.
  * [50] M. Yang, L. Lyu, J. Zhao, T. Zhu, and K.-Y. Lam, “Local differential privacy and its applications: A comprehensive survey,” _arXiv preprint arXiv:2008.03686_ , 2020.