#  Privacy-Preserving Data Deduplication for Enhancing Federated Learning of
Language Models

Aydin Abadi1 1Equal contribution. Listing order is alphabetical. Newcastle
University
<EMAIL_ADDRESS>Vishnu Asutosh Dasu1  Pennsylvania State University
<EMAIL_ADDRESS>Sumanta Sarkar1  University of Warwick
<EMAIL_ADDRESS>
###### Abstract

Deduplication is a vital preprocessing step that enhances machine learning
model performance and saves training time and energy. However, enhancing
federated learning through deduplication poses challenges, especially
regarding scalability and potential privacy violations if deduplication
involves sharing all clients' data. In this paper, we address the problem of
deduplication in a federated setup by introducing a pioneering protocol,
Efficient Privacy-Preserving Multi-Party Deduplication (EP-MPD). It
efficiently removes duplicates from multiple clients' datasets without
compromising data privacy. EP-MPD is constructed in a modular fashion,
utilizing two novel variants of the Private Set Intersection protocol. Our
extensive experiments demonstrate the significant benefits of deduplication in
federated learning of large language models. For instance, we observe up to
19.61% improvement in perplexity and up to 27.95% reduction in running time.
EP-MPD effectively balances privacy and performance in federated learning,
making it a valuable solution for large-scale applications.

##  I Introduction

The application of machine learning (ML) has experienced rapid growth,
becoming widely embraced by businesses due to its various benefits. As ML
relies heavily on data, there is an inherent risk of privacy breaches
associated with this process. Federated learning (FL) is one of the main steps
towards privacy-preserving ML that allows training across multiple
decentralized devices without exchanging data. In FL, devices compute local
models based on their data and then share the local model updates with a
central server. This server aggregates the updates to derive a global model
that encapsulates the features of all the local data held by the individual
devices [38].

The quality of the training data significantly influences the accuracy of an
ML model. Data generated from real-world applications often lacks
organization, leading to issues such as missing values, typos, format
mismatches, outliers, or duplicated entries within the raw dataset. To ensure
meaningful learning, the collected data must undergo a thorough data cleaning
process [23]. Duplicated sequences are prevalent in text datasets. They can
adversely affect the training process of Language Models (LMs). Lee et al.
[31] investigated the Colossal Clean Crawled Corpus (C4) [44] dataset. They
discovered a 61-word sequence within C4 that was repeated 61,036 times
verbatim in the training dataset and 61 times in the validation set. As a
result, the trained model generalized poorly on the dataset, and over $1\%$ of
the unprompted model outputs were memorized and copied verbatim from the
training dataset. Upon deduplicating the dataset, they reduced memorization by
up to $10\times$ and, in certain cases, even improved perplexity by up to
$10\%$.

Additionally, memorization negatively affects the privacy and fairness of LMs
[12]. Memorization makes language models vulnerable to membership inference
attacks [48, 37], data extraction attacks [39, 13], and can lead to copyright
violations as LMs can regurgitate training data sequences from copyrighted
sources [28]. Carlini et al. [12] conclude that bigger LMs memorize more and
more duplicates increase memorization. Kandpal et al. [27] show that the
success of most privacy attacks on LMs is largely due to the duplication in
the training datasets. Furthermore, in the FL setting, malicious clients can
exploit the memorization of LMs to extract sensitive information from honest
clients' datasets [46]. Therefore, we must adopt data-cleaning practices to
improve model utility and reduce the risks of privacy attacks.

While deduplication can improve model performance and reduce memorization, it
also enhances training efficiency in various aspects [31]. Removing duplicates
reduces GPU time and minimizes training costs in terms of time, money, and
carbon footprint. This streamlined process optimizes resource utilization and
contributes to more sustainable ML practices [7, 47, 42]. Sustainable
development is a global priority, and aligning ML practices with this theme is
crucial.

Based on the discussions thus far, it is evident that the deduplication of
training data offers numerous benefits. Several real-world applications
involve training with FL such as healthcare [3], smart city [25], and edge
computing [51]. Some of these applications pose a risk of duplicates in the
local training data across multiple devices. For example, Google Keyboard
suggestions from a user's text query rely on FL [22]. Local models are trained
in situ on Android phones with user data. In this setting, many text queries
typed by the users across multiple phones are the same.

Therefore, for a FL process to be efficient and effective, participating
devices must perform deduplication. When a data owner solely intends to remove
duplicates from their dataset, the privacy risk is minimal since the data is
entirely under the owner's control. In the context of FL, the scenario shifts
significantly when deduplication is introduced. Multiple devices participating
in FL may possess overlapping data, even after deduplicating their datasets.
If they aim to deduplicate the combined dataset, one approach could involve
sharing their raw data with each other and checking for intersections.
However, this approach compromises privacy.

Hence, there is a necessity for privacy-preserving deduplication in FL, where
participating devices would collaboratively deduplicate the combined datasets
in a privacy-preserving fashion. This paper demonstrates how deduplication can
be executed in FL without compromising the privacy of the data belonging to
the individual devices.

###  I-A Overview of Privacy-Preserving Deduplication in FL

Consider nodes $D_{\scriptscriptstyle 1},\ldots,D_{\scriptscriptstyle n}$ are
involved in FL, where each $D_{\scriptscriptstyle i}$ has a dataset
$S_{\scriptscriptstyle i}$. Effectively, the training in FL is conducted on
the union of these datasets, i.e., $\bigcup\limits_{\scriptscriptstyle
i=1}^{\scriptscriptstyle n}S_{\scriptscriptstyle i}$. If intersections exist
among the datasets, FL will incorporate duplicates, leading to the drawbacks
discussed earlier.

Consider nodes $D_{\scriptscriptstyle 1}$ and $D_{\scriptscriptstyle 2}$, each
with datasets $S_{\scriptscriptstyle 1}$ and $S_{\scriptscriptstyle 2}$,
respectively implying that FL training occurs on $S_{\scriptscriptstyle 1}\cup
S_{\scriptscriptstyle 2}$. If the intersection $S_{\scriptscriptstyle 1}\cap
S_{\scriptscriptstyle 2}$ is nonempty, training individually on
$S_{\scriptscriptstyle 1}$ and $S_{\scriptscriptstyle 2}$ would mean training
twice on the duplicate $S_{\scriptscriptstyle 1}\cap S_{\scriptscriptstyle
2}$. Thus, one of $D_{\scriptscriptstyle 1}$ and $D_{\scriptscriptstyle 2}$
should remove the duplicate $S_{\scriptscriptstyle 1}\cap
S_{\scriptscriptstyle 2}$. This should be done without harming each other's
data privacy. Our solution applies private set intersection (PSI) which
securely finds the intersection of $S_{\scriptscriptstyle 1}$ and
$S_{\scriptscriptstyle 2}$ without revealing any other elements. Once
$D_{\scriptscriptstyle 1}$ and $D_{\scriptscriptstyle 2}$ learn
$S_{\scriptscriptstyle 1}\cap S_{\scriptscriptstyle 2}$ through PSI,
$D_{\scriptscriptstyle 1}$ will train on $S_{\scriptscriptstyle
1}^{\prime}=S_{\scriptscriptstyle 1}\setminus S_{\scriptscriptstyle 1}\cap
S_{\scriptscriptstyle 2}$ and $D_{\scriptscriptstyle 2}$ will train on
$S_{\scriptscriptstyle 2}$. According to set theory, it holds that
$S_{\scriptscriptstyle 1}^{\prime}\cup S_{\scriptscriptstyle
2}=S_{\scriptscriptstyle 1}\cup S_{\scriptscriptstyle 2}$. Hence, the
resulting FL model remains as intended, while the training process is devoid
of duplicates, avoiding the associated drawbacks. The scenario with two nodes
seems straightforward. However, when more than two nodes participate, it
becomes complicated. We now consider $n$ nodes $D_{\scriptscriptstyle
1},\ldots,D_{\scriptscriptstyle n}$, where each node $D_{\scriptscriptstyle
i}$ has a set $S_{\scriptscriptstyle i}$, $\forall i,1\leq i\leq n$, and
$n>2$.

Following the approach used in the two-node case, one might be tempted to (i)
apply multi-party PSI to $n$ nodes, (ii) find their intersection
$I_{\scriptscriptstyle n}$, and (iii) let node $D_{\scriptscriptstyle 1}$
train on $S_{\scriptscriptstyle 1}^{\prime}=S_{\scriptscriptstyle 1}\setminus
I_{\scriptscriptstyle n}$, and rest of the nodes train on their own dataset
$S_{\scriptscriptstyle i}$. This method removes the duplicates that exist
across all the nodes. However, this does not detect and remove the duplicates
that exist among a subset of nodes. For instance, if there is a subset of $k$
nodes ($k<n$) with a large intersection $I_{\scriptscriptstyle k}$, then
$I_{\scriptscriptstyle k}$ will remain in the full training dataset
$S_{\scriptscriptstyle 1}^{\prime}\bigcup(\bigcup\limits_{\scriptscriptstyle
i=2}^{\scriptscriptstyle n}S_{\scriptscriptstyle i})$ as duplicates. A generic
multi-party PSI does not help in this case. Therefore, we need to consider
each pair of nodes and remove the duplicates accordingly.

###  I-B Our Contributions

In this paper, our end goal is to develop a scheme such that allows multiple
clients to benefit from deduplication while training on their data in a
federated learning setup. The first requirement is an efficient deduplication
of sets belonging to multiple clients. To address this, we introduce the
notion of _Privacy-Preserving Multi-Party Deduplication_ (P-MPD) in Section
IV. This essentially describes a functionality that takes input datasets
$S_{\scriptscriptstyle 1},\ldots,S_{\scriptscriptstyle m}$ (potentially
containing duplicates) from $m$ clients and outputs the datasets
$S_{\scriptscriptstyle 1}^{\prime},\ldots,S_{\scriptscriptstyle m}^{\prime}$
such that $\bigcup\limits_{\scriptscriptstyle i=1}^{\scriptscriptstyle
m}S_{\scriptscriptstyle i}^{\prime}=\bigcup\limits_{\scriptscriptstyle
i=1}^{\scriptscriptstyle m}S_{i}$, where $S_{\scriptscriptstyle
i}^{\prime}\cap S_{\scriptscriptstyle j}^{\prime}=\emptyset,i\neq j$. We
realize that an efficient construction of P-MPD requires a substantially
improved PSI protocol that supports scalability. This leads us to introduce a
new notion for PSI which we call _Group PSI_ (G-PSI) in Section III. The
functionality of G-PSI takes sets from a group of clients and returns each
client the intersection of their sets with all the other clients' sets. We
provide constructions of _Efficient Group PSI_ (EG-PSI) that efficiently
realizes G-PSI, namely $\text{EG-PSI}^{\scriptscriptstyle(\text{I})}$ and
$\text{EG-PSI}^{\scriptscriptstyle(\text{II})}$ in Figures 1 and 2,
respectively. $\text{EG-PSI}^{\scriptscriptstyle(\text{I})}$ is based on
symmetric key primitives such as pseudorandom permutation, while $\text{EG-
PSI}^{\scriptscriptstyle(\text{II})}$ is developed using an oblivious
pseudorandom function, which is a well-known public key primitive. With the
building block EG-PSI, we build _Efficient Privacy-Preserving Multi-Party
Deduplication_ (EP-MPD) that realizes P-MPD as shown in Figure 4. We prove the
security of EP-MPD, $\text{EG-PSI}^{\scriptscriptstyle(\text{I})}$, and
$\text{EG-PSI}^{\scriptscriptstyle(\text{II})}$ within the simulation-based
paradigm. Our construction of EP-MPD allows for efficient duplicate removal
without compromising clients' data privacy, resulting in an improved model
after running federated learning on the deduplicated datasets, as outlined in
Figure 5.

We perform an extensive experimental evaluation to benchmark EP-MPD and the
effect of the resulting deduplication on FL. The overall running time for
$\text{EP-MPD}^{\scriptscriptstyle(\text{I})}$, which employs $\text{EG-
PSI}^{\scriptscriptstyle(\text{I})}$ (symmetric key primitives based), is much
less than $\text{EP-MPD}^{\scriptscriptstyle(\text{II})}$, which utilizes
$\text{EG-PSI}^{\scriptscriptstyle(\text{II})}$ (public key primitives based).
Overall, clients enjoy relatively less computation time in $\text{EP-
MPD}^{\scriptscriptstyle(\text{II})}$. Our protocols can scale to large
datasets and client counts. For example, when 50 clients have
$2^{\scriptscriptstyle 19}$ data points in their datasets comprising of $30\%$
duplicates, then $\text{EP-MPD}^{\scriptscriptstyle(\text{I})}$ takes 1160
seconds and $\text{EP-MPD}^{\scriptscriptstyle(\text{II})}$ takes 7653
seconds; client running time is 641 and 111 seconds in $\text{EP-
MPD}^{\scriptscriptstyle(\text{I})}$ and $\text{EP-
MPD}^{\scriptscriptstyle(\text{II})}$ respectively. We experiment with 7
datasets, 2 language models, and 10 clients in FL. We achieve an improvement
of up to 19.61% in perplexity and up to 27.95% improvement in GPU training
time.

##  II Preliminaries

###  II-A Notations and Assumptions

We define a wrapper function $\mathtt{Update}(S,\hat{S})\rightarrow S$ which
takes two sets, $S$ and $\hat{S}$. It updates $S$ by removing from it the
elements in set $\hat{S}$ and returns the updated set $S$. In this paper, by
the sum of sets (e.g., $\sum\limits_{\scriptscriptstyle
i=1}^{\scriptscriptstyle n}S_{\scriptscriptstyle i}$) we mean the
concatenation of the sets which may result in a multi-set. We denote an empty
set by $\emptyset$. We denote a size of vector $\vec{v}$ with $|\vec{v}|$. We
assume that the server and all the users have access to secure channels among
them. By the notation, $\mathcal{X}\stackrel{{\scriptstyle
c}}{{\equiv}}\mathcal{Y}$, we mean that the two distributions $\mathcal{X}$
and $\mathcal{Y}$ are computationally indistinguishable.

###  II-B Federated Learning (FL)

The concept of FL was proposed by McMahan et al. [38] as a framework for
training an ML model where the training data are distributed across multiple
devices. In FL, a server orchestrates the training of a global model by
aggregating models locally computed by the clients on their local devices.
Suppose there are $n$ clients, and each client $D_{\scriptscriptstyle i}$ has
a dataset $S_{\scriptscriptstyle i}$. The server has the initial model
$\bm{\theta}$. It sends $\bm{\theta}$ to the clients, and each client performs
gradient descent computation on their local dataset $S_{\scriptscriptstyle i}$
as $J_{i}({S}_{\scriptscriptstyle
i},\bm{\theta})=\frac{1}{d_{\scriptscriptstyle
i}}\sum\limits_{\scriptscriptstyle(\textbf{x},y)\in{S}_{\scriptscriptstyle
i}}C(\bm{\theta},(\textbf{x},y)),$ where $C$ is the cost function and
$d_{\scriptscriptstyle i}=|{S}_{\scriptscriptstyle i}|$. The client
$D_{\scriptscriptstyle i}$ computes the local models as
$\bm{\theta}_{\scriptscriptstyle i}\leftarrow\bm{\theta}-\eta\nabla
J({S}_{\scriptscriptstyle i},\bm{\theta}),$ where $\eta$ is the learning rate.
After receiving the local models from the clients, the server performs an
aggregated averaging on the local models to derive the global model as:

$\Theta=\dfrac{1}{d}\big{(}d_{\scriptscriptstyle
1}\bm{\theta}_{\scriptscriptstyle 1}+\ldots+d_{\scriptscriptstyle
n}\bm{\theta}_{\scriptscriptstyle n}\big{)}$ (1)

where $d=\sum\limits_{\scriptscriptstyle i=1}^{\scriptscriptstyle
n}d_{\scriptscriptstyle i}$ is the total size of the dataset
${S}=\sum\limits_{\scriptscriptstyle i=1}^{\scriptscriptstyle
n}{S}_{\scriptscriptstyle i}$, and $\bm{\theta}_{\scriptscriptstyle i}$ is the
locally trained model on the dataset ${S}_{\scriptscriptstyle i}$. This
computation is repeated until the model converges.

While this framework achieves a basic level of privacy in which each user's
data is not directly sent to the server, it is susceptible to advanced privacy
attacks such as membership inference attacks [48, 37] and data extraction
attacks [13, 46, 18, 4] as the client models $\theta_{\scriptscriptstyle i}$
are aggregated in a non-private fashion on the server side. Some privacy-
preserving FL protocols have attempted to mitigate these attacks by securely
aggregating the client models. These protocols rely on cryptographic
techniques like homomorphic encryption [14, 15], functional encryption [52],
or secure aggregation [5, 9]. Additionally, differentially private training
techniques [2] can be used to ensure differential privacy guarantees on the
global model $\Theta$. We emphasize that in this paper, our proposed schemes
are agnostic to the type of FL mechanism used.

###  II-C Causal Language Modeling (CLM)

Causal Language Modeling (CLM) is a natural language processing task where the
goal of the language model is to predict the next word or token given a
sequence of tokens. The language model autoregressively generates the next
token until a pre-determined sequence length is reached or a special STOP
token is generated. Given a sequence of $n$ tokens
$\mathbf{Y}=\\{y_{\scriptscriptstyle 1},y_{\scriptscriptstyle
2}\ldots,y_{\scriptscriptstyle n-1},y_{\scriptscriptstyle n}\\}$, the language
model $\Theta$ is trained to learn the following probability distribution:

$P(\mathbf{Y})={\displaystyle\prod_{\scriptscriptstyle
i=1}^{\scriptscriptstyle n}P(y_{\scriptscriptstyle i}|y_{\scriptscriptstyle
1},\ldots,y_{\scriptscriptstyle i-1})}$ (2)

The CLM training objective is to minimize the negative log-likelihood loss
given by:

$\mathcal{L}(\Theta,\mathbf{Y})=-\displaystyle\sum_{\scriptscriptstyle
i=1}^{\scriptscriptstyle n}\log(\Theta(y_{\scriptscriptstyle
i}|y_{\scriptscriptstyle 1},\ldots,y_{\scriptscriptstyle i-1}))$ (3)

After training is complete, the text is autoregressively sampled from the
language model i.e., $\hat{y}_{\scriptscriptstyle
t<n}\sim\Theta(y_{\scriptscriptstyle t}|y_{\scriptscriptstyle
1},\ldots,y_{\scriptscriptstyle t-1})$.

The perplexity metric is commonly used to evaluate the performance of the
language model to determine how well it has learned the probability
distribution in Equation 2. The perplexity $PP$ of a sequence $\mathbf{y}$ is
defined as:

$PP(\mathbf{Y})=\exp\left(-\frac{1}{n}{\displaystyle\sum_{\scriptscriptstyle
i=1}^{\scriptscriptstyle n}\log(\Theta(y_{\scriptscriptstyle
i}|y_{\scriptscriptstyle 1},\ldots,y_{\scriptscriptstyle i-1}))}\right)$ (4)

A lower perplexity score implies that model $\Theta$ has been trained well to
estimate the real-world probability distribution. Informally, a sequence with
a low perplexity score implies that the model is less ``surprised'' by a
sequence of tokens.

###  II-D Security Model

In this paper, we use the simulation-based paradigm of secure multi-party
computation [21] to define and prove the proposed protocol. Since we focus on
the static passive (semi-honest) adversarial model, we will restate the
security definition within this context.

####  II-D1 Two-party Computation

A two-party protocol $\Gamma$ is captured by specifying a random process that
maps a pair of input to a pair of outputs (one output for each party). Such
process is referred to as a functionality denoted by
$f:\\{0,1\\}^{\scriptscriptstyle*}\times\\{0,1\\}^{\scriptscriptstyle*}\rightarrow\\{0,1\\}^{\scriptscriptstyle*}\times\\{0,1\\}^{\scriptscriptstyle*}$,
where $f:=(f_{\scriptscriptstyle 1},f_{\scriptscriptstyle 2})$. For every
input pair $(x,y)$, the output pair is a random variable
$(f_{\scriptscriptstyle 1}(x,y),f_{\scriptscriptstyle 2}(x,y))$, such that the
party with input $x$ wishes to obtain $f_{\scriptscriptstyle 1}(x,y)$ while
the party with input $y$ wishes to receive $f_{\scriptscriptstyle 2}(x,y)$.
The above functionality can be easily extended to more than two parties.

####  II-D2 Security in the Presence of Passive Adversaries

In the passive adversarial model, the party corrupted by such an adversary
correctly follows the protocol specification. Nonetheless, the adversary
obtains the internal state of the corrupted party, including the transcript of
all the messages received, and tries to use this to learn information that
should remain private. Loosely speaking, a protocol is secure if whatever can
be computed by a corrupt party in the protocol can be computed using its input
and output only.

In the simulation-based model, it is required that a party’s view in a
protocol's execution can be simulated given only its input and output. This
implies that the parties learn nothing from the protocol's execution.
Formally, in two-party case, party $i$’s view (during the execution of
$\Gamma$) on input pair $(x,y)$ is denoted by
$\mathsf{View}_{\scriptscriptstyle i}^{\scriptscriptstyle\Gamma}(x,y)$ and
equals $(w,r^{\scriptscriptstyle i},m_{\scriptscriptstyle
1}^{\scriptscriptstyle i},...,m_{\scriptscriptstyle t}^{\scriptscriptstyle
i})$, where $w\in\\{x,y\\}$ is the input of $i^{\scriptscriptstyle th}$ party,
$r_{\scriptscriptstyle i}$ is the outcome of this party's internal random coin
tosses, and $m_{\scriptscriptstyle j}^{\scriptscriptstyle i}$ represents the
$j^{\scriptscriptstyle th}$ message this party receives. The output of the
$i^{\scriptscriptstyle th}$ party during the execution of $\Gamma$ on $(x,y)$
is denoted by $\mathsf{Output}_{\scriptscriptstyle
i}^{\scriptscriptstyle\Gamma}(x,y)$ and can be generated from its own view of
the execution.

######  Definition 1.

Let $f$ be the deterministic functionality defined above. Protocol $\Gamma$
securely computes $f$ in the presence of a static passive probabilistic
polynomial-time (PPT) adversary $\mathcal{A}$, if for every $\mathcal{A}$ in
the real model, there exist PPT algorithms $(\mathsf{Sim}_{\scriptscriptstyle
1},\mathsf{Sim}_{\scriptscriptstyle 2})$ such that:

$\\{\mathsf{Sim}_{\scriptscriptstyle 1}(x,f_{\scriptscriptstyle
1}(x,y))\\}_{\scriptscriptstyle x,y}\stackrel{{\scriptstyle
c}}{{\equiv}}\\{\mathsf{View}_{\scriptscriptstyle
1}^{\scriptscriptstyle\mathcal{A},\Gamma}(x,y)\\}_{\scriptscriptstyle x,y}$
$\\{\mathsf{Sim}_{\scriptscriptstyle 2}(y,f_{\scriptscriptstyle
2}(x,y))\\}_{\scriptscriptstyle x,y}\stackrel{{\scriptstyle
c}}{{\equiv}}\\{\mathsf{View}_{\scriptscriptstyle
2}^{\scriptscriptstyle\mathcal{A},\Gamma}(x,y)\\}_{\scriptscriptstyle x,y}$

Definition 1 can be easily extended to $m>2$ parties.

###  II-E Pseudorandom Function and Permutation

Informally, a pseudorandom function $\mathtt{PRF}(.)$ is a deterministic
function that takes a key of length $\lambda$ and an input of length $u$; and
outputs a value of length $v$ indistinguishable from an output of a truly
random function. More formally, a pseudorandom function can be defined as
$\mathtt{PRF}:\\{0,1\\}^{\scriptscriptstyle\lambda}\times\\{0,1\\}^{\scriptscriptstyle
u}\rightarrow\\{0,1\\}^{\scriptscriptstyle v}$, where $\lambda$ is the
security parameter.

The definition of a pseudorandom permutation,
$\mathtt{PRP}:\\{0,1\\}^{\scriptscriptstyle\lambda}\times\\{0,1\\}^{\scriptscriptstyle
u}\rightarrow\\{0,1\\}^{\scriptscriptstyle u}$, is very similar to that of a
pseudorandom function, with a difference; namely, it is required the keyed
function $\mathtt{PRP}(k,\cdot)$ to be indistinguishable from a uniform
permutation, instead of a uniform function. In cryptographic schemes that
involve $\mathtt{PRP}$, sometimes honest parties may be required to compute
the inverse of pseudorandom permutation, i.e.,
$\mathtt{PRP}^{\scriptscriptstyle-1}(k,\cdot)$, as well. In this case, it
would require that $\mathtt{PRP}(k,\cdot)$ be indistinguishable from a uniform
permutation even if the distinguisher is additionally given oracle access to
the inverse of the permutation.

###  II-F Oblivious Pseudorandom Function

An Oblivious Pseudorandom Function (OPRF) is a protocol that involves a client
and a server. OPRF enables the client with input
$x\in\\{0,1\\}^{\scriptscriptstyle u}$, and the server with key
$k\in\\{0,1\\}^{\scriptscriptstyle\lambda}$ to execute an instance of
$\mathtt{PRF}$. Informally, the security of an OPRF asserts that, by the
completion of OPRF, the client only learns the output of $\mathtt{PRF}$ is
evaluated on inputs $k$ and $x$, i.e., $\mathtt{PRF}(k,x)$ while the server
gains no information, e.g., about the input of the client and the output of
$\mathtt{PRF}$.

###  II-G Trusted Execution Environments

Trusted Execution Environment ($\mathcal{TEE}$), also known as a secure
enclave, constitutes a secure processing environment comprising processing,
memory, and storage hardware units [41, 54]. Within this environment, the code
and data residing in them remain isolated from other layers in the software
stack, including the operating system. An ideal $\mathcal{TEE}$ guarantees the
preservation of data integrity and confidentiality. Moreover, $\mathcal{TEE}$
can provide remote attestation capabilities, allowing a party to remotely
verify the execution of an enclave on a genuine $\mathcal{TEE}$ hardware
platform. Given the assumption that the physical CPU remains uncompromised,
enclaves are shielded from attackers with physical access to the machine,
including the memory and system bus.

Side-channel attacks on different deployments of $\mathcal{TEE}$s have been
demonstrated in the literature [49]. These attacks pose a threat as they could
enable attackers to extract secrets from $\mathcal{TEE}$s. Nevertheless,
$\mathcal{TEE}$s technologies have been evolving to address and mitigate side-
channel attacks.

Our security, trust, and system assumptions regarding $\mathcal{TEE}$s are
conservative. Specifically, as detailed in Sections IV-B1 and III-B, our
solution (i) avoids disclosing any plaintext messages or private keys to
$\mathcal{TEE}$ and (ii) does not expect $\mathcal{TEE}$ to maintain an
extensive storage and memory space or possess strong processing resources.
Instead, we establish a formal model and construction under the assumption
that $\mathcal{TEE}$ guarantees execution integrity (and authenticity), and
ensures minimal confidentiality. Specifically, we formally demonstrate that
$\mathcal{TEE}$ at the most only learns the size of the encrypted computation
result (i.e., the intersections' cardinality). In our work, $\mathcal{TEE}$
can be seamlessly substituted with any semi-honest server that does not
collude with other entities.

##  III Group PSI (G-PSI)

###  III-A Formal Definition of G-PSI

In this section, we present the concept of Group PSI (G-PSI). In G-PSI, there
are two groups of clients, $\mathcal{G}_{\scriptscriptstyle 0}$ and
$\mathcal{G}_{\scriptscriptstyle 1}$, where each group contains $m$ clients,
$\mathcal{G}_{\scriptscriptstyle j}:\\{\mathcal{C}_{\scriptscriptstyle
j,1},\ldots,\mathcal{C}_{\scriptscriptstyle j,m}\\}$, $0\leq j\leq 1$. Each
client $\mathcal{C}_{\scriptscriptstyle j,1}$ has a set
${S}_{\scriptscriptstyle j,1}$, such that no pair of clients' sets in the same
group share a common element.

Informally, G-PSI allows every client in one group to (efficiently) find the
intersection that their set has with the set of every client of the other
group, without allowing them to learn anything beyond that about other
clients' set elements. To achieve a high level of computational efficiency in
G-PSI, we will involve a third-party $\mathcal{TP}$ that assists the clients
with computing the intersection. The functionality
${f}_{\scriptscriptstyle\text{G-PSI}}$ that G-PSI computes takes a set
${S}_{\scriptscriptstyle j,i}$ from every client
$\mathcal{C}_{\scriptscriptstyle j,i}$ and no input from $\mathcal{TP}$. It
returns (i) to every client $\mathcal{C}_{\scriptscriptstyle j,i}$ a vector
$\vec{v}_{\scriptscriptstyle j,i}$ which contains the intersection that
$\mathcal{C}_{\scriptscriptstyle j,i}$'s set has with every other client's set
in the other group and (ii) to $\mathcal{TP}$ an empty set $\emptyset$. Hence,
functionality $f_{\scriptscriptstyle\text{G-PSI}}$ can be formally defined as
follows.

$\begin{split}f_{\scriptscriptstyle\text{G-PSI}}\Big{(}(\underbrace{{S}_{\scriptscriptstyle
0,1},\ldots,{S}_{\scriptscriptstyle
0,m}}_{\scriptscriptstyle\mathcal{G}_{\scriptscriptstyle
0}}),(\underbrace{{S}_{\scriptscriptstyle 1,1},\ldots,{S}_{\scriptscriptstyle
1,m}}_{\scriptscriptstyle\mathcal{G}_{\scriptscriptstyle
1}}),\emptyset\Big{)}\rightarrow\\\
\Big{(}(\underbrace{\vec{v}_{\scriptscriptstyle
0,1},\ldots,\vec{v}_{\scriptscriptstyle
0,m}}_{\scriptscriptstyle\mathcal{G}_{\scriptscriptstyle
0}}),(\underbrace{\vec{v}_{\scriptscriptstyle
1,1},\ldots,\vec{v}_{\scriptscriptstyle
1,m}}_{\scriptscriptstyle\mathcal{G}_{\scriptscriptstyle
1}}),\emptyset\Big{)},\end{split}$ (5)

where, $\vec{v}_{\scriptscriptstyle j,i}=\Big{[}[{S}_{\scriptscriptstyle
j,i}\cap{S}_{\scriptscriptstyle 1-j,1}],\ldots,[{S}_{\scriptscriptstyle
j,i}\cap{S}_{\scriptscriptstyle 1-j,m}]\Big{]}$, $0\leq j\leq 1$, and $1\leq
i\leq m$.

In the case where clients of only one of the groups, e.g.,
$\mathcal{G}_{\scriptscriptstyle 0}$, receives the result, then the above
functionality simply returns $\emptyset$ to the clients in the other group,
e.g., ${\vec{v}_{\scriptscriptstyle 1,1}=\ldots=\vec{v}_{\scriptscriptstyle
1,m}}=\emptyset$.

Since $\mathcal{TP}$ performs computation on all clients' encrypted sets,
there is a possibility of leakage to $\mathcal{TP}$. Depending on the protocol
that realizes $f_{\scriptscriptstyle\text{G-PSI}}$ this leakage could contain
different types of information; for instance, it could contain (i) the size of
the intersection of any two clients' sets, or (ii) the size of the
intersection of all clients' sets, or (iii) nothing at all. Often such leakage
is defined by a leakage function $\mathcal{L}$ that takes all parties
(encoded) inputs and returns the amount of leakage.

We assert that a protocol securely realizes
$f_{\scriptscriptstyle\text{G-PSI}}$ if (1) it reveals nothing beyond a
predefined leakage to $\mathcal{TP}$ and (2) whatever can be computed by a
client in the protocol can be obtained from its input and output. This is
formalized under the simulation paradigm. We require a client’s view during an
execution of G-PSI to be simulatable given its input and output. We require
that the view of $\mathcal{TP}$ can be simulated given the leakage.

######  Definition 2 (Security of G-PSI).

Let $\mathcal{G}_{\scriptscriptstyle 0}$ and $\mathcal{G}_{\scriptscriptstyle
1}$ be two groups of clients, where each group contains $m$ clients,
$\mathcal{G}_{\scriptscriptstyle j}:\\{\mathcal{C}_{\scriptscriptstyle
j,1},\ldots,\mathcal{C}_{\scriptscriptstyle j,m}\\}$, $0\leq j\leq 1$. Let
$\mathcal{L}$ denote a leakage function, $f_{\scriptscriptstyle\text{G-PSI}}$
be the functionality defined above (in Relation 5 on page 5),
$S=\\{{S}_{\scriptscriptstyle 0,1},\ldots,$ ${S}_{\scriptscriptstyle
0,m},{S}_{\scriptscriptstyle 1,1},\ldots,{S}_{\scriptscriptstyle 1,m}\\}$, and
${S}_{\scriptscriptstyle j,i}$ represent a set belonging to client
$\mathcal{C}_{\scriptscriptstyle j,i}$. Then, a protocol $\Gamma$ securely
realizes $f_{\scriptscriptstyle\text{G-PSI}}$ in the presence of a static
semi-honest PPT adversary $\mathcal{A}$, if for every $\mathcal{A}$ in the
real model, there exists a PPT adversary (simulator) $\mathsf{Sim}$ in the
ideal model, such that for every $\mathcal{C}_{\scriptscriptstyle
j,i}\in\\{\mathcal{C}_{\scriptscriptstyle
0,1},\ldots,\mathcal{C}_{\scriptscriptstyle
0,m},\mathcal{C}_{\scriptscriptstyle
1,1},\ldots,\mathcal{C}_{\scriptscriptstyle 1,m}\\}$ and $\mathcal{TP}$,
Relations 6 and 7 hold respectively.

$\\{\mathsf{Sim}_{\scriptscriptstyle\mathcal{C}_{\scriptscriptstyle
j,i}}({S}_{\scriptscriptstyle j,i},\vec{v}_{\scriptscriptstyle
j,i})\\}_{\scriptscriptstyle S}\stackrel{{\scriptstyle
c}}{{\equiv}}\\{\mathsf{View}_{\scriptscriptstyle\mathcal{C}_{\scriptscriptstyle
j,i}}^{\scriptscriptstyle\mathcal{A},\Gamma}(S,\emptyset)\\}_{\scriptscriptstyle
S}$ (6)
$\\{\mathsf{Sim}^{\scriptscriptstyle\mathcal{L}}_{\scriptscriptstyle\mathcal{TP}}(\emptyset,\emptyset)\\}_{\scriptscriptstyle
S}\stackrel{{\scriptstyle
c}}{{\equiv}}\\{\mathsf{View}_{\scriptscriptstyle\mathcal{TP}}^{\scriptscriptstyle\mathcal{A},\Gamma}(S,\emptyset)\\}_{\scriptscriptstyle
S}$ (7)

where $\vec{v}_{\scriptscriptstyle j,i}=\Big{[}[{S}_{\scriptscriptstyle
j,i}\cap{S}_{\scriptscriptstyle 1-j,1}],\ldots,[{S}_{\scriptscriptstyle
j,i}\cap{S}_{\scriptscriptstyle 1-j,m}]\Big{]}$, $0\leq j\leq 1$, $1\leq i\leq
m$, and $\mathcal{TP}$'s input is $\emptyset$.

###  III-B Efficient Construction of G-PSI

In this section, we introduce two efficient protocols that realize G-PSI. The
first one, called $\text{EG-PSI}^{\scriptscriptstyle(\text{I})}$, is highly
efficient and based on symmetric key cryptography. The second one, called
$\text{EG-PSI}^{\scriptscriptstyle(\text{II})}$, is based on OPRF (in turn
depends on public key cryptography) and discloses less information to
$\mathcal{TEE}$ than the former does. Thus, these two protocols trade-off
between performance and leakage amount.

####  III-B1 $\text{EG-PSI}^{\scriptscriptstyle(\text{I})}$

At a high level, $\text{EG-PSI}^{\scriptscriptstyle(\text{I})}$ operates as
follows. Initially, each client in group $\mathcal{G}_{\scriptscriptstyle 0}$
agrees with every client in group $\mathcal{G}_{\scriptscriptstyle 1}$ on a
secret key. Every client encrypts its set elements using every key it has
agreed on with other clients (in a different group).

Each client, for every encrypted set element, temporally stores a triple that
includes (i) the encrypted element, (ii) the key used to encrypt that element,
and (iii) the index of the client with whom the key was shared. These triples
will enable the client to efficiently (a) retrieve the correct key and (b)
identify the client with whom it has the element in common when presented with
an encrypted element. Once all elements are encrypted using the corresponding
keys, each client transmits only its encrypted elements to $\mathcal{TEE}$.

Given the sets of encrypted elements from all clients, $\mathcal{TEE}$
aggregates these sets and identifies the encrypted elements that appear more
than once. Subsequently, $\mathcal{TEE}$ forwards to a client those encrypted
elements that (1) appear more than once and (2) are among the messages that
the client initially sent to $\mathcal{TEE}$. Upon receiving each encrypted
element from $\mathcal{TEE}$, a client searches its local list of triples to
locate the corresponding key and the index $l$ representing a specific client.
Utilizing the key, the client decrypts the element and regards the resultant
element as one of the elements within the intersection it shares with the
$l$-th client. For a comprehensive description of $\text{EG-
PSI}^{\scriptscriptstyle(\text{I})}$, refer to Figure 1.

• Parties. Trusted execution environment $\mathcal{TEE}$, clients in group
$\mathcal{G}_{\scriptscriptstyle 0}:\\{\mathcal{C}_{\scriptscriptstyle
0,1},\ldots,\mathcal{C}_{\scriptscriptstyle 0,m}\\}$, and clients in group
$\mathcal{G}_{\scriptscriptstyle 1}:\\{\mathcal{C}_{\scriptscriptstyle
1,1},\ldots,\mathcal{C}_{\scriptscriptstyle 1,m}\\}$. • Inputs. Sets
${S}_{\scriptscriptstyle 0,1},\ldots,{S}_{\scriptscriptstyle
0,m},{S}_{\scriptscriptstyle 1,1},\ldots,{S}_{\scriptscriptstyle 1,m}$, where
each ${S}_{\scriptscriptstyle i,j}$ belongs to client
$\mathcal{C}_{\scriptscriptstyle i,j}$, $0\leq j\leq 1$ and $1\leq i\leq m$. •
Outputs. $\vec{v}_{\scriptscriptstyle j,i}$ to
$\mathcal{C}_{\scriptscriptstyle j,i}$, where $\vec{v}_{\scriptscriptstyle
j,i}=\Big{[}[{S}_{\scriptscriptstyle j,i}\cap{S}_{\scriptscriptstyle
1-j,1}],\ldots,[{S}_{\scriptscriptstyle j,i}\cap{S}_{\scriptscriptstyle
1-j,m}]\Big{]}$. 1. Setup. (a) each client $\mathcal{C}_{\scriptscriptstyle
0,i}$ in $\mathcal{G}_{\scriptscriptstyle 0}$ agrees with every client
$\mathcal{C}_{\scriptscriptstyle 1,l}$ in $\mathcal{G}_{\scriptscriptstyle 1}$
on a secret key $k_{\scriptscriptstyle i,l}$, by picking a random key
$k_{\scriptscriptstyle i,l}$ and sending it to
$\mathcal{C}_{\scriptscriptstyle 1,l}$. Client
$\mathcal{C}_{\scriptscriptstyle 0,i}$ stores this key as
$k_{\scriptscriptstyle i,l}$ while $\mathcal{C}_{\scriptscriptstyle 1,l}$
stores this key as $k_{\scriptscriptstyle l,i}$. (b) each
$\mathcal{C}_{\scriptscriptstyle j,i}$ takes the following steps: i. encrypts
its set elements under keys $k_{\scriptscriptstyle i,l}$ ($\forall l,1\leq
l\leq m$) as follows, $\forall e\in{S}_{\scriptscriptstyle
j,i}:\mathtt{PRP}(k_{\scriptscriptstyle i,l},e)\rightarrow
e^{\prime}_{\scriptscriptstyle i,l}$. Let set
${S}^{\prime}_{\scriptscriptstyle j,i}$ contain the encrypted set elements of
$\mathcal{C}_{\scriptscriptstyle j,i}$ and let set $T_{\scriptscriptstyle
j,i}$ contains all triples of the form $(e^{\prime}_{\scriptscriptstyle
i,l},k_{\scriptscriptstyle i,l},l)$. ii. sends
${S}^{\prime}_{\scriptscriptstyle j,i}$ to $\mathcal{TEE}$ and locally keeps
$T_{j,i\scriptscriptstyle}$. 2. Finding Encrypted Intersection.
$\mathcal{TEE}$ takes the following steps for each
$\mathcal{C}_{\scriptscriptstyle j,i}$. (a) appends to an empty set,
$R_{\scriptscriptstyle j,i}$, every ciphertext that satisfy the following
conditions hold: • it appears more than once in the set
$S=\sum\limits_{\scriptscriptstyle j=0}^{\scriptscriptstyle
1}\sum\limits_{\scriptscriptstyle i=1}^{\scriptscriptstyle
m}{S}^{\prime}_{\scriptscriptstyle j,i}$. • it appears in set
${S}^{\prime}_{\scriptscriptstyle j,i}$. (b) sends $R_{\scriptscriptstyle
j,i}$ to $\mathcal{C}_{\scriptscriptstyle j,i}$. 3. Extracting Plaintext
Intersection. Each $\mathcal{C}_{\scriptscriptstyle j,i}$ takes the following
steps. (a) constructs a vector $\vec{v}_{\scriptscriptstyle
j,i}=[\vec{v}_{\scriptscriptstyle j,i,1},\ldots,\vec{v}_{\scriptscriptstyle
j,i,m}]$, where each vector in $\vec{v}_{\scriptscriptstyle j,i}$ is initially
empty. (b) decrypts each element of $R_{\scriptscriptstyle j,i}$ as follows.
$\forall e^{\prime}\in R_{\scriptscriptstyle j,i}:$ i. retrieves decryption
key $k_{\scriptscriptstyle i,l}$ and index $l$ from $T_{\scriptscriptstyle
j,i}$ using $e^{\prime}$. ii. calls
$\mathtt{PRP}^{\scriptscriptstyle-1}(k_{\scriptscriptstyle
i,l},e^{\prime})\rightarrow e$ and appends $e$ to $l$-th vector in
$\vec{v}_{\scriptscriptstyle j,i}$. (c) considers $\vec{v}_{\scriptscriptstyle
j,i}$ as the result.

Figure 1: First Variant of Efficient Group PSI ($\text{EG-
PSI}^{\scriptscriptstyle(\text{I})}$).

The only information that $\mathcal{TEE}$ learns in EG-PSI is the _size_ of
the intersection of any two clients' sets, called _pair-wise intersection
cardinality_. Below, we formally define it.

######  Definition 3 (pair-wise intersection cardinality).

Let $(\underbrace{{S}^{\prime}_{\scriptscriptstyle
0,1},\ldots,{S}^{\prime}_{\scriptscriptstyle
0,m}}_{\scriptscriptstyle\mathcal{G}_{\scriptscriptstyle 0}}),$
$(\underbrace{{S}^{\prime}_{\scriptscriptstyle
1,1},\ldots,{S}^{\prime}_{\scriptscriptstyle
1,m}}_{\scriptscriptstyle\mathcal{G}_{\scriptscriptstyle 1}})$ be two groups
$\mathcal{G}_{\scriptscriptstyle 0}$ and $\mathcal{G}_{\scriptscriptstyle 1}$
of (encrypted) sets. Then, vector $\vec{s}$ represents the pair-wise
intersection cardinality: $\vec{s}=[\vec{s}_{\scriptscriptstyle 0,1},\ldots,$
$\vec{s}_{\scriptscriptstyle 0,m},\vec{s}_{\scriptscriptstyle
1,1},\ldots,\vec{s}_{\scriptscriptstyle 1,m}]$, where
$\vec{s}_{\scriptscriptstyle j,i}=\Big{[}\big{|}[{S}_{\scriptscriptstyle
j,i}\cap{S}_{\scriptscriptstyle
1-j,1}]\big{|},\ldots,\big{|}[{S}_{\scriptscriptstyle
j,i}\cap{S}_{\scriptscriptstyle 1-j,m}]\big{|}\Big{]}$, $0\leq j\leq 1$, and
$1\leq i\leq m$.

######  Definition 4.

Let $\vec{s}$ be a pair-wise intersection cardinality of two groups
$\mathcal{G}_{\scriptscriptstyle 0}$ and $\mathcal{G}_{\scriptscriptstyle 1}$
of encrypted sets: $(\underbrace{{S}^{\prime}_{\scriptscriptstyle
0,1},\ldots,{S}^{\prime}_{\scriptscriptstyle
0,m}}_{\scriptscriptstyle\mathcal{G}_{\scriptscriptstyle
0}}),(\underbrace{{S}^{\prime}_{\scriptscriptstyle
1,1},\ldots,{S}^{\prime}_{\scriptscriptstyle
1,m}}_{\scriptscriptstyle\mathcal{G}_{\scriptscriptstyle 1}})$, with respect
to Definition 3. Then, leakage function $\mathcal{L}$ is defined as follows:
$\mathcal{L}\Big{(}({S}^{\prime}_{\scriptscriptstyle
0,1},\ldots,{S}^{\prime}_{\scriptscriptstyle
0,m}),({S}^{\prime}_{\scriptscriptstyle
1,1},\ldots,{S}^{\prime}_{\scriptscriptstyle 1,m})\Big{)}\rightarrow\vec{s}$.

######  Theorem 1.

Let $f_{\scriptscriptstyle\text{G-PSI}}$ be the functionality defined in
Relation 5. Also, let $\mathcal{L}$ be the leakage function presented in
Definition 4. If $\mathtt{PRP}$ is a secure pseudorandom permutation, then
$\text{EG-PSI}^{\scriptscriptstyle(\text{I})}$ (presented in Figure 1)
securely realizes $f_{\scriptscriptstyle\text{G-PSI}}$, with respect to
Definition 2.

We refer to Appendix -A for the proof of Theorem 1.

####  III-B2 $\text{EG-PSI}^{\scriptscriptstyle(\text{II})}$

In this section, we present $\text{EG-PSI}^{\scriptscriptstyle(\text{II})}$
which is the second variant of EG-PSI. Note that $\mathcal{TEE}$ in $\text{EG-
PSI}^{\scriptscriptstyle(\text{I})}$ is able to learn the cardinality of the
intersection of each pair of clients' sets. We aim to reduce this leakage in
$\text{EG-PSI}^{\scriptscriptstyle(\text{II})}$. However, $\text{EG-
PSI}^{\scriptscriptstyle(\text{II})}$ is no longer based on symmetric key
cryptography as it depends on OPRF. To the best of our knowledge, all the
constructions of OPRFs are based on public key cryptography whose security
depends on some hard problem assumptions. The same holds for $\text{EG-
PSI}^{\scriptscriptstyle(\text{II})}$.

A brief overview of the construction of $\text{EG-
PSI}^{\scriptscriptstyle(\text{II})}$ is as follows. We have two groups of
clients $\mathcal{G}_{\scriptscriptstyle 0}$ and
$\mathcal{G}_{\scriptscriptstyle 1}$ having their own set that they want to
find the pairwise intersection. There is a $\mathcal{TEE}$ that has a key $k$
for a $\mathtt{PRF}$. During the setup, each client interacts with
$\mathcal{TEE}$ to encrypt their set using $\mathtt{PRF}(k,\cdot)$ through an
OPRF call. Then, each client of group $\mathcal{G}_{\scriptscriptstyle 1}$
will send their encrypted set to every client of
$\mathcal{G}_{\scriptscriptstyle 0}$. Upon receiving an encrypted set from a
client of $\mathcal{G}_{\scriptscriptstyle 1}$, each client of
$\mathcal{G}_{\scriptscriptstyle 0}$ determines the intersection with their
encrypted set. Once the client finds the intersection, it marks the index of
the elements in the intersection and consider the elements with the same index
in the unencrypted set as elements in the intersection. Similarly, each client
of $\mathcal{G}_{\scriptscriptstyle 0}$ shares their encrypted set with each
client of $\mathcal{G}_{\scriptscriptstyle 1}$ and follows the same steps.
Ultimately, every client of $\mathcal{G}_{\scriptscriptstyle 0}$ knows the
intersection between their set and all the sets belonging to the clients of
$\mathcal{G}_{\scriptscriptstyle 1}$, and the other way around. We give a
detailed description of $\text{EG-PSI}^{\scriptscriptstyle(\text{II})}$ in
Figure 2.

• Parties. Trusted execution environment $\mathcal{TEE}$, clients in group
$\mathcal{G}_{\scriptscriptstyle 0}:\\{\mathcal{C}_{\scriptscriptstyle
0,1},\ldots,\mathcal{C}_{\scriptscriptstyle 0,m}\\}$, and clients in group
$\mathcal{G}_{\scriptscriptstyle 1}:\\{\mathcal{C}_{\scriptscriptstyle
1,1},\ldots,\mathcal{C}_{\scriptscriptstyle 1,m}\\}$. • Inputs. Sets
${S}_{\scriptscriptstyle 0,1},\ldots,{S}_{\scriptscriptstyle
0,m},{S}_{\scriptscriptstyle 1,1},\ldots,{S}_{\scriptscriptstyle 1,m}$, where
each ${S}_{\scriptscriptstyle i,j}$ belongs to client
$\mathcal{C}_{\scriptscriptstyle i,j}$, $0\leq j\leq 1$ and $1\leq i\leq m$. •
Outputs. $\vec{v}_{\scriptscriptstyle j,i}$ to
$\mathcal{C}_{\scriptscriptstyle j,i}$, where $\vec{v}_{\scriptscriptstyle
j,i}=\Big{[}[{S}_{\scriptscriptstyle j,i}\cap{S}_{\scriptscriptstyle
1-j,1}],\ldots,[{S}_{\scriptscriptstyle j,i}\cap{S}_{\scriptscriptstyle
1-j,m}]\Big{]}$. 1. Setup. $\mathcal{TEE}$ generates a secret key $k$ for
$\mathtt{PRF}$ that will be used for an OPRF evaluation. 2. Encryption of each
client's set. Each client $\mathcal{C}_{j,i}$ and $\mathcal{TEE}$ run an OPRF
protocol and obtains the encrypted set $\mathtt{PRF}(k,{S}_{\scriptscriptstyle
j,i})$, where $0\leq j\leq 1$ and $1\leq i\leq m$. 3. Finding Encrypted
Intersections. (a) Each client $\mathcal{C}_{\scriptscriptstyle j,i}$ sends
each $\mathtt{PRF}(k,{S}_{\scriptscriptstyle j,i})$ to every client
$\mathcal{C}_{\scriptscriptstyle 1-j,i}$ (in the other group), where $0\leq
j\leq 1$ and $1\leq i\leq m$. (b) Each client $\mathcal{C}_{\scriptscriptstyle
j,i}$, takes the following steps. i. Creates an empty set $R_{j,i,t}$ for all
$1\leq t\leq m$. ii. Let $e_{\ell}$ represents an element of
$\mathtt{PRF}(k,{S}_{\scriptscriptstyle j,i})$, where
$1\leq\ell\leq|\mathtt{PRF}(k,{S}_{\scriptscriptstyle j,i})|$.
Performs $R_{j,i,t}\leftarrow R_{j,i,t}\cup\\{\ell\\}$ if $e_{\ell}$ appears
both in $\mathtt{PRF}(k,{S}_{\scriptscriptstyle j,i})$ and
$\mathtt{PRF}(k,{S}_{\scriptscriptstyle j-1,i})$. 4. Extracting Plaintext
Intersection. Each $\mathcal{C}_{j,i}$ for $j=0,1$, and $1\leq i\leq m$ does
the following. (a) Constructs a vector $\vec{v}_{\scriptscriptstyle
j,i}=[\vec{v}_{\scriptscriptstyle j,i,1},\ldots,\vec{v}_{\scriptscriptstyle
j,i,m}]$, where each vector in $\vec{v}_{\scriptscriptstyle j,i}$ is initially
empty. (b) Appends the $\ell$-th element of ${S}_{\scriptscriptstyle j,i}$ to
$\vec{v}_{\scriptscriptstyle j,i,t}$ for all $\ell\in R_{j,i,t}$. (c) Returns
$\vec{v}_{\scriptscriptstyle j,i}$.

Figure 2: Second Variant of Efficient Group PSI ($\text{EG-
PSI}^{\scriptscriptstyle(\text{II})}$).

In $\text{EG-PSI}^{\scriptscriptstyle(\text{II})}$, $\mathcal{TEE}$ does not
participate in the protocol except the OPRF evaluation and that is also a one-
time activity. As a result, $\mathcal{TEE}$ does not learn anything about the
set intersection, it only learns the cardinality of each client's set.

######  Theorem 2.

Let $f_{\scriptscriptstyle\text{G-PSI}}$ be the functionality defined in
Relation 5 (on page 5). Also, let $\mathcal{L}$ be the leakage function
presented in Definition 4 with the empty output. If OPRF is secure, then
$\text{EG-PSI}^{\scriptscriptstyle(\text{II})}$ securely realizes
$f_{\scriptscriptstyle\text{G-PSI}}$, w.r.t. Definition 2.

Appendix -B outlines the proof of Theorem 2. Note that both variants remain
secure in the presence of semi-honest adversaries. However, if $\mathcal{TEE}$
or a client is a malicious (or active) adversary, then it can affect the
correctness of the result, without being detected.

##  IV Privacy-Preserving Multi-Party Deduplication (P-MPD)

###  IV-A Formal Definition of P-MPD

P-MPD considers the setting where there are $n$ clients
$C=\\{\mathcal{C}_{\scriptscriptstyle
1},\ldots,\mathcal{C}_{\scriptscriptstyle m}\\}$ and each
$\mathcal{C}_{\scriptscriptstyle i}\in C$ has a set $S_{\scriptscriptstyle
i}$. P-MPD enables the clients to (efficiently) remove duplicates from their
local sets such that after the deduplication the concatenation of all clients'
local sets equals the union of their initial sets.

The functionality $f_{\scriptscriptstyle\text{P-MPD}}$ that P-MPD computes
takes a set $S_{\scriptscriptstyle i}$ from each
$\mathcal{C}_{\scriptscriptstyle i}$. It returns an updated (i.e.,
deduplicated) set $S^{\prime}_{\scriptscriptstyle i}$ to each
$\mathcal{C}_{\scriptscriptstyle i}$. Formerly,
$f_{\scriptscriptstyle\text{P-MPD}}$ can be defined as follows:

$f_{\scriptscriptstyle\text{P-MPD}}(S_{\scriptscriptstyle
1},\ldots,S_{\scriptscriptstyle m})\rightarrow(S^{\prime}_{\scriptscriptstyle
1},\ldots,S^{\prime}_{\scriptscriptstyle m}),$ (8)

where $\sum\limits^{\scriptscriptstyle m}_{\scriptscriptstyle
i=1}S^{\prime}_{\scriptscriptstyle i}=\bigcup\limits_{\scriptscriptstyle
i=1}^{\scriptscriptstyle m}S_{\scriptscriptstyle
i}=S_{\scriptscriptstyle\cup}$ and $S_{\cup}$ denotes the union of all initial
sets and contains only unique elements.

To maintain generality, we define a leakage function, denoted as
$\mathcal{W}$. The output of this function relies on the protocol implementing
$f_{\scriptscriptstyle\text{P-MPD}}$. We assert that a protocol securely
realizes $f_{\scriptscriptstyle\text{P-MPD}}$ if whatever can be computed by a
party in the protocol can be derived solely from its individual input and
output, given the output of $\mathcal{W}$. Below, we formally state it.

######  Definition 5 (Security of P-MPD).

Let $S=\\{{S}_{\scriptscriptstyle 1},\ldots,{S}_{\scriptscriptstyle m}\\}$,
and ${S}_{\scriptscriptstyle i}$ represent a set belonging to client
$\mathcal{C}_{\scriptscriptstyle i}$. Let $\mathcal{W}$ denote a leakage
function and $f_{\scriptscriptstyle\text{P-MPD}}$ be the functionality defined
in Relation 8. Then, a protocol $\Psi$ securely realizes
$f_{\scriptscriptstyle\text{P-MPD}}$ in the presence of a static semi-honest
PPT adversary $\mathcal{A}$, if for every $\mathcal{A}$ in the real model,
there exists a PPT $\mathsf{Sim}$ in the ideal model, such that for every
$\mathcal{C}_{\scriptscriptstyle i}\in\\{\mathcal{C}_{\scriptscriptstyle
1},\ldots,\mathcal{C}_{\scriptscriptstyle m}\\}$, Relation 9 holds.

$\\{\mathsf{Sim}^{\scriptscriptstyle\mathcal{W}}_{\scriptscriptstyle\mathcal{C}_{\scriptscriptstyle
i}}({S}_{\scriptscriptstyle i},{S}^{\prime}_{\scriptscriptstyle
i})\\}_{\scriptscriptstyle S}\stackrel{{\scriptstyle
c}}{{\equiv}}\\{\mathsf{View}_{\scriptscriptstyle\mathcal{C}_{\scriptscriptstyle
i}}^{\scriptscriptstyle\mathcal{A},\Psi}(S)\\}_{\scriptscriptstyle S}.$ (9)

###  IV-B Constructions of P-MPD

####  IV-B1 Construction Based on EG-PSI

We introduce a pioneering protocol called Efficient Privacy-Preserving Multi-
Party Deduplication (EP-MPD) that realizes P-MPD efficiently. The idea behind
EP-MPD's design involves constructing a binary tree with leaf nodes
representing the clients’ indices. At each level, each cluster is formed with
two different groups of clients, namely $\mathcal{G}_{\scriptscriptstyle 0}$
and $\mathcal{G}_{\scriptscriptstyle 1}$. Subsequently, EG-PSI is recursively
applied to the sets of clients sharing the same cluster until the tree's root
is reached. After each invocation of EG-PSI, the clients of
$\mathcal{G}_{\scriptscriptstyle 0}$ update their sets by removing the
intersections, returned by EG-PSI, from their local sets. These updated sets
are then used as input in the subsequent EG-PSI invocation.

Next, we delve into further detail. We begin by sorting the clients' indices
in ascending order. Next, we construct a binary tree such that the leaf nodes
represent the clients' indices.

At level $d=1$, commencing from the left-hand side, every two clients form a
cluster. Within each cluster, the first client is assigned to group
$\mathcal{G}_{\scriptscriptstyle 0}$ and the second client to group
$\mathcal{G}_{\scriptscriptstyle 1}$. Then, the clients within the same
cluster engage in an instance of EG-PSI. Upon the return of the sets'
intersection by EG-PSI, only the client situated on the left-hand side,
specifically the one with the smaller index, modifies its local set by
eliminating the elements of the intersection from its sets. This process is
outlined in Figure 3(a).

(a) Demonstration of clients joining various groups and clusters at level 1.

(b) Illustration of clients joining various groups and clusters at level 2.

(c) Depiction of how clients become part of diverse groups and clusters at
level 3.

Figure 3: The process of eight clients forming clusters and groups at various
levels of a binary tree. At each level, clients belonging to groups
$\mathcal{G}_{\scriptscriptstyle 0}$ and $\mathcal{G}_{\scriptscriptstyle 1}$
within the same cluster initiate EG-PSI, followed by the updating of their
respective local sets.

At level $d=2$, starting from the left-hand side, every set of
$2^{\scriptscriptstyle d}$ clients form a cluster. Within each cluster, the
initial $\frac{2^{\scriptscriptstyle d}}{2}=2$ clients enter group
$\mathcal{G}_{\scriptscriptstyle 0}$ and the remainder (i.e., the remaining
$2$ clients) enter group $\mathcal{G}_{\scriptscriptstyle 1}$. Subsequently,
the clients within the same cluster engage in an instance of EG-PSI. Once
again, upon the return of their sets' intersection by EG-PSI, the clients
possessing the smaller indices update their local sets. This procedure is
illustrated in Figure 3(b).

The process continues until level $d=\log_{\scriptscriptstyle 2}{m}$ is
reached. At this point, all $m$ clients collectively engage in an instance of
EG-PSI. Each $\frac{2^{\scriptscriptstyle d}}{2}=\frac{m}{2}$ clients enter
group $\mathcal{G}_{\scriptscriptstyle 0}$ and the remaining $\frac{m}{2}$
clients enter group $\mathcal{G}_{\scriptscriptstyle 1}$. These $m$ clients
jointly participate in an instance of EG-PSI. Similarly to previous steps, the
clients with the smaller indices update their local sets based on the output
of EG-PSI. This procedure is outlined in Figure 3(c).

• Parties. A set of clients $\\{\mathcal{C}_{\scriptscriptstyle
1},\ldots,\mathcal{C}_{\scriptscriptstyle m}\\}$. • Inputs. Sets
${S}_{\scriptscriptstyle 1},\ldots,{S}_{\scriptscriptstyle m}$, where each
${S}_{\scriptscriptstyle i}$ belongs to client
$\mathcal{C}_{\scriptscriptstyle i}$, $1\leq i\leq m$, and $m$ is a power of
2. • Outputs. Updated sets ${S}^{\prime}_{\scriptscriptstyle
1},\ldots,{S}^{\prime}_{\scriptscriptstyle m}$, where each
${S}^{\prime}_{\scriptscriptstyle i}$ belongs to client
$\mathcal{C}_{\scriptscriptstyle i}$, and $\sum\limits^{\scriptscriptstyle
m}_{\scriptscriptstyle i=1}S^{\prime}_{\scriptscriptstyle
i}=\bigcup\limits_{\scriptscriptstyle i=1}^{\scriptscriptstyle
m}S_{\scriptscriptstyle i}$. The clients take the following steps $\forall d$,
$1\leq d\leq\log_{\scriptscriptstyle 2}(m):$ 1. Forming Clusters. Every
distinct $2^{\scriptscriptstyle d}$ clients enter the same cluster. Thus, for
every level $d$, there will be $\frac{m}{2^{\scriptscriptstyle d}}$
cluster(s). For instance, when $d=1$, then there are the following clusters:
$(\mathcal{C}_{\scriptscriptstyle 1},\mathcal{C}_{\scriptscriptstyle
2}),\ldots,(\mathcal{C}_{\scriptscriptstyle
m-1},\mathcal{C}_{\scriptscriptstyle m})$. 2. Forming Group. In each cluster,
the first $\frac{2^{\scriptscriptstyle d}}{2}$ clients enter group $0$,
$\mathcal{G}_{\scriptscriptstyle 0}$, and the rest of the clients enter group
$1$, $\mathcal{G}_{\scriptscriptstyle 1}$. 3. Finding Intersection. In each
cluster, the clients of $\mathcal{G}_{\scriptscriptstyle 0}$ and
$\mathcal{G}_{\scriptscriptstyle 1}$ together engage an instance of EG-PSI.
Each client $\mathcal{C}_{\scriptscriptstyle j}$ receives a vector
$\vec{v}_{\scriptscriptstyle j}$ from EG-PSI, where
$\vec{v}_{\scriptscriptstyle j}$ specifies the elements that
$\mathcal{C}_{\scriptscriptstyle j}$ has in common with each client of the
other group in the same cluster. It would be sufficient if only clients of
$\mathcal{G}_{\scriptscriptstyle 0}$ in each cluster were aware of the
intersection result. 4. Removing Duplication. For every element
$e\in\vec{v}_{\scriptscriptstyle j}$, each $\mathcal{C}_{\scriptscriptstyle
j}$ in $\mathcal{G}_{\scriptscriptstyle 0}$ calls
$\mathtt{Update}(S_{\scriptscriptstyle j},\\{e\\})\rightarrow
S_{\scriptscriptstyle j}$, where $S_{\scriptscriptstyle j}\leftarrow
S_{\scriptscriptstyle j}\setminus\\{e\\}$.

Figure 4: Efficient Privacy-Preserving Multi-Party Deduplication (EP-MPD): the
construction of P-MPD.

Figure 4 presents a detailed description of EP-MPD. For the sake of
simplicity, we assume that $m$ is a power of 2 in EP-MPD's description.
However, we do not impose on the number of clients. Non-powers of 2 will
result in incomplete sub-trees in the formation of clusters in the DE protocol
where each group may have an unequal number of clients. This does not affect
the EP-MPD protocol execution.

###  IV-C Naive Approaches

####  IV-C1 Running a Two-Party PSI Multiple Times

One might be tempted to allow each client to invoke an existing two-party PSI
with every other client. However, this approach in total requires ${m\choose
2}=O(m^{\scriptscriptstyle 2})$ invocations of the two-party PSI. Whereas EP-
MPD requires only $\sum\limits^{\scriptscriptstyle\log_{\scriptscriptstyle
2}(m)}_{\scriptscriptstyle i=1}(\frac{m}{2^{\scriptscriptstyle i}})=m-1$
invocations of our efficient tailor-made PSI, EG-PSI. To provide concrete
values, when $m=256$, the naive scheme requires 32,640 invocations of a
standard two-party PSI, whereas our scheme requires only $255$ invocations of
EG-PSI.

####  IV-C2 Running Multi-Party PSI Once

One might be tempted to execute an existing multi-party PSI protocol only once
on all clients' sets, hoping to identify and subsequently remove duplicated
elements. Nevertheless, this approach falls short of identifying all
duplications. The limitation arises from the fact that a multi-party PSI can
uncover elements common to all clients, making it incapable of detecting
elements shared among only a subset of clients.

####  IV-C3 Deduplicating all Sets at Once

There is a simplified version of EP-MPD. In this variant, each client reaches
an agreement with the others on a secret key. Subsequently, each client
encrypts its set elements using every key agreed upon with the other clients.
Finally, all clients transmit their encrypted set elements to $\mathcal{TEE}$.
Upon receiving the encrypted sets from all clients, $\mathcal{TEE}$ identifies
all duplicated elements. It then transmits to each client: (1) the duplicated
elements found in the original elements that the respective client sent to
$\mathcal{TEE}$, and (2) the index of the client with which it shares the same
element. Based on $\mathcal{TEE}$'s response, the clients with smaller indices
update their local sets accordingly.

However, this approach requires that $\mathcal{TEE}$ maintains a local storage
or memory space equal to the size of the concatenation of all encrypted sets.
In contrast, EP-MPD with the underlying EG-PSI building block, allows
$\mathcal{TEE}$ to have a substantially smaller storage or memory space. This
is achieved because, before $\mathcal{TEE}$ receives all clients' encrypted
sets at level $d=log_{\scriptscriptstyle 2}(m)$, clients apply updates to
their sets multiple times. This iterative process progressively reduces the
size of the clients' sets, and the reduction can be particularly significant
when the number of duplications is substantial.

###  IV-D Security Analysis

In any secure (multi-party) deduplication protocol, a participating client
will learn the exact redundant elements within its set upon the protocol's
completion. However, in EP-MPD, a client gains slightly more information. To
be specific, upon the completion of EP-MPD, each client acquires the knowledge
of the index (or identity) of the client that shares the redundant element.
This additional information gained by a client during the execution of EP-MPD
is formally defined as the output of a leakage function $\mathcal{W}$ which we
define below.

$\mathcal{W}$ takes as input (i) sets ${S}_{\scriptscriptstyle
1},\ldots,{S}_{\scriptscriptstyle m}$, where each set ${S}_{\scriptscriptstyle
i}$ belongs to client $\mathcal{C}_{\scriptscriptstyle i}$, and (ii) sets
$R_{\scriptscriptstyle 1},\ldots,R_{\scriptscriptstyle m}$, where each
$R_{\scriptscriptstyle i}$ contains the redundancy (or intersection) that a
set ${S}_{\scriptscriptstyle i}$ has with every other set. $\mathcal{W}$
outputs to the $i$-th client a set $Q_{\scriptscriptstyle i}$ of triples,
where each triple is of the form $(r_{\scriptscriptstyle i,l},i,l)$,
$r_{\scriptscriptstyle i,l}\in R_{\scriptscriptstyle i}$ is a redundancy
between sets ${S}_{\scriptscriptstyle i}$ and ${S}_{\scriptscriptstyle l}$.

######  Definition 6.

Let $S=\\{{S}_{\scriptscriptstyle 1},\ldots,{S}_{\scriptscriptstyle m}\\}$ be
a set of sets, where each set ${S}_{\scriptscriptstyle i}$ belongs to client
$\mathcal{C}_{\scriptscriptstyle i}$. Also, let $R=\\{R_{\scriptscriptstyle
1},\ldots,R_{\scriptscriptstyle m}\\}$ be a set of sets, where each set
$R_{\scriptscriptstyle i}$ comprises the redundancy that
${S}_{\scriptscriptstyle i}$ has with every other $j$-th set, for all $j$,
$1\leq j\leq m$ and $i\neq j$. Then, leakage function $\mathcal{W}$ is defined
as follows: $\mathcal{W}(S,R)\rightarrow(Q_{\scriptscriptstyle
1},\ldots,Q_{\scriptscriptstyle m})$, where each $Q_{\scriptscriptstyle i}$ is
a set of triples of the form $(r_{\scriptscriptstyle i,l},i,l)$,
$r_{\scriptscriptstyle i,l}\in R_{\scriptscriptstyle i}$ is a redundancy
between sets ${S}_{\scriptscriptstyle i}$ and ${S}_{\scriptscriptstyle l}$.

######  Theorem 3.

Let $f_{\scriptscriptstyle\text{P-MPD}}$ be the functionality defined in
Relation 8 and $\mathcal{W}$ be the leakage function presented in Definition
6. If EG-PSI is secure (w.r.t. Definition 2), then EP-MPD (presented in Figure
4) securely realizes $f_{\scriptscriptstyle\text{P-MPD}}$, w.r.t. Definition
5.

The proof of Theorem 3 can be found in Appendix -C.

##  V Enhanced FL: Applying EP-MPD to FL

With all essential building blocks in place, we are prepared to elucidate the
complete functionality of the system. There are clients
$\mathcal{C}_{\scriptscriptstyle 1},\ldots,\mathcal{C}_{\scriptscriptstyle m}$
having the sets ${S}_{\scriptscriptstyle 1},\ldots,{S}_{\scriptscriptstyle
m}$, where each ${S}_{\scriptscriptstyle i}$ belongs to client
$\mathcal{C}_{\scriptscriptstyle i}$ respectively. Phase 1 involves each
client conducting local deduplication. Since the local deduplication is a
private computation there is no privacy requirement. The data owners can apply
deduplication techniques as illustrated in [31] which results in having a set
${S}_{\scriptscriptstyle i}^{\prime}$ free of duplicates by each client
$\mathcal{C}_{\scriptscriptstyle i}$. Subsequently, in Phase 2 they employ EP-
MPD to eliminate duplicates across all clients. At the end of this phase,
client $\mathcal{C}_{\scriptscriptstyle i}$ gets an updated set
${S}_{\scriptscriptstyle i}^{\prime\prime}$, such that
$\sum\limits_{i=1}^{\scriptscriptstyle m}{S}_{\scriptscriptstyle
i}^{\prime\prime}=\bigcup\limits_{i=1}^{\scriptscriptstyle
m}{S}_{\scriptscriptstyle i}^{\prime}.$ Moving to Phase 3, they adopt a FL
protocol (outlined in Section II-B) to train the model. Further details of
this procedure are provided in Figure 5.

• Parties. A set of clients $\\{\mathcal{C}_{\scriptscriptstyle
1},\ldots,\mathcal{C}_{\scriptscriptstyle m}\\}$. • Server. Holds the initial
model $\bm{\theta}$. • Inputs. Sets ${S}_{\scriptscriptstyle
1},\ldots,{S}_{\scriptscriptstyle m}$, where each ${S}_{\scriptscriptstyle i}$
belongs to client $\mathcal{C}_{\scriptscriptstyle i}$, $1\leq i\leq m$, and
$m$ is a power of two. • Outputs. A global updated model $\Theta$. 1. Local
Deduplication. Each client runs a deduplication algorithm on their local
dataset. At the end, client $\mathcal{C}_{\scriptscriptstyle i}$ receives an
updated dataset ${S}_{\scriptscriptstyle i}^{\prime}$. 2. Global
Deduplication. (a) All the clients participate in the EP-MPD as described in
Figure 4. (b) Each client $\mathcal{C}_{\scriptscriptstyle i}$ gets updated
set ${S}_{\scriptscriptstyle i}^{\prime\prime}$, such that
$\sum\limits_{i=1}^{\scriptscriptstyle m}{S}_{\scriptscriptstyle
i}^{\prime\prime}=\bigcup\limits_{i=1}^{\scriptscriptstyle
m}{S}_{\scriptscriptstyle i}^{\prime}.$ 3. Federated learning. (a) The server
and clients agree upon an FL protocol for training. (b) The server initiates
the learning by sharing the initial model $\bm{\theta}$ with each client. (c)
Each client $\mathcal{C}_{\scriptscriptstyle i}$ trains on their local dataset
${S}_{\scriptscriptstyle i}^{\prime\prime}$ and updates $\bm{\theta}$ to
$\bm{\theta}_{\scriptscriptstyle i}$. (d) The clients and server aggregate the
local models $\bm{\theta}_{\scriptscriptstyle i}$ trained by the clients. (e)
The server outputs the global updated model $\Theta$ for the next training
round.

Figure 5: Federated learning with deduplication.

##  VI Experiments

###  VI-A Implementation Details

We implement the EP-MPD protocol in python=3.10. We use AES with a 128-bit key
in CBC mode from the cryptography library as a PRP in $\text{EG-
PSI}^{\scriptscriptstyle(\text{I})}$. To realize an OPRF in $\text{EG-
PSI}^{\scriptscriptstyle(\text{II})}$, we use the OPRF algorithm proposed in
[11] from the oprf library. All EP-MPD experiments are conducted on a batch
computing facility with a Dual Intel Xeon E5-2660 v3 @ 2.6 GHz CPU and 60 GB
RAM.

For the FL experiments, we implement a FL setting for CLMs using python=3.10
with the transformers=4.40.1 and torch=2.3 libraries. We implement the FedAvg
[38] algorithm for FL training to analyze the effect of EP-MPD on FL's
performance. However, in practice, we recommend combining EP-MPD with privacy-
preserving FL protocols for end-to-end privacy guarantees. All FL experiments
are conducted on a server with an Intel(R) Xeon(R) Gold 6336Y CPU @ 2.40GHz
CPU and NVIDIA RTX A6000 GPU.

We run all clients sequentially on a machine for both experiments. However, to
emulate a real-world setting where clients run on different devices at the
same time, we first compute the individual client running times and then
estimate the real-world distributed running time by assuming the clients have
run simultaneously. We open-source our
implementations111https://github.com/vdasu/deduplication.

While implementing EP-MPD, we have two options for the EG-PSI module:
$\text{EG-PSI}^{\scriptscriptstyle(\text{I})}$ and $\text{EG-
PSI}^{\scriptscriptstyle(\text{II})}$. We observe that $\text{EG-
PSI}^{\scriptscriptstyle(\text{II})}$-based EP-MPD calls an OPRF function for
every client in the leaf nodes of the EP-MPD tree, returning an encryption of
the clients' sets. As clients move to upper levels, their set elements remain
unchanged, with only the cardinality potentially changing. Therefore, except
at the bottom level, OPRF calls are unnecessary for encryption, allowing the
same encrypted set or their subsets to be reused at other levels. Thus, we
have slightly adjusted the implementation. This significantly reduces time
without compromising security properties, as reflected in our experiments.

###  VI-B EP-MPD Benchmarks

####  VI-B1 Experimental Setup

We designed three experiment settings to benchmark the performance of EP-MPD.
The three settings analyze the effect of the number of clients, dataset size,
and duplication percentage on the runtime of EP-MPD. All experiments were
performed with both $\text{EG-PSI}^{\scriptscriptstyle(\text{I})}$ and
$\text{EG-PSI}^{\scriptscriptstyle(\text{II})}$ as building blocks. The
duplication percentage refers to the percentage of samples in a client's
dataset present in another client's dataset. The three experiment settings
are:

  1. a.

The dataset size is fixed at $|S_{\scriptscriptstyle i}|=2^{\scriptscriptstyle
19}$, the duplication percentage at $30\%$, while the number of clients $m$ is
varied. Specifically, $m$ is set to each value in $\\{10,20,30,40,50\\}$.

  2. b.

The number of clients is fixed at $50$ and the duplication percentage at
$30\%$, while the dataset size $|S_{\scriptscriptstyle i}|$ is varied.
Specifically, $|S_{\scriptscriptstyle i}|$ is set to each value in
$\\{2^{\scriptscriptstyle 10},2^{\scriptscriptstyle 11},2^{\scriptscriptstyle
13},2^{\scriptscriptstyle 15},2^{\scriptscriptstyle 17},2^{\scriptscriptstyle
19}\\}$.

  3. c.

The database size $|S_{\scriptscriptstyle i}|$ is fixed at
$2^{\scriptscriptstyle 19}$, the number of clients at $50$, while the
duplication percentage is varied. Specifically, it is set to each value in
$\\{10\%,30\%,50\%,70\%,90\%\\}$.

We create pairwise duplicates between clients such that every client has a
unique duplicate element with every other client. All set elements are 32-bit
integers. We assume that the $\mathcal{TEE}$ can receive data in parallel from
the clients. All other interactions that require computation between
$\mathcal{TEE}$ and clients occur sequentially. In the remainder of this
section, by $\text{EP-MPD}^{\scriptscriptstyle(\text{I})}$ and $\text{EP-
MPD}^{\scriptscriptstyle(\text{II})}$ we mean the EP-MPD that uses $\text{EG-
PSI}^{\scriptscriptstyle(\text{I})}$ and $\text{EG-
PSI}^{\scriptscriptstyle(\text{II})}$ respectively.

####  VI-B2 Effect of Client Count

Figure 6 depicts the effect of the number of clients on (a) EP-MPD running
time, (b) the average running time of clients, and (c) $\mathcal{TEE}$ running
time. Figure 6(a) demonstrates that the EP-MPD running time increases linearly
with the number of clients for both $\text{EP-
MPD}^{\scriptscriptstyle(\text{I})}$ and $\text{EP-
MPD}^{\scriptscriptstyle(\text{II})}$. The increase in the client count rises
the number of PRP and OPRF evaluations as the total number of elements across
all clients grows. We observe that $\text{EP-
MPD}^{\scriptscriptstyle(\text{I})}$ is about $7\mbox{--}10\times$ faster than
$\text{EP-MPD}^{\scriptscriptstyle(\text{II})}$.

The average running time of the client however shows a different trend. The
client running time in $\text{EP-MPD}^{\scriptscriptstyle(\text{I})}$
increases linearly with the client count and is always greater than – up to
$6\times$ – the running time of $\text{EP-
MPD}^{\scriptscriptstyle(\text{II})}$. The running time of $\text{EP-
MPD}^{\scriptscriptstyle(\text{II})}$ is constant as the number of clients
increases. In $\text{EP-MPD}^{\scriptscriptstyle(\text{I})}$, the client-side
running time increases with the number of clients, because each client has to
perform more PRP evaluations. However, in $\text{EP-
MPD}^{\scriptscriptstyle(\text{II})}$, the number of OPRF evaluations is equal
to the number of elements in each client's set. Additionally, in $\text{EP-
MPD}^{\scriptscriptstyle(\text{I})}$, the clients perform the PRP evaluations
at every level of the tree. However, in $\text{EP-
MPD}^{\scriptscriptstyle(\text{II})}$ the OPRF evaluations are only performed
once when the clients are at the leaf level.

The running time of $\mathcal{TEE}$ follows a similar trend to the EP-MPD
running time. The $\mathcal{TEE}$ running time in $\text{EP-
MPD}^{\scriptscriptstyle(\text{II})}$ is always higher than $\text{EP-
MPD}^{\scriptscriptstyle(\text{I})}$. Both exhibit linear increases in running
time as the number of clients increases. The running time in $\text{EP-
MPD}^{\scriptscriptstyle(\text{II})}$ is much higher as the OPRF evaluations
are relatively expensive.

(a) EP-MPD running time.

(b) Client running time.

(c) $\mathcal{TEE}$ running time.

Figure 6: Effect of client count with $2^{\scriptscriptstyle 19}$ dataset size
and $30\%$ duplication percentage on running time (logarithmic scale).

####  VI-B3 Effect of Dataset Size

Figure 7 illustrates the effect of dataset size on EP-MPD running time, the
average running time of clients, and $\mathcal{TEE}$ running time. From Figure
7(a), it is evident that the EP-MPD running time grows linearly with
increasing the dataset size. $\text{EP-MPD}^{\scriptscriptstyle(\text{I})}$ is
up to $8\times$ faster than $\text{EP-MPD}^{\scriptscriptstyle(\text{II})}$.
As the dataset size increases, the number of PRP and OPRF evaluations grows,
thereby increasing the EP-MPD running time.

Figure 7(b) shows the effect of dataset size on client running time. Unlike
increasing the client count, increasing the dataset size increases the client
running time of both $\text{EP-MPD}^{\scriptscriptstyle(\text{I})}$ and
$\text{EP-MPD}^{\scriptscriptstyle(\text{II})}$. We observe this difference
because an increase in dataset size increases the number of OPRF evaluations
while any change in the client count does not. The client running time of
$\text{EP-MPD}^{\scriptscriptstyle(\text{II})}$ is up to $7\times$ faster than
$\text{EP-MPD}^{\scriptscriptstyle(\text{I})}$.

Figure 7(c) depicts the effect of dataset size on the running time of
$\mathcal{TEE}$. The growth of dataset size increases the OPRF evaluations in
$\text{EP-MPD}^{\scriptscriptstyle(\text{II})}$. In $\text{EP-
MPD}^{\scriptscriptstyle(\text{I})}$, $\mathcal{TEE}$ has to identify more
overlapping ciphertexts as the datasets are larger. The running time of
$\mathcal{TEE}$ increases linearly with the dataset size for both cases.
$\mathcal{TEE}$ running time in $\text{EP-MPD}^{\scriptscriptstyle(\text{I})}$
is up to $5\times$ faster than $\text{EP-
MPD}^{\scriptscriptstyle(\text{II})}$.

(a) EP-MPD running time.

(b) Client running time.

(c) $\mathcal{TEE}$ running time.

Figure 7: Effect of dataset size with 50 clients and $30\%$ duplication
percentage on running time (logarithmic scale).

####  VI-B4 Effect of Duplication Percentage

Figure 8 shows the effect of duplication percentage on EP-MPD running time,
the average running time of clients, and $\mathcal{TEE}$ running time. Figure
8(a) highlights the running time of EP-MPD as the duplication percentage
changes. We note that in $\text{EP-MPD}^{\scriptscriptstyle(\text{II})}$, OPRF
evaluations incur the most overwhelming running time, dominating all other
running time costs. Overall, the running time of $\text{EP-
MPD}^{\scriptscriptstyle(\text{II})}$ is constant while that of $\text{EP-
MPD}^{\scriptscriptstyle(\text{I})}$ linearly decreases as the duplication
rate grows. In $\text{EP-MPD}^{\scriptscriptstyle(\text{II})}$, the number of
OPRF evaluations is independent of the duplication percentage, because the
OPRF is always performed only when the clients are at the leaf level. However,
in $\text{EP-MPD}^{\scriptscriptstyle(\text{I})}$, the number of PRP
invocations decreases as clients move up the tree from the leaf level because
a higher duplication percentage removes more elements in each level of the
tree. The total running time of $\text{EP-MPD}^{\scriptscriptstyle(\text{I})}$
is up to $7\times$ faster than $\text{EP-
MPD}^{\scriptscriptstyle(\text{II})}$.

Furthermore, the client-side running time of $\text{EP-
MPD}^{\scriptscriptstyle(\text{II})}$ is constant while that of $\text{EP-
MPD}^{\scriptscriptstyle(\text{I})}$ linearly decreases as the duplication
percentage increases, as shown in Figure 8(b). The reason is identical to the
observation of the EP-MPD running time. The number of PRP evaluations reduces
while the number of OPRF evaluations does not. Similar to the prior experiment
settings, the client time of $\text{EP-MPD}^{\scriptscriptstyle(\text{I})}$ is
higher than $\text{EP-MPD}^{\scriptscriptstyle(\text{II})}$ and is up to
$7\times$ slower. Figure 8(c) shows the effect of duplication percentage on
the running time of $\mathcal{TEE}$. The $\mathcal{TEE}$ running time in
$\text{EP-MPD}^{\scriptscriptstyle(\text{II})}$ is constant while in
$\text{EP-MPD}^{\scriptscriptstyle(\text{I})}$ linearly decreases. The
$\mathcal{TEE}$ running time in $\text{EP-MPD}^{\scriptscriptstyle(\text{I})}$
is up to $2\times$ faster than $\text{EP-
MPD}^{\scriptscriptstyle(\text{II})}$.

The overall running time of the symmetric key-based $\text{EP-
MPD}^{\scriptscriptstyle(\text{I})}$ is considerably less than the public key-
based $\text{EP-MPD}^{\scriptscriptstyle(\text{II})}$. Nevertheless, the
clients in $\text{EP-MPD}^{\scriptscriptstyle(\text{I})}$ need to perform more
computations compared to those in $\text{EP-
MPD}^{\scriptscriptstyle(\text{II})}$.

(a) EP-MPD running time.

(b) Client running time.

(c) $\mathcal{TEE}$ running time.

Figure 8: Effect of duplication percentage with $2^{\scriptscriptstyle 19}$
dataset size and $50$ clients on running time (logarithmic scale).

###  VI-C FL with EP-MPD

####  VI-C1 Experimental Setup

We create an FL setting with varying levels of duplication to analyze the
effect of EP-MPD on the model performance and training efficiency of CLM fine-
tuning. We use GPT-2 Medium and GPT-2 Large CLMs from the GPT-2 [43] family of
decoder-only models based on the Transformer [50] architecture. The GPT-2
Medium has 345 million parameters with 24 decoder blocks, 16 attention heads,
and 1024 hidden sizes while GPT-2 Large has 774 million parameters with 36
decoder blocks, 20 attention heads, and 1280 hidden sizes. Both models have a
sequence length of 1024 tokens.

We create 10 clients and experiment with the following 7 datasets. The Rotten
Tomatoes and IMDB datasets contain movie reviews. The Sonnets and Plays
datasets are a collection of works by William Shakespeare. Poetry is a
collection of short poems by a variety of poets. Haiku and Short Jokes are a
collection of short Japanese-style poems and Jokes from Reddit respectively.
The language modeling task for each dataset is to learn how to generate text
from the dataset's distribution. For all datasets, we create a Train and Test
split in an 80:20 ratio. Model perplexity is evaluated on the Test set after
training. We follow a two-step procedure to create the client datasets with
$x\%$ duplication. Initially, we equally distributed the Train set among all
10 clients. Next, we sample with replacement $x\%$ of the original Train set.
This subset is then again equally distributed among all clients. We perform 5
rounds of FL training with at most 10 epochs of local training. The GPT-2
Large models were trained for fewer epochs and with less data because they
were overfitting to the Train set for more epochs and data. Additional details
about the datasets and FL training hyperparameters can be found in Appendix
-E.

####  VI-C2 FL model performance

We measure the perplexity of the final model on the Test set to assess the
impact of various duplication levels on model performance. Table I shows the
results of perplexity (PP) and improvement rate (IR). IR refers to the
percentage of improvement in perplexity after deduplication. For example, the
Haiku dataset with GPT-2 Medium and 30% duplication shows an IR of 5.36% from
3.73 to 3.53 after deduplication. The deduplicated client datasets represent
the baseline perplexity.

The blue text in the table highlights the largest improvement in perplexity,
which is for the Plays dataset with GPT-2 Medium. We observe an improvement
rate of $19.61\%$ from 34.88 to 28.04 for $30\%$ duplication. The Plays
dataset in general has a higher perplexity than other datasets as it is a
relatively challenging task with longer sequences and fewer training samples.
The impact of duplicates in such scenarios is aggravated. We observe a similar
trend with the Sonnets dataset with a $13.64\%$ improvement rate, which is
also a difficult task with few samples and relatively long sequences.

The purple text highlights the least improvement in perplexity for the Rotten
Tomatoes dataset with GPT-2 Medium. The $10\%$ duplication results in a
$1.7\%$ improvement rate from $3.6$ to $3.53$. Similarly, the Haiku and Short
Jokes datasets exhibit smaller improvement rates across different levels of
duplication, while maintaining low perplexity. We observe these trends because
these datasets are relatively easier to learn with a greater number of
training samples. The impact of duplicates in such cases is not as pronounced.

The red text highlights two scenarios where deduplication results in
insignificant changes ($<1\%)$ to perplexity. The Plays dataset with GPT-2
Medium shows an improvement of $0.28\%$ after deduplication with $10\%$
duplication while the Sonnets dataset with GPT-2 Large worsens by $0.24\%$
after deduplication with $10\%$ duplication. The reason for the ``noisy''
results for the Plays and Sonnets dataset is that both datasets have very few
training data samples. A $10\%$ duplication percentage merely adds $3-5$
duplicated data points to each client. Both datasets, however, show
significant improvements for $20\%$ and $30\%$ duplication.

TABLE I: Test set perplexity (PP) and improvement rate (IR) of perplexity after deduplication. Model | Dataset | Duplication Percentage | Deduplicated
---|---|---|---
30% | 20% | 10%
PP | IR (%) | PP | IR (%) | PP | IR (%) | PP
GPT-2 Medium | Haiku | 3.73 | 5.36 | 3.69 | 4.3 | 3.6 | 1.94 | 3.53
Rotten Tomatoes | 2.4 | 3.75 | 2.36 | 2.18 | 2.35 | 1.7 | 2.31
Short Jokes | 3.95 | 5.31 | 3.89 | 3.85 | 3.83 | 2.34 | 3.74
Poetry | 5.46 | 8.42 | 5.59 | 10.55 | 5.33 | 6.19 | 5.00
IMDB | 12.81 | 4.57 | 12.71 | 3.75 | 12.5 | 2.0 | 12.25
Sonnets | 15.83 | 13.64 | 15.63 | 12.5 | 14.22 | 4.02 | 13.67
Plays | 34.31 | 18.27 | 34.88 | 19.61 | 28.12 | – | 28.04
GPT-2 Large | Haiku | 3.27 | 8.86 | 3.26 | 8.58 | 3.23 | 7.73 | 2.98
Rotten Tomatoes | 2.65 | 16.98 | 2.6 | 15.38 | 2.53 | 13.00 | 2.2
Short Jokes | 4.11 | 7.78 | 4.02 | 5.72 | 3.95 | 4.05 | 3.79
Sonnets | 8.51 | 5.53 | 8.4 | 4.28 | 8.02 | – | 8.04

####  VI-C3 FL model training efficiency

We analyze the model training efficiency by computing the total GPU running
time of all clients during training. The CPU-bound EP-MPD costs are negligible
for 10 clients and at most 5,000 elements (the size of the largest dataset is
50,000 elements distributed among all clients). Table II highlights the
results for GPU running time. The Time column is the total GPU running time
and IR is the percentage improvement compared to the running time within the
deduplicated setting.

The blue text shows the largest improvement in running time of $27.95\%$ from
33.13 minutes to 23.87 minutes in the GPT-2 Medium experiment with the Sonnets
dataset. The purple text highlights the smallest improvement in running time
of $7.33\%$ from 11.87 to 11.0 minutes in the Sonnets experiment with GPT-2
Large.

We observe a relatively consistent improvement trend of approximately $22\%$,
$16\%$, and $8\%$ for $30\%$, $20\%$, and $10\%$ duplication levels
respectively. The GPT-2 Medium experiments show higher running times as these
models were trained longer. We observe that the running time efficiency
consistently improves across all duplication levels and experiments.

Tables I and II demonstrate the effectiveness of applying EP-MPD to FL of
language models. The experiments show improvements of up to $18\%$ in
perplexity and $27\%$ in GPU running time. Deduplication significantly reduces
resource usage while enhancing the quality of FL models. The RTX A6000 GPU
used in our experiments consumes 0.3 kWh of energy. As FL scales to larger
datasets and more clients, the energy savings with EP-MPD become even more
significant, contributing to more sustainable and cost-effective FL
implementations, benefiting both the environment and the end-users.

TABLE II: Total GPU training time (minutes) of all clients and improvement rate (IR) of time after deduplication. Model | Dataset | Duplication Percentage | Deduplicated
---|---|---|---
30% | 20% | 10%
Time | IR (%) | Time | IR (%) | Time | IR (%) | Time
GPT-2 Medium | Haiku | 111.92 | 22.96 | 105.03 | 17.91 | 95.62 | 9.83 | 86.22
Rotten Tomatoes | 162.79 | 21.7 | 151.54 | 15.89 | 138.76 | 8.14 | 127.46
Short Jokes | 396.62 | 27.85 | 338.69 | 15.51 | 313.35 | 8.68 | 286.15
Poetry | 114.28 | 22.65 | 105.48 | 16.2 | 96.85 | 8.74 | 88.39
IMDB | 2133.36 | 22.56 | 2006.94 | 17.68 | 1788.11 | 7.61 | 1652.04
Sonnets | 33.13 | 27.95 | 28.53 | 16.33 | 26.14 | 8.68 | 23.87
Plays | 31.48 | 22.9 | 29.38 | 17.39 | 26.95 | 9.94 | 24.27
GPT-2 Large | Haiku | 20.89 | 22.98 | 19.28 | 16.55 | 17.7 | 9.1 | 16.09
Rotten Tomatoes | 70.74 | 23.08 | 65.26 | 16.63 | 59.91 | 9.18 | 54.41
Short Jokes | 340.75 | 22.93 | 313.65 | 16.27 | 288.86 | 9.08 | 262.63
Sonnets | 13.91 | 20.92 | 12.89 | 14.66 | 11.87 | 7.33 | 11.0

##  VII Asymptotic Costs Analysis

In this section, we analyze the asymptotic costs of our schemes. Table III
summarizes the result.

TABLE III:  Complexities of our solutions; namely, $\text{EG-
PSI}^{\scriptscriptstyle(\text{I})}$, $\text{EG-
PSI}^{\scriptscriptstyle(\text{II})}$, and EP-MPD. In the table, we have
considered the maximum communication complexity of a client in EP-MPD (without
considering the cases where the updates reduce the clients' set size). In the
table, $m$ is the number of clients in each group, $|{S}|$ is the maximum
cardinality of sets, and $|R|$ is the maximum cardinality of sets intersection
that a client has with clients of the other group.

Protocols | Computation Cost | Communication Cost
---|---|---
Client | $\mathcal{TEE}$ | Client | $\mathcal{TEE}$
$\text{EG-PSI}^{\scriptscriptstyle(\text{I})}$ | $O(m\cdot|{S}_{\scriptscriptstyle j,i}|)$ | $O(m\cdot|{S}|)$ | $O(m\cdot|S_{\scriptscriptstyle j,i}|)$ | $O(m\cdot|R|)$
$\text{EG-PSI}^{\scriptscriptstyle(\text{II})}$ | $O(m\cdot|{S}|)$ | $O(m\cdot|S|)$ | $O(m\cdot|{S}_{\scriptscriptstyle j,i}|)$ | $O(m\cdot|{S}|)$
EP-MPD | $O(m\cdot\log_{\scriptscriptstyle 2}(m)\cdot|S|)$ | $O(m\cdot\log_{\scriptscriptstyle 2}(m)\cdot|S|)$ | $O(m\cdot\log_{\scriptscriptstyle 2}(m)\cdot|{S}_{\scriptscriptstyle j,i}|)$ | $O(m\cdot\log_{\scriptscriptstyle 2}(m)\cdot|{S}|)$

###  VII-A Costs of $\text{EG-PSI}^{\scriptscriptstyle(\text{I})}$ and
$\text{EG-PSI}^{\scriptscriptstyle(\text{II})}$

####  VII-A1 Computation Cost

Initially, we focus on the computation cost of parties in $\text{EG-
PSI}^{\scriptscriptstyle(\text{I})}$. In step 1b, each client
$\mathcal{C}_{\scriptscriptstyle j,i}$ encrypts each element of its set using
the symmetric key encryption $\mathtt{PRP}$, under each key it agrees with the
clients in the other group. Specifically, it invokes $\mathtt{PRP}$
$m\cdot|{S}_{\scriptscriptstyle j,i}|$ times, where $m$ is the total number of
clients in the other group. In step 3, each client
$\mathcal{C}_{\scriptscriptstyle j,i}$ invokes $\mathtt{PRP}$
$m\cdot|R_{\scriptscriptstyle j,i}|$ times, where $R_{\scriptscriptstyle j,i}$
is the (encrypted) intersection set. Thus, the computation complexity of each
$\mathcal{C}_{\scriptscriptstyle j,i}$ is $O(m\cdot|{S}_{\scriptscriptstyle
j,i}|)$. The computation complexity of $\mathcal{TEE}$ in step 2 is
$O(m\cdot|{S}|)$, where $|{S}|$ represents the maximum cardinality of sets.
The only computation that $\mathcal{TEE}$ performs is searching to find
duplicated values.

We proceed to analyze the computation cost of parties in $\text{EG-
PSI}^{\scriptscriptstyle(\text{II})}$. In step 2, each client
$\mathcal{C}_{\scriptscriptstyle j,i}$ invokes $|{S}_{\scriptscriptstyle
j,i}|$ times OPRF to encrypt its set elements. In steps 3 and 4, each
$\mathcal{C}_{\scriptscriptstyle j,i}$ performs a search on $m+1$ encrypted
sets, which imposes negligible costs compared to the executions of OPRF. Thus,
the complexity of each $\mathcal{C}_{\scriptscriptstyle j,i}$ is
$O(m\cdot|{S}|)$, where $|{S}|$ is the maximum cardinality of sets.
$\mathcal{TEE}$ invokes an instance of OPRF in step 2 for every set of
elements of each client. Therefore, its computation complexity is
$O(m\cdot|S|)$, where $|S|$ is the maximum cardinality of sets.

####  VII-A2 Communication Cost

We first concentrate on the communication cost of parties in $\text{EG-
PSI}^{\scriptscriptstyle(\text{I})}$. Each client
$\mathcal{C}_{\scriptscriptstyle 0,i}$ in step 1a transmits $m$ keys to the
clients of the other group. Thus, its communication complexity in this step is
$O(m)$. However, the clients in $\mathcal{G}_{\scriptscriptstyle 1}$ do not
transmit any message in this step. In step 1b, each client
$\mathcal{C}_{\scriptscriptstyle j,i}$ of each group, transmits
$m\cdot|{S}_{\scriptscriptstyle j,i}|$ messages to $\mathcal{TEE}$, where the
size of each message is only about $256$ bits. Thus, each client's
communication complexity is $O(m\cdot|S_{\scriptscriptstyle j,i}|)$. On the
other hand, $\mathcal{TEE}$ sends to each client $R_{\scriptscriptstyle j,i}$
which contains the intersection the client has with the clients in the other
group. Thus, the overall communication complexity of $\mathcal{TEE}$ is
$O(m\cdot|R|)$, where $|R|$ is the maximum cardinality of sets intersection
that a client may have with clients of the other group.

We proceed to evaluate the communication complexity of parties in $\text{EG-
PSI}^{\scriptscriptstyle(\text{II})}$. In step 2, each
$\mathcal{C}_{\scriptscriptstyle j,i}$ performs OPRF evaluations on
${S}_{\scriptscriptstyle j,i}$. This procedure imposes
$O(|{S}_{\scriptscriptstyle j,i}|)$ communication cost to the client. In step
3, the communication complexity of each $\mathcal{C}_{\scriptscriptstyle j,i}$
is $O(m\cdot|{S}_{\scriptscriptstyle j,i}|)$ because it sends its encrypted
set to every client in the other group. In step 2, $\mathcal{TEE}$ performs
OPRF evaluations on the elements of each $\mathcal{C}_{\scriptscriptstyle
j,i}$ using OPRF. This procedure imposes $O(m\cdot|{S}|)$ communication cost
to $\mathcal{TEE}$.

###  VII-B Costs of EP-MPD

####  VII-B1 Computation Cost

In step 3, at each level $d$, each client $\mathcal{C}_{\scriptscriptstyle
j,i}$ invokes an instance of EG-PSI. When $\text{EG-
PSI}^{\scriptscriptstyle(\text{I})}$ or $\text{EG-
PSI}^{\scriptscriptstyle(\text{II})}$ is used, then the computation complexity
of $\mathcal{C}_{\scriptscriptstyle j,i}$ in this step is
$O(m\cdot\log_{\scriptscriptstyle 2}(m)\cdot|{S}|)$, where $|{S}|$ is the
maximum cardinality of the clients' sets. In step 4,
$\mathcal{C}_{\scriptscriptstyle j,i}$ updates its set. This involves simply
removing items from its local set and the associated cost is negligible
compared to other costs. Thus, the overall computation complexity of
$\mathcal{C}_{\scriptscriptstyle j,i}$ is $O(m\cdot\log_{\scriptscriptstyle
2}(m)\cdot|S|)$. The computation cost is dominated by the cost of executing
$\mathtt{PRP}$ and OPRF if $\text{EG-PSI}^{\scriptscriptstyle(\text{I})}$ and
$\text{EG-PSI}^{\scriptscriptstyle(\text{II})}$ are used respectively. The
computation complexity of $\mathcal{TEE}$ in either case (when $\text{EG-
PSI}^{\scriptscriptstyle(\text{I})}$ or $\text{EG-
PSI}^{\scriptscriptstyle(\text{II})}$ is used) is
$O(m\cdot\log_{\scriptscriptstyle 2}(m)\cdot|S|)$.

####  VII-B2 Communication Cost

In step 3, at each level $d$, each client $\mathcal{C}_{\scriptscriptstyle
0,i}$ transmits its updated set to an instance of $\text{EG-
PSI}^{\scriptscriptstyle(\text{I})}$ or $\text{EG-
PSI}^{\scriptscriptstyle(\text{II})}$. Therefore, its overall communication
complexity is $O\Big{(}m\cdot\big{(}|{S}_{\scriptscriptstyle
0,i}|+\sum\limits_{\scriptscriptstyle u=2}^{\scriptscriptstyle
d}(|{S}_{\scriptscriptstyle 0,i}|-\sum\limits_{\scriptscriptstyle
u^{\prime}=1}^{\scriptscriptstyle
u-1}|{S}_{\scriptscriptstyle\cap}^{\scriptscriptstyle(u^{\prime})}|)\big{)}\Big{)}$
where $d=\log_{\scriptscriptstyle 2}(m)$ and
$|{S}_{\scriptscriptstyle\cap}^{\scriptscriptstyle(u^{\prime})}|$ is the size
of the intersection that $\mathcal{C}_{\scriptscriptstyle 0,i}$ has with the
clients of the other group at level $u^{\prime}$. On the other hand, at each
level $d$, the communication complexity of each client
$\mathcal{C}_{\scriptscriptstyle 1,i}$ is $O(m\cdot\log_{\scriptscriptstyle
2}(m)\cdot|{S}_{\scriptscriptstyle 1,i}|)$. Note that the majority of the
clients will eventually become members of group 0. Thus, their set size
eventually reduces when they (i) proceed to a higher level in the tree and
(ii) have intersections with other clients' sets.

The communication complexity of $\mathcal{TEE}$, when $\text{EG-
PSI}^{\scriptscriptstyle(\text{I})}$ is used, is
$O(m\cdot\log_{\scriptscriptstyle 2}(m)\cdot|R|)$, where $|R|$ is the maximum
cardinality of sets intersection that a client may have with clients of the
other group. The communication complexity of $\mathcal{TEE}$, when $\text{EG-
PSI}^{\scriptscriptstyle(\text{II})}$ is used, is
$O(m\cdot\log_{\scriptscriptstyle 2}(m)\cdot|{S}|)$.

##  VIII Related Works

A detailed deduplication method has been proposed in [31] that used existing
techniques of finding duplicates such as suffix array [36] and MinHash [10].
However, there were no privacy requirements in this method as the data owner
is responsible for local deduplication. As we consider the problem of
deduplication in a distributive setting, thus our problem statement is
fundamentally different from [31].

In [29], the problem of privacy-preserving deduplication by a centralized
service was discussed – there is a server that stores multiple users' files
after removing duplicates. Their method involves a second server which helps
in setting up keys for each user using an OPRF. Our work is different from
[29] in many ways. First, we apply OPRF for encrypting the dataset elements,
which allows efficient deduplication. Second, our deduplication requirement is
more granular – we want entries of users' datasets to be deduplicated. If the
two datasets have the same elements irrespective of their order, then at the
end of our deduplication, one of the users will receive an empty dataset and
the other will receive their dataset unchanged. On the other hand, since [29]
considers a file as a whole (not every set element), so two files
$M_{\scriptscriptstyle 1}$ and $M_{\scriptscriptstyle 2}$ have the same
elements but in a different order will not be removed. Third, our public key-
based deduplication protocol is federated as opposed to [29] which is
centralized (all data is stored in a centralized server responsible for the
deduplication). Fourth, [29] is a two-server setting – one server helps in
deduplication and the other stores the deduplicated files. In contrast, in our
protocol apart from the users, we only have one third-party.

Another work along the lines of [29] is [33] which proposed Multi-Key
Revealing Encryption (MKRE) that lets a server compress the encrypted files of
multiple users by removing ciphertexts related to similar plaintexts. Their
construction is based on message lock encryption, therefore, it is subject to
dictionary attacks [34]. Our scheme is not vulnerable to such attacks and, as
a result, provides a stronger security guarantee.

The work of [8] also has pointed out the need for data processing for ML and
applied PSI-type tools. However, their problem statement is to find a mismatch
in the datasets belonging to two participants, whereas we are considering
finding duplicates (matching data) in sets belonging to two or more parties.
Additionally, their application domain is narrow as they only considered
labeled data. Their end goal is to find entries in two different sets where
their features match but their corresponding labels do not match. On the other
hand, our protocol supports both labeled and unlabeled data.

##  IX Conclusions

It was established in [31] that machine learning benefits significantly from
deduplication. However, it was not evident how federated learning (FL) could
benefit from deduplication without compromising data privacy. Our successful
and efficient solution to this problem has paved the way for further
applications. Our pioneering protocols, $\text{EG-
PSI}^{\scriptscriptstyle(\text{I})}$ and $\text{EG-
PSI}^{\scriptscriptstyle(\text{II})}$, can be employed in any distributed
system to identify and efficiently remove duplicates. Although this paper
considers elements as duplicates only if they are exact copies, there are
scenarios where elements that are not exact matches but are sufficiently
similar should also be treated as duplicates [31]. Our current primitives can
easily be extended to address this case. By applying fuzzy hash functions,
which map closely related elements to the same digest, the deduplication of
near-match elements can be reduced to the problem of deduplication of exact-
match elements, allowing the use of $\text{EG-
PSI}^{\scriptscriptstyle(\text{I})}$ and $\text{EG-
PSI}^{\scriptscriptstyle(\text{II})}$ in distributed setups. While our
system's application focuses on text-based learning, it can also be extended
to other areas, such as image processing and speech recognition, thereby
broadening its utility and impact.

## References

  * [1] A. Abadi, ``Earn while you reveal: Private set intersection that rewards participants,'' _CoRR_ , 2023.
  * [2] M. Abadi, A. Chu, I. Goodfellow, H. B. McMahan, I. Mironov, K. Talwar, and L. Zhang, ``Deep learning with differential privacy,'' ser. CCS '16, 2016.
  * [3] R. S. Antunes, C. A. da Costa, A. Küderle, I. A. Yari, and B. Eskofier, ``Federated learning for healthcare: Systematic review and architecture proposal,'' _TIST_ , 2022.
  * [4] M. Balunović, D. I. Dimitrov, N. Jovanović, and M. Vechev, ``Lamp: Extracting text from gradients with language model priors,'' 2022. [Online]. Available: https://arxiv.org/abs/2202.08827
  * [5] J. H. Bell, K. A. Bonawitz, A. Gascón, T. Lepoint, and M. Raykova, ``Secure single-server aggregation with (poly)logarithmic overhead,'' ser. CCS, 2020.
  * [6] A. Ben-Efraim, O. Nissenbaum, E. Omri, and A. Paskin-Cherniavsky, ``Psimple: Practical multiparty maliciously-secure private set intersection,'' in _ASIA CCS_ , 2022.
  * [7] E. M. Bender, T. Gebru, A. McMillan-Major, and S. Shmitchell, ``On the dangers of stochastic parrots: Can language models be too big?'' in _FAccT_ , 2021.
  * [8] E. Blass and F. Kerschbaum, ``Private collaborative data cleaning via non-equi psi,'' in _IEEE SP_ , 2023.
  * [9] K. Bonawitz, V. Ivanov, B. Kreuter, A. Marcedone, H. B. McMahan, S. Patel, D. Ramage, A. Segal, and K. Seth, ``Practical secure aggregation for privacy-preserving machine learning,'' in _CCS_ , 2017.
  * [10] A. Z. Broder, ``On the resemblance and containment of documents,'' in _SEQUENCES_ , 1997.
  * [11] J. Burns, D. Moore, K. Ray, R. Speers, and B. Vohaska, ``Ec-oprf: Oblivious pseudorandom functions using elliptic curves,'' Cryptology ePrint Archive, 2017\.
  * [12] N. Carlini, D. Ippolito, M. Jagielski, K. Lee, F. Tramer, and C. Zhang, ``Quantifying memorization across neural language models,'' 2023. [Online]. Available: https://arxiv.org/abs/2202.07646
  * [13] N. Carlini, F. Tramer, E. Wallace, M. Jagielski, A. Herbert-Voss, K. Lee, A. Roberts, T. Brown, D. Song, U. Erlingsson, A. Oprea, and C. Raffel, ``Extracting training data from large language models,'' in _USENIX Security_ , 2021.
  * [14] K. Cheng, T. Fan, Y. Jin, Y. Liu, T. Chen, D. Papadopoulos, and Q. Yang, ``Secureboost: A lossless federated learning framework,'' _IEEE Intelligent Systems_ , 2021.
  * [15] V. A. Dasu, S. Sarkar, and K. Mandal, ``Prov-fl: Privacy-preserving round optimal verifiable federated learning,'' in _Proceedings of the 15th ACM Workshop on Artificial Intelligence and Security_ , ser. AISec'22. New York, NY, USA: Association for Computing Machinery, 2022, p. 33–44. [Online]. Available: https://doi.org/10.1145/3560830.3563729
  * [16] C. Dong, A. Abadi, S. J. Murdoch, and S. Terzis, ``Multi-party updatable delegated private set intersection,'' in _FC_ , 2022.
  * [17] F. Dörre, J. Mechler, and J. Müller-Quade, ``Practically efficient private set intersection from trusted hardware with side-channels,'' in _ASIACRYPT_. Springer, 2023.
  * [18] L. Fowl, J. Geiping, S. Reich, Y. Wen, W. Czaja, M. Goldblum, and T. Goldstein, ``Decepticons: Corrupted transformers breach privacy in federated learning for language models,'' 2023. [Online]. Available: https://arxiv.org/abs/2201.12675
  * [19] M. J. Freedman, K. Nissim, and B. Pinkas, ``Efficient private matching and set intersection,'' in _EUROCRYPT_ , 2004.
  * [20] S. Ghosh and T. Nilges, ``An algebraic approach to maliciously secure private set intersection,'' in _EUROCRYPT_ , 2019.
  * [21] O. Goldreich, _The Foundations of Cryptography - Volume 2, Basic Applications_. Cambridge University Press, 2004.
  * [22] A. Hard, K. Rao, R. Mathews, F. Beaufays, S. Augenstein, H. Eichner, C. Kiddon, and D. Ramage, ``Federated learning for mobile keyboard prediction,'' _CoRR_ , 2018.
  * [23] I. F. Ilyas and X. Chu, _Data Cleaning_. New York, NY, USA: Association for Computing Machinery, 2019.
  * [24] R. Inbar, E. Omri, and B. Pinkas, ``Efficient scalable multiparty private set-intersection via garbled bloom filters,'' in _SCN_ , 2018.
  * [25] J. C. Jiang, B. Kantarci, S. Oktug, and T. Soyata, ``Federated learning in smart city sensing: Challenges and opportunities,'' _Sensors_ , 2020.
  * [26] S. Kamara, P. Mohassel, M. Raykova, and S. Sadeghian, ``Scaling private set intersection to billion-element sets,'' in _FC_ , 2014.
  * [27] N. Kandpal, E. Wallace, and C. Raffel, ``Deduplicating training data mitigates privacy risks in language models,'' 2022. [Online]. Available: https://arxiv.org/abs/2202.06539
  * [28] A. Karamolegkou, J. Li, L. Zhou, and A. Søgaard, ``Copyright violations and large language models,'' 2023. [Online]. Available: https://arxiv.org/abs/2310.13771
  * [29] S. Keelveedhi, M. Bellare, and T. Ristenpart, ``Dupless: Server-aided encryption for deduplicated storage,'' in _USENIX Security_ , 2013.
  * [30] V. Kolesnikov, N. Matania, B. Pinkas, M. Rosulek, and N. Trieu, ``Practical multi-party private set intersection from symmetric-key techniques,'' in _CCS_ , 2017.
  * [31] K. Lee, D. Ippolito, A. Nystrom, C. Zhang, D. Eck, C. Callison-Burch, and N. Carlini, ``Deduplicating training data makes language models better,'' in _Proceedings of the 60th Annual Meeting of the Association for Computational Linguistics_ , 2022.
  * [32] I. Loshchilov and F. Hutter, ``Decoupled weight decay regularization,'' 2019. [Online]. Available: https://arxiv.org/abs/1711.05101
  * [33] D. E. Lucani, L. Nielsen, C. Orlandi, E. Pagnin, and R. Vestergaard, ``Secure generalized deduplication via multi-key revealing encryption,'' in _SCN_ , 2020.
  * [34] ——, ``Secure generalized deduplication via multi-key revealing encryption,'' Cryptology ePrint Archive, Paper 2020/799, 2020. [Online]. Available: https://eprint.iacr.org/2020/799
  * [35] A. L. Maas, R. E. Daly, P. T. Pham, D. Huang, A. Y. Ng, and C. Potts, ``Learning word vectors for sentiment analysis,'' in _Proceedings of the 49th Annual Meeting of the Association for Computational Linguistics: Human Language Technologies_ , 2011.
  * [36] U. Manber and E. W. Myers, ``Suffix arrays: a new method for on-line string searches,'' _SIAM J. Comput._ , 1993.
  * [37] J. Mattern, F. Mireshghallah, Z. Jin, B. Schölkopf, M. Sachan, and T. Berg-Kirkpatrick, ``Membership inference attacks against language models via neighbourhood comparison,'' in _ACL_ , 2023.
  * [38] H. B. McMahan, E. Moore, D. Ramage, and B. A. y Arcas, ``Federated learning of deep networks using model averaging,'' _CoRR_ , 2016.
  * [39] M. Nasr, N. Carlini, J. Hayase, M. Jagielski, A. F. Cooper, D. Ippolito, C. A. Choquette-Choo, E. Wallace, F. Tramèr, and K. Lee, ``Scalable extraction of training data from (production) language models,'' 2023.
  * [40] O. Nevo, N. Trieu, and A. Yanai, ``Simple, fast malicious multiparty private set intersection,'' in _CCS_ , 2021.
  * [41] R. Pass, E. Shi, and F. Tramèr, ``Formal abstractions for attested execution secure processors,'' in _EUROCRYPT_ , 2017.
  * [42] D. A. Patterson, J. Gonzalez, Q. V. Le, C. Liang, L. Munguia, D. Rothchild, D. R. So, M. Texier, and J. Dean, ``Carbon emissions and large neural network training,'' _CoRR_ , 2021.
  * [43] A. Radford, J. Wu, R. Child, D. Luan, D. Amodei, and I. Sutskever, ``Language models are unsupervised multitask learners,'' 2019.
  * [44] C. Raffel, N. Shazeer, A. Roberts, K. Lee, S. Narang, M. Matena, Y. Zhou, W. Li, and P. J. Liu, ``Exploring the limits of transfer learning with a unified text-to-text transformer,'' _J. Mach. Learn. Res._ , 2020.
  * [45] S. Raghuraman and P. Rindal, ``Blazing fast PSI from improved OKVS and subfield VOLE,'' in _CCS_ , 2022.
  * [46] M. R. U. Rashid, V. A. Dasu, K. Gu, N. Sultana, and S. Mehnaz, ``Fltrojan: Privacy leakage attacks against federated language models through selective weight tampering,'' 2024. [Online]. Available: https://arxiv.org/abs/2310.16152
  * [47] E. Strubell, A. Ganesh, and A. McCallum, ``Energy and policy considerations for deep learning in NLP,'' in _ACL_ , 2019.
  * [48] A. Suri, P. Kanani, V. J. Marathe, and D. W. Peterson, ``Subject membership inference attacks in federated learning,'' 2023. [Online]. Available: https://arxiv.org/abs/2206.03317
  * [49] F. Tramèr, F. Zhang, H. Lin, J. Hubaux, A. Juels, and E. Shi, ``Sealed-glass proofs: Using transparent enclaves to prove and sell knowledge,'' in _EuroS &P_, 2017.
  * [50] A. Vaswani, N. Shazeer, N. Parmar, J. Uszkoreit, L. Jones, A. N. Gomez, L. Kaiser, and I. Polosukhin, ``Attention is all you need,'' _CoRR_ , vol. abs/1706.03762, 2017. [Online]. Available: http://arxiv.org/abs/1706.03762
  * [51] Q. Xia, W. Ye, Z. Tao, J. Wu, and Q. Li, ``A survey of federated learning for edge computing: Research problems and solutions,'' _High-Confidence Computing_ , 2021.
  * [52] R. Xu, N. Baracaldo, Y. Zhou, A. Anwar, and H. Ludwig, ``Hybridalpha,'' _AISec_ , 2019.
  * [53] E. Zhang, F. Liu, Q. Lai, G. Jin, and Y. Li, ``Efficient multi-party private set intersection against malicious adversaries,'' in _CCSW_ , 2019.
  * [54] F. Zhang and H. Zhang, ``Sok: A study of using hardware-assisted isolated execution environments for security,'' in _Proceedings of the Hardware and Architectural Support for Security and Privacy 2016_ , 2016.

###  -A Security Proof of $\text{EG-PSI}^{\scriptscriptstyle(\text{I})}$

In this section, we prove the security of $\text{EG-
PSI}^{\scriptscriptstyle(\text{I})}$, i.e., Theorem 1.

###### Proof.

We consider a set of cases where in each case a party is corrupt.

####  -A1 Corrupt Client

In this case, for the sake of simplicity, we focus on the view of a client
$\mathcal{C}_{\scriptscriptstyle 1,i}$ in $\mathcal{G}_{\scriptscriptstyle
1}$. Because the clients of both groups behave the same way, with the main
difference being that a client in $\mathcal{G}_{\scriptscriptstyle 0}$
generates a key and sends it to each client of
$\mathcal{G}_{\scriptscriptstyle 1}$. Thus, the proof asserting the protocol
is secure regarding a corrupt client in $\mathcal{G}_{\scriptscriptstyle 1}$
will imply the security of the same protocol concerning a client in
$\mathcal{G}_{\scriptscriptstyle 0}$.

In the real execution of the protocol, the view of a client,
$\mathcal{C}_{\scriptscriptstyle 1,i}$, is defined as follows:

$\\{\mathsf{View}_{\scriptscriptstyle\mathcal{C}_{\scriptscriptstyle
1,i}}^{\scriptscriptstyle\mathcal{A},\text{EG-
PSI}^{\scriptscriptstyle(\text{I})}}(S,\emptyset)\\}_{\scriptscriptstyle
S}=\\{S_{\scriptscriptstyle 1,i},r_{\scriptscriptstyle
1,i},\vec{k},R_{\scriptscriptstyle 1,i},\vec{v}_{\scriptscriptstyle 1,i}\\},$

where $S$ is the set containing all clients' sets, $r_{\scriptscriptstyle
1,i}$ is the outcome of internal random coins of
$\mathcal{C}_{\scriptscriptstyle 1,i}$, $\vec{k}=[k_{\scriptscriptstyle
i,1},\ldots,k_{\scriptscriptstyle i,m}]$ is a vector of $m$ keys received from
the clients of $\mathcal{G}_{\scriptscriptstyle 0}$, $R_{\scriptscriptstyle
1,i}$ is the encrypted intersection $\mathcal{C}_{\scriptscriptstyle 1,i}$
received from $\mathcal{TEE}$, and $\vec{v}_{\scriptscriptstyle j,i}$ equals
$[\vec{v}_{\scriptscriptstyle j,i,1},\ldots,\vec{v}_{\scriptscriptstyle
j,i,m}]$, each $l$-th vector in $\vec{v}_{\scriptscriptstyle j,i}$ contains
the elements that are common between $\mathcal{C}_{\scriptscriptstyle 1,i}$'s
set and the set that belongs to the $l$-th client in the other group.

We proceed to construct a simulator,
$\mathsf{Sim}_{\scriptscriptstyle\mathcal{C}_{\scriptscriptstyle 1,i}}$, in
the ideal model. The simulator, receiving the client's input
$S_{\scriptscriptstyle 1,i}$ and output $\vec{v}_{\scriptscriptstyle 1,i}$,
operates as follows.

  1. 1.

initiates an empty view. It appends to it $S_{\scriptscriptstyle 1,i}$ and
uniformly random coins $r^{\prime}_{\scriptscriptstyle 1,i}$.

  2. 2.

constructs an empty vector $\vec{k}^{\prime}$ and then chooses $m$ keys for
$\mathtt{PRP}$. It appends the keys to $\vec{k}^{\prime}$ and adds
$\vec{k}^{\prime}$ to the view.

  3. 3.

constructs an empty set $R^{\prime}$. It encrypts the elements of every $l$-th
vector $\vec{v}_{\scriptscriptstyle 1,i,l}\in\vec{v}_{\scriptscriptstyle 1,i}$
using $l$-th key $k_{\scriptscriptstyle l}$ in $\vec{k}^{\prime}$ and
$\mathtt{PRP}$. It inserts the ciphertexts into $R^{\prime}$.

  4. 4.

appends $R^{\prime}$ and $\vec{v}_{\scriptscriptstyle 1,i}$ to the view. It
outputs the view.

Now, we are prepared to discuss that the two views are computationally
indistinguishable. The input set $S_{\scriptscriptstyle 1,i}$ has identical
distribution in both models, as their elements are identical. Furthermore,
since we are in the semi-honest model, in the real execution of the protocol,
the client picks its random coins $r_{\scriptscriptstyle 1,i}$ according to
the protocol description. In the ideal model, coins
$r^{\prime}_{\scriptscriptstyle 1,i}$ have been selected uniformly at random.
Therefore $r_{\scriptscriptstyle 1,i}$ and $r^{\prime}_{\scriptscriptstyle
1,i}$ have identical distributions. Vectors $\vec{k}$ and $\vec{k}^{\prime}$
have identical distributions too because their elements have been chosen
uniformly at random.

In the real model, $R_{\scriptscriptstyle 1,i}$ contains the encrypted
elements of $\vec{v}_{\scriptscriptstyle 1,i}$, where the keys in $\vec{k}$
are used for the encryption by applying the $\mathtt{PRP}$. Similarly, in the
ideal model, each element of $R^{\prime}$ is the encryption of an element in
$\vec{v}_{\scriptscriptstyle 1,i}$ where a key in $\vec{k}^{\prime}$ is used
for the encryption with the same $\mathtt{PRP}$. Thus, $R$ and $R^{\prime}$
have identical distributions. Furthermore, elements of
$\vec{v}_{\scriptscriptstyle 1,i}$ are identical in both models; therefore,
they have identical distributions in the real and ideal models.

We conclude that the views in the real and ideal models are indistinguishable.

####  -A2 Corrupt $\mathcal{TEE}$

In the real model, the view of $\mathcal{TEE}$ is as follows:

$\\{\mathsf{View}_{\scriptscriptstyle\mathcal{TP}}^{\scriptscriptstyle\mathcal{A},\Gamma}(S,\emptyset)\\}_{\scriptscriptstyle
S}=\\{({S}^{\prime}_{\scriptscriptstyle
0,1},\ldots,{S}^{\prime}_{\scriptscriptstyle
0,m}),({S}^{\prime}_{\scriptscriptstyle
1,1},\ldots,{S}^{\prime}_{\scriptscriptstyle 1,m})\\}$

where each ${S}^{\prime}_{\scriptscriptstyle j,i}$ contains the encrypted set
elements of client $\mathcal{C}_{\scriptscriptstyle j,i}$. Next, we construct
a simulator $\mathsf{Sim}^{\scriptscriptstyle\mathcal{L}}_{\mathcal{TEE}}$
that receives the output $\vec{s}$ of leakage function $\mathcal{L}$ (as
defined in Definition 4).

  1. 1.

initiates an empty view.

  2. 2.

constructs $m$ empty sets for each $\mathcal{G}_{\scriptscriptstyle 0}$ and
$\mathcal{G}_{\scriptscriptstyle 1}$. Specifically, it constructs empty sets
$(\underbrace{{S}^{\prime\prime}_{\scriptscriptstyle
0,1},\ldots,{S}^{\prime\prime}_{\scriptscriptstyle
0,m}}_{\scriptscriptstyle\mathcal{G}_{\scriptscriptstyle
0}}),(\underbrace{{S}^{\prime\prime}_{\scriptscriptstyle
1,1},\ldots,{S}^{\prime\prime}_{\scriptscriptstyle
1,m}}_{\scriptscriptstyle\mathcal{G}_{\scriptscriptstyle 1}})$.

  3. 3.

fills each set ${S}^{\prime\prime}_{\scriptscriptstyle j,i}$ as follows, given
that $\vec{s}=[\vec{s}_{\scriptscriptstyle
0,1},\ldots,\vec{s}_{\scriptscriptstyle 0,m},\vec{s}_{\scriptscriptstyle
1,1},$ $\ldots,\vec{s}_{\scriptscriptstyle 1,m}]$, where
$\vec{s}_{\scriptscriptstyle j,i}=\Big{[}\big{|}[{S}_{\scriptscriptstyle
j,i}\cap{S}_{\scriptscriptstyle
1-j,1}]\big{|},\ldots,\big{|}[{S}_{\scriptscriptstyle
j,i}\cap{S}_{\scriptscriptstyle 1-j,m}]\big{|}\Big{]}$, as defined in
Definition 3.

    1. (a)

for every $y$-th element of each $\vec{s}_{\scriptscriptstyle 0,i}$ (where
$1\leq i,y\leq m$) picks $\vec{s}_{\scriptscriptstyle 0,i}[y]$ random values
(from the range of $\mathtt{PRP}$). It appends these random values to both
sets ${S}^{\prime\prime}_{\scriptscriptstyle 0,i}$ and
${S}^{\prime\prime}_{\scriptscriptstyle 1,y}$.

    2. (b)

pads every set ${S}^{\prime\prime}_{\scriptscriptstyle j,i}$ with some random
values (from the range of $\mathtt{PRP}$) such that the size of each
${S}^{\prime\prime}_{\scriptscriptstyle j,i}$ after padding equals the size of
${S}^{\prime}_{\scriptscriptstyle j,i}$.

  4. 4.

appends sets $({{S}^{\prime\prime}_{\scriptscriptstyle
0,1},\ldots,{S}^{\prime\prime}_{\scriptscriptstyle
0,m}}),({{S}^{\prime\prime}_{\scriptscriptstyle
1,1},\ldots,{S}^{\prime\prime}_{\scriptscriptstyle 1,m}})$ to the view and
outputs the view.

We proceed to demonstrate that the views in the real and ideal models are
computationally indistinguishable. In the real model, each elements of a set
$S^{\prime}_{\scriptscriptstyle j,i}$ is an output of $\mathtt{PRP}$. However,
in the ideal model, each element of a set
$S^{\prime\prime}_{\scriptscriptstyle j,i}$ has been picked uniformly at
random (from the range of $\mathtt{PRP}$). By the security of $\mathtt{PRP}$
(i.e., an output of $\mathtt{PRP}$ is computationally indistinguishable from a
random value), sets' elements in the real and ideal model are computationally
indistinguishable.

Moreover, the size of the intersection between each set
$S^{\prime}_{\scriptscriptstyle 0,i}$ and each set
$S^{\prime}_{\scriptscriptstyle 1,l}$ (in the real model) equals the size of
the intersection between each set $S^{\prime\prime}_{\scriptscriptstyle 0,i}$
and each set $S^{\prime\prime}_{\scriptscriptstyle 1,l}$ (in the ideal model).
Furthermore, the size of each $S^{\prime}_{\scriptscriptstyle j,i}$ in the
real model equals the size of the corresponding set
$S^{\prime\prime}_{\scriptscriptstyle j,i}$ in the ideal model. Hence, sets
${S}^{\prime}_{\scriptscriptstyle 0,1},\ldots,{S}^{\prime}_{\scriptscriptstyle
0,m},{S}^{\prime}_{\scriptscriptstyle
1,1},\ldots,{S}^{\prime}_{\scriptscriptstyle 1,m}$ in the real model are
computationally indistinguishable from sets
${S}^{\prime\prime}_{\scriptscriptstyle
0,1},\ldots,{S}^{\prime\prime}_{\scriptscriptstyle
0,m},{S}^{\prime\prime}_{\scriptscriptstyle
1,1},\ldots,{S}^{\prime\prime}_{\scriptscriptstyle 1,m}$ in the ideal model.

Thus, the views in the real and ideal models are computationally
indistinguishable. ∎

###  -B Security Proof of $\text{EG-PSI}^{\scriptscriptstyle(\text{II})}$

###### Proof (sketch).

It is not hard to simulate parties' views. $\mathcal{TEE}$'s view in the real
model can be easily simulated given that the main information it learns within
the protocol execution includes its view during the invocation of the OPRF
instances (but not the outputs of OPRF). If OPRF is secure, then the views of
$\mathcal{TEE}$ within the real and ideal model will be computationally
indistinguishable in this protocol.

Each client's view (in the real execution of the protocol) mainly includes the
outputs of OPRF received from its counterparts and the exchanged messages
during OPRF's execution with $\mathcal{TEE}$. Due to the security of OPRF, an
output of OPRF is computationally indistinguishable from a value picked
uniformly at random from the output range of OPRF. Also, the messages each
client receives during the execution of OPRF can be simulated, due to the
security of OPRF. ∎

###  -C Security Proof of EP-MPD

In this section, we prove the security of EP-MPD, i.e., Theorem 3. For the
sake of concreteness and because we have provided a detailed proof for
$\text{EG-PSI}^{\scriptscriptstyle(\text{I})}$, we will prove Theorem 3 when
EP-MPD relies on $\text{EG-PSI}^{\scriptscriptstyle(\text{I})}$. The proof for
$\text{EG-PSI}^{\scriptscriptstyle(\text{I})}$-based EP-MPD will easily
follow.

###### Proof.

In the real execution of the protocol, the view of a client,
$\mathcal{C}_{\scriptscriptstyle i}$, is defined as follows:

$\\{\mathsf{View}_{\scriptscriptstyle\mathcal{C}_{\scriptscriptstyle
i}}^{\scriptscriptstyle\mathcal{A},\text{EP-MPD}}(S)\\}_{\scriptscriptstyle
S}=\\{S_{\scriptscriptstyle
i},\vec{\mathsf{View}}_{\scriptscriptstyle\mathcal{C}_{\scriptscriptstyle
i}},\vec{v}_{\scriptscriptstyle i}\\}$

where $S=\\{{S}_{\scriptscriptstyle 1},\ldots,{S}_{\scriptscriptstyle m}\\}$,
${S}_{\scriptscriptstyle i}$ represents a set belonging to client
$\mathcal{C}_{\scriptscriptstyle i}$,
$\vec{\mathsf{View}}_{\scriptscriptstyle\mathcal{C}_{\scriptscriptstyle
i}}=[\mathsf{View}_{\scriptscriptstyle\mathcal{C}_{\scriptscriptstyle
i},1}^{\scriptscriptstyle\mathcal{A},\text{EG-
PSI}^{\scriptscriptstyle(\text{I})}},\ldots,\mathsf{View}_{\scriptscriptstyle\mathcal{C}_{\scriptscriptstyle
i},z}^{\scriptscriptstyle\mathcal{A},\text{EG-
PSI}^{\scriptscriptstyle(\text{I})}}]$ contains $z=log_{\scriptscriptstyle
2}(m)$ views of $\mathcal{C}_{\scriptscriptstyle i}$ such that each view
$\mathsf{View}_{\scriptscriptstyle\mathcal{C}_{\scriptscriptstyle
i},d}^{\scriptscriptstyle\mathcal{A},\text{EG-
PSI}^{\scriptscriptstyle(\text{I})}}$ corresponds to
$\mathcal{C}_{\scriptscriptstyle i}$'s view when it invokes $\text{EG-
PSI}^{\scriptscriptstyle(\text{I})}$ at level $d$, where $1\leq d\leq z$.
Moreover, $\vec{v}_{\scriptscriptstyle i}$ contains $z$ vectors, where each
vector $\vec{v}_{\scriptscriptstyle i,d}$ in $\vec{v}_{\scriptscriptstyle i}$
is the output of $\text{EG-PSI}^{\scriptscriptstyle(\text{I})}$ that client
$\mathcal{C}_{\scriptscriptstyle i}$ receives at level $d$.

We proceed to construct a simulator,
$\mathsf{Sim}_{\scriptscriptstyle\mathcal{C}_{\scriptscriptstyle i}}$, in the
ideal model. The simulator, receives the output $Q_{\scriptscriptstyle i}$ of
leakage function $\mathcal{W}$ (as defined in Definition 6), the client's
input $S_{\scriptscriptstyle i}$ and output $\vec{v_{\scriptscriptstyle i}}$.
$\mathsf{Sim}_{\scriptscriptstyle\mathcal{C}_{\scriptscriptstyle i}}$ operates
as follows.

  1. 1.

initiates an empty view.

  2. 2.

for each level $d$ (where $1\leq d\leq z$) constructs the following set for
each client $\mathcal{C}_{\scriptscriptstyle l}$ in the other group, using (i)
the result $\vec{v}_{\scriptscriptstyle i,d}$ that
$\mathcal{C}_{\scriptscriptstyle i}$ receives at level $d$ and (ii) the
leakage function's output $Q_{\scriptscriptstyle i}$ (hence in total, in level
$d$, the simulator will generate $\frac{2^{\scriptscriptstyle d}}{2}$ sets on
behalf of the clients in the other group).

    1. (a)

constructs an empty set $S_{\scriptscriptstyle l}$.

    2. (b)

finds every triple $(x,a,b)$ in $Q_{\scriptscriptstyle i}$, such that $a=i$
and $b=l$. It adds the first element $x$ of each triple that meets the above
conditions to $S_{\scriptscriptstyle l}$. This ensures that
$S_{\scriptscriptstyle l}$ contains all the elements in common with
$S_{\scriptscriptstyle i}$.

    3. (c)

pads every set ${S}_{\scriptscriptstyle l}$ with some random values (from the
set universe) such that the size of each ${S}_{\scriptscriptstyle l}$, in the
ideal model, after padding equals the size of ${S}_{\scriptscriptstyle l}$ in
the real model.

  3. 3.

generates $\frac{2^{\scriptscriptstyle d}}{2}-1$ empty sets for the group to
which $S_{\scriptscriptstyle i}$ belongs. It appends to these empty sets
values picked uniformly at random from the set universe. It ensures the size
of each of these sets in the ideal model equals to that of in the real model.

  4. 4.

for every level $d$:

    1. (a)

invokes an instance of $\text{EG-PSI}^{\scriptscriptstyle(\text{I})}$ using
the following sets: (i) $S_{\scriptscriptstyle i}$ and sets generated in step
3, that are placed in one group and (ii) sets generated in step 2, placed in
another group. As a result, it receives output $\vec{v}_{\scriptscriptstyle
i,d}$.

    2. (b)

extracts $\mathcal{C}_{\scriptscriptstyle i}$'s view
$\mathsf{View}_{\scriptscriptstyle\mathcal{C}_{\scriptscriptstyle
i},d}^{\scriptscriptstyle\mathcal{A},\text{EG-
PSI}^{\scriptscriptstyle(\text{I})}}$ after the execution of $\text{EG-
PSI}^{\scriptscriptstyle(\text{I})}$.

    3. (c)

appends every
$\mathsf{View}_{\scriptscriptstyle\mathcal{C}_{\scriptscriptstyle
i},d}^{\scriptscriptstyle\mathcal{A},\text{EG-
PSI}^{\scriptscriptstyle(\text{I})}}$ and $\vec{v}_{\scriptscriptstyle i,d}$
to its view.

    4. (d)

outputs the view.

Now, we are prepared to show that the two views (in the real and ideal models)
are computationally indistinguishable. The input $S_{\scriptscriptstyle i}$ in
both models are identical, therefore they will have identical distribution.

Due to the security of $\text{EG-PSI}^{\scriptscriptstyle(\text{I})}$, for
every level $d$,
$\mathsf{View}_{\scriptscriptstyle\mathcal{C}_{\scriptscriptstyle
i},d}^{\scriptscriptstyle\mathcal{A},\text{EG-
PSI}^{\scriptscriptstyle(\text{I})}}$ in the real and ideal models are
computationally indistinguishable, as demonstrated in the proof of Theorem 1.
Furthermore, the intersection $\vec{v}_{\scriptscriptstyle i,d}$ that
$\mathcal{A}$ learns at every level $d$ in the real and ideal model are
identical, thus they are indistinguishable.

Hence, the views of $\mathcal{A}$ in the real and ideal models are
computationally indistinguishable. ∎

###  -D Related Work in PSI Research

Since their introduction in [19], numerous PSIs have been designed. In
general, PSIs fall into two broad categories traditional and delegated. In
traditional PSIs, clients (i.e., data owners) compute the result interactively
using their data stored locally. In this research line, researchers in [45]
introduced two two-party PSIs, one secure against semi-honest and the other
against malicious (or active) adversaries. These protocols are the fastest
two-party PSIs to date. They use Oblivious Key-Value Stores (OKVS) data
structure and Vector Oblivious Linear Evaluation (VOLE). These solutions'
computation cost is $O(c)$, where $c$ is a set's cardinality. They also impose
$O(c\log c^{\scriptscriptstyle 2}+\kappa)$ and $O(c\cdot\kappa)$ communication
costs in the semi-honest and malicious models respectively, where $\kappa$ is
a security parameter.

Dorre et al. [17] proposed an efficient two-party PSI that requires each party
to locally posses a secure hardware, a requirement that may not always be
possible to meet. The scheme further relies on a hash function and
deterministic symmetric-key encryption. The scheme's communication complexity
is $O(poly(\kappa)+|S|\lambda)$ and its computation complexity is
$O((2\cdot|S|)\cdot poly(\kappa\cdot l))$, where $l$ is a set element's bit
size and $\lambda$ is a security parameter. As the authors stated, the
protocol cannot directly support multiple more than two parties.

Furthermore, researchers developed PSIs that allows multiple (i.e., more than
two) parties to compute the intersection. The multi-party PSIs in [24, 30] are
secure against semi-honest adversaries while those proposed in [6, 20, 53, 30,
40] were developed to remain secure against active ones. The protocols in [30]
and [40] are the most efficient multi-party PSIs designed to be secure against
passive and active adversaries respectively. The computation and communication
complexities of the PSI in [30] are $O(c\cdot m^{\scriptscriptstyle 2}+c\cdot
m)$ and $O(c\cdot m^{\scriptscriptstyle 2})$. The PSI in [40] has a parameter
$t$ that determines how many parties can collude with each other and must be
set before the protocol's execution, where $t\in[2,m)$. Its computation and
communication complexities are $O(c\cdot\kappa(m+t^{\scriptscriptstyle
2}-t(m+1)))$ and $O(c\cdot m\cdot\kappa)$ respectively.

Delegated PSIs use cloud computing for computation and/or storage. These PSIs
can be further categorized into those that allow one-off and repeated
delegation of PSI computation. The most efficient one that supports one-off
delegation is [26], designed for the two-party setting, with an overhead of
$O(c)$. Researchers also proposed a multi-party PSI that supports repeated
delegation and efficient _updates_ [16]. It imposes $O(h\cdot
d^{\scriptscriptstyle 2}\cdot m)$ and $O(h\cdot d\cdot m)$ computation and
communication costs respectively, during the PSI computation. Furthermore, to
incentivize clients to participate in a PSI protocol and share their sensitive
inputs, researchers proposed a PSI that rewards participants [1].

Thus, despite the development of numerous two-party and multiple-party PSIs,
none of them to date can match the features offered by our PSIs.

###  -E Datasets and FL Hyperparameters

We use the following datasets in our study:

  1. 1.

Haiku222https://www.kaggle.com/datasets/bfbarry/haiku-dataset: This dataset
contains 15,281 Haikus scraped from ``reddit.com/r/haiku''. Haiku is a
Japanese style of short poetry.

  2. 2.

Rotten Tomatoes333https://huggingface.co/datasets/cornell-movie-review-
data/rotten_tomatoes: It contains 10,662 movie reviews from the Rotten
Tomatoes movie critic website. Originally intended for sentiment analysis, the
dataset has 5,331 positive and negative reviews each. In our experiments, we
ignore the sentiment of the reviews and train the CLM only on the review.

  3. 3.

Short Jokes444https://www.kaggle.com/datasets/abhinavmoudgil95/short-jokes: It
contains 231,657 jokes scraped from Reddit. We randomly sample 50,000 jokes
for our experiments.

  4. 4.

Poetry555https://huggingface.co/datasets/merve/poetry: It contains 573 poems
from the Renaissance and Modern eras by various poets.

  5. 5.

IMDB [35]: This dataset contains 50,000 movie reviews from the IMDB movie
critic website. Similar to the Rotten Tomatoes dataset, the IMDB dataset was
originally intended for sentiment analysis. We ignore the sentiment of each
review and only train the CLM on the review.

  6. 6.

Sonnets666https://huggingface.co/datasets/Lambent/shakespeare_sonnets_diffused:
This dataset contains 460 sonnets (including variations) from William
Shakespeare. Sonnets are 14-line poems with variable rhyme schemes

  7. 7.

Plays777https://huggingface.co/datasets/Trelis/tiny-shakespeare: It contains
521 plays from William Shakespeare.

We train the GPT-2 Medium and GPT-2 Large models for $5\text{--}10$ and
$1\text{--}2$ local epochs respectively. Both models are trained for 5 rounds.
The Haiku GPT-2 Large was trained for 1 epoch while the other GPT-2 Large
models were trained for 2 epochs. The Poetry and Sonnets GPT-2 Medium models
were trained for 10 epochs while the others were trained for 5 epochs. We
observe that training GPT-2 Large for more epochs and data results in
overfitting and poor Test set perplexity across all duplication levels.

For all experiments, we use a learning of $5\times 10^{\scriptscriptstyle-5}$
with the AdamW [32] optimizer. We use a linear warm-up schedule with 10% of
the training steps as warm-up steps. We use $\ell_{\scriptscriptstyle 2}$-norm
clipping for the gradients and set the threshold to 1.0. We set the sequence
length for the datasets as follows:

  1. 1.

Haiku: 100

  2. 2.

Rotten Tomatoes: 200

  3. 3.

Short Jokes: 100

  4. 4.

Poetry: 1000

  5. 5.

IMDB: 500

  6. 6.

Sonnets: 400

  7. 7.

Plays: 1000

For the Short Jokes dataset, we randomly sample 50,000 elements to ensure the
running time is feasible as we train with 10 clients. We set the batch size to
values in the range $[4,32]$, depending on the sequence length and model size
to ensure that training can be performed on one RTX A6000 GPU. We use a
Train/Test split of 80/20 for all datasets. In the case of datasets like IMDB
that have a separate Test set, we combine the original Train and Test sets
into a single dataset, shuffle it, and then create 80:20 splits. We fix the
random seed to 123 for the Numpy, PyTorch, and Python random number generators
to ensure the reproducibility of our results.