Sherpa.ai Privacy-Preserving Multi-Party Entity Alignment without Intersection Disclosure for Noisy Identifiers
arXiv:2604.19219v1 [cs.CR] 21 Apr 2026
Sherpa.ai [email protected]
Abstract Federated Learning (FL) enables collaborative model training among multiple parties without centralizing raw data. There are two main paradigms in FL: Horizontal FL (HFL), where all participants share the same feature space but hold different samples, and Vertical FL (VFL), where parties possess complementary features for the same set of samples. A prerequisite for VFL training is privacy-preserving entity alignment (PPEA), which establishes a common index of samples across parties (alignment) without revealing which samples are shared between them. Conventional private set intersection (PSI) achieves alignment but leaks intersection membership, exposing sensitive relationships between datasets. The standard private set union (PSU) mitigates this risk by aligning on the union of identifiers rather than the intersection. However, existing approaches are often limited to two parties or lack support for typo-tolerant matching. In this paper, we introduce the Sherpa.ai multi-party PSU protocol for VFL, a PPEA method that hides intersection membership and enables both exact and noisy matching. The protocol generalizes two-party approaches to multiple parties with low communication overhead and offers two variants: an order-preserving version for exact alignment and an unordered version tolerant to typographical and formatting discrepancies. We prove correctness and privacy, analyze communication and computational (exponentiation) complexity, and formalize a universal index mapping from local records to a shared index space. This multi-party PSU offers a scalable, mathematically grounded protocol for PPEA in real-world VFL deployments, such as multi-institutional healthcare disease detection, collaborative risk modeling between banks and insurers, and cross-domain fraud detection between telecommunications and financial institutions, while preserving intersection privacy. Party A
Party B
ID
Gender
Income
John Doe
Male
$80,000
Jane Smith
Female
$85,000
Privacy Preserving Entity Alignment
ID
Address
Zip Code
John Doe
42 Oak Ave
04173
Jane Smith
5 River Lane
07204
Aligned Data ID
Gender
Income
Address
Zip Code
John Doe
Male
$80,000
42 Oak Ave
04173
Jane Smith
Female
$85,000
5 River Lane
07204
Figure 1: Illustrative example of entity alignment in VFL: based on the ID, Parties A and B perform private matching and produce Aligned Data without disclosing intersection membership or sensitive values.
1
PRIME AI paper
1
Introduction
Federated Learning (FL) [20] enables multiple parties (nodes, clients, or devices) to jointly train a model without sharing their raw data; instead, they exchange model parameters or updates, thereby avoiding the need to centralize datasets as in standard Machine Learning (ML). FL is commonly divided into Horizontal FL (HFL) [34], where participants have the same features but different records, and Vertical FL (VFL), where participants own complementary feature sets for an overlapping population of samples [32]. A fundamental prerequisite in VFL is that datasets be aligned row-wise [37]: (i) each record across parties refers to the same real-world entity, and (ii) records appear in the same order for all parties. In practice, this means establishing a common index of entities while avoiding disclosure of which entities are shared across parties (i.e., intersection membership) [30]. For example, consider a collaboration between a bank and an insurance company: the bank holds financial transaction data, while the insurer maintains policy and claim records. To jointly train a predictive model, such as estimating default risk or detecting fraud, their datasets must be aligned so that each row corresponds to the same customer across both organizations. Achieving this alignment without revealing which customers are shared between them is the challenge that privacy-preserving entity alignment (PPEA) aims to address (see Figure 1). PPEA [9] addresses this need by aligning datasets held by different parties while preserving privacy. Two main cryptographic approaches are commonly used: private set intersection (PSI) and private set union (PSU), as illustrated in Figures 2 and 3.
Figure 2: Illustration of the PSI protocol. Only the common identifiers (IDs) between the two parties are used to form the shared training dataset.
Figure 3: Illustration of the PSU protocol. All unique IDs across parties form the union dataset used for training; missing features for non-overlapping records are completed with synthetic data. In this paper, we introduce Sherpa.ai PSU for VFL, a multi-party, union-based entity-alignment method that employs a commutative-encryption PSU protocol to conceal intersection membership and construct a shared universal index across parties. Unlike prior PSU approaches that are primarily limited to the two-party setting and exact identifier matching, our method generalizes naturally to multiple parties and supports both exact and noisy matching regimes. After alignment on the union, missing attributes can be completed using synthetic data as a common practice used in PSU for VFL training. In VFL, we distinguish two conceptually distinct stages. First, at the alignment stage, PSU conceals intersection membership while constructing a private universal index across parties. Second, at the training stage, any downstream VFL method can operate on the aligned data produced by PSU. For example, paradigms such as Sherpa.ai Blind Vertical Federated Learning (SBVFL) [1], which replace true labels with server-generated synthetic labels and reduce party--server exchanges, may be employed to mitigate label and gradient leakage as well as communication overhead. In this sense, PSU is independent of the subsequent training method and serves as a privacy-preserving preprocessing step for VFL.
2
PRIME AI paper
1.1
Motivation and Challenges
PSI privately computes the intersection of the parties’ identifier sets (see Figure 2) enabling them to identify which identifiers they share. However, PSI outputs the intersection of identifiers as well, which can pose a privacy risk. For example, consider a federation of a bank and a cancer clinic: learning that a particular customer of the bank is in the intersection, it implies that this individual is in the clinics’s records, potentially leaking sensitive health information (i.e., the bank could infer that the customer suffers from cancer, and hence, denying them a loan). Revealing intersection membership can therefore violate privacy [26]; this motivates union-based alignment that keeps membership hidden. PSU computes the union of identifier sets (see Figure 3) without revealing intersection information. In PSU, the parties compute the set of all identifiers that appear in at least one dataset. By merging datasets on the union rather than the intersection, the parties avoid disclosing which identifiers they have in common. When using the union, some feature values will be missing for entities present only in one party. These gaps can be filled with synthetic data generated locally by each party, which prior work has shown can preserve model utility while improving privacy by hiding membership [26]. While several PSU protocols have been proposed in recent years, they have key limitations. Two-party designs, such as Sun et al. [26] and Tu et al. [27], target balanced or unbalanced two-party settings and, thus, do not directly scale to multi-party VFL. Multi-party or high-throughput variants (e.g., Gao et al. [7]) prioritize efficiency with heavier primitives but do not support typo-tolerant matching. Finally, differentially private unions (e.g., Gopi et al. [10]) produce approximate, rather than exact, unions. Motivated by these gaps, we develop a multi-party PSU for VFL that hides intersection membership and supports two alignment regimes: (i) an exact-hash, order-preserving regime, which is theoretically optimal when identifiers are clean and consistently formatted, and (ii) a fuzzy matching, unordered regime, which is substantially robust in real-world scenarios with noisy, heterogeneous identifier fields, but might give less accurate results in ideal conditions. In addition, some privacy-preserving entity-alignment approaches rely on a trusted coordinator or stronger trust assumptions, which may be undesirable in cross-organizational deployments; our protocol avoids this requirement. Further details and guarantees are provided in Sections 2 and 4. 1.2
Contributions
The main contributions of this work are summarized as follows: • We propose the multi-party Sherpa.ai PSU protocol for PPEA in VFL. Unlike traditional PSI methods, our hashing-based PSU construction enables secure alignment across multiple parties without requiring a trusted third party and prevents the disclosure of intersection membership. • We introduce an n-gram tokenization preprocessing step that enhances robustness to formatting inconsistencies and typographical errors, supporting both order-preserving (exact) and unordered (noisy) matching depending on data quality. • We formalize the commutative encryption process based on the Diffie–Hellman key exchange principle, generalizing existing two-party PSU methods [26] to a multi-party setting with provable privacy guarantees under the semi-honest model. • We define the procedure for computing universal indices that map each party’s local records into a shared index space, enabling subsequent data integration and joint model training. In summary, our approach establishes a mathematically grounded and robust to noisy identifiers framework for PPEA in VFL, maintaining confidentiality while remaining practical for deployment in real-world, multi-institutional collaborations. The remainder of this paper is organized as follows. Section 2 reviews related work. In Section 3, we formalize the problem setting for PSU in VFL. Section 4 details the proposed solution, including identifier preprocessing, hashing, PSU protocols (with or without order preservation), and synthetic data generation. Finally, Section 5 concludes the paper.
2
Related Work
Several PSU protocols have been proposed in the literature, leveraging diverse cryptographic techniques. For example, Sun et al. [26] proposed one of the first PSU solutions specifically for VFL without revealing 3
PRIME AI paper
intersection membership. Their protocol (which we build upon) is limited to two parties; in contrast, our approach generalizes to P parties and introduces n-gram tokenization for improved matching. Gao et al. [6] developed PULSE, a parallel multi-party PSU protocol that leverages fast cryptographic operations (e.g., symmetric-key primitives and oblivious transfers) to efficiently handle large-scale datasets. Our approach shares a similar multi-party setting but prioritizes minimal communication rounds over parallel throughput. Tu et al. [27] present an enhanced two-party PSU protocol that supports both balanced and unbalanced set sizes, achieving better computational and communication performance than earlier methods. In contrast, our protocol minimizes communication overhead by utilizing commutative encryption and naturally accommodates multiple parties without requiring additional assumptions. Beyond purely cryptographic methods, some works rely on differential privacy (DP). For instance, Gopi et al. [10] design algorithms that produce the union with rigorous privacy guarantees by injecting noise. Such DP-based approaches do not reveal exact intersection membership, but they trade off some accuracy (and typically do not yield exact unions) in exchange for strong privacy. Other approaches employ homomorphic encryption (HE): for example, Tu et al. [28] use fully HE (FHE) to compute an unbalanced PSU, achieving strong security with relatively heavy computation. Compared to these, our protocol avoids expensive public-key operations on large data, instead using hashing and modular exponentiations that are efficient, and requires only a few rounds of communication. Our primary design goal is to minimize both the number of communication rounds and the amount of exchanged data. The trade-off is that the ‘‘PSU without order’’ variant of our method involves a potentially expensive comparison step for handling typos, which can be mitigated through low-level implementations or optimized data structures such as Bloom filters. For additional references on the topic, we refer the reader to [17, 5, 25, 18, 14, 36, 8, 7, 15, 35]. Our approach builds upon and extends prior PSU research. In particular, our multi-party commutative encryption scheme generalizes the two-party PSU method of Sun et al. [26] by supporting any number of parties and introducing n-gram-based noisy matching. Unlike many PSI/PSU protocols that rely on heavier cryptographic tools (e.g., oblivious transfer, garbled circuits, or FHE) [16], our method keeps the computations relatively lightweight (modular exponentiations and hashing) and aims to reduce communication to two main rounds. Recent works, such as Gao et al. [6] and Tu et al. [27], focus on optimizing PSU for performance, achieving notable speed-ups through parallel operations and specialized data structures, albeit at the cost of increased protocol complexity. In contrast, our protocol emphasizes ease of integration within an FL system and simplicity of implementation, assuming semi-honest parties. Beyond PSU-specific research, complementary lines of work are directly relevant to PPEA in VFL. Private Sample Alignment (PSA) protocols have been explored to achieve reliable multi-client VFL deployments and scalable two-party settings [33, 31], offering alternative building blocks to PSU. For asymmetric federations, differential PSI (DPSI) protects membership by adding calibrated noise to the revealed results [11]. Noisy or approximate matching has been studied in PSI for biometric search [29], while classic privacy-preserving record linkage (PPRL) methods based on n-grams and Bloom filters [24, 4] are adapted to our unordered (noisy) matching design. A concise comparison of privacy properties across standard entity alignment (PSI), standard PSU, and our proposed Sherpa.ai PSU is presented in Table 1. Standard entity-alignment (PSI) protocols typically reveal the intersection between parties and are limited to exact, pairwise alignment, whereas standard PSU constructions hide the intersection but do not support multi-party execution and assume perfectly matching identifiers. In contrast, our proposed Sherpa.ai PSU simultaneously (i) computes only the union without revealing the intersection, (ii) naturally extends to more than two parties via a commutative-encryption design, and (iii) supports privacy-preserving noisy alignment to cope with typos and non-canonical identifiers. This combination of properties, which is crucial in realistic VFL deployments, is not provided by existing PSI/PSU-based entity-alignment schemes.
Raw identifiers exchanged Intersection revealed Multi-party Noisy alignment
Standard Entity Alignment (PSI)
Standard PSU
Sherpa.ai PSU
✓ No ✗ Yes ✓ Yes ✗ No
✓ No ✓ No ✗ No ✗ No
✓ No ✓ No ✓ Yes ✓ Yes
Table 1: Comparison of the privacy properties of different entity alignment protocols.
4
PRIME AI paper
3
Problem Formulation
We consider a set of P parties wishing to perform VFL. Without loss of generality, assume there are P − 1 passive parties F0 , . . . , FP −2 and an active party FP −1 . For each k ∈ {0, . . . , P − 1}, party Fk owns a dataset Dk = ⃗xki i∈{0,...,N −1} consisting of Nk data examples k
(rows), where each example (or row) ⃗xki ∈ Rdk , Nk ∈ N \ {0} and dk ∈ N \ {0}. All parties agree on a common set of one or more identifying features that will be used for record matching (for example, a combination of name, phone number, and address). We denote by dmatch the number of such identifying features (this dmatch is the same for every party). Let πk : Rdk −→ Rdmatch , be the projection that extracts the dmatch identifying attributes from party Fk ’s feature space. Each party can then derive from its dataset a set of raw identifiers (one identifier per example) as Iraw,k := πk ⃗xki | k = 0, . . . , Nk − 1 . for k = 0, . . . , P − 1. In other words, Iraw,k is the set of identifier tuples (such as personal data fields) for the records held by party Fk . Our goal is to perform the following steps in a privacy-preserving manner, without revealing to any party which identifiers are shared or not shared with other parties. 1. Compute the Union of Identifiers. Determine the union of all parties’ identifier sets: U :=
P[ −1
Iraw,k .
(3.1)
k=0
Let N = |U| be the total number of unique identifiers across all parties. 2. Define Universal Indices. Assign each identifier in the union U a unique universal index. Let V := {0, . . . , N − 1} be the set of universal indices. This is essentially an indexing of the union U. 3. Align Local to Universal Index Mappings. For each party Fk , determine a mapping φk : {0, . . . , Nk − 1} −→ V,
(3.2)
which maps each local index i (the position of a record in party Fk ’s dataset) to the corresponding universal index in V . In other words, if πk (xki ) ∈ U ends up as the j-th element of the union, then ϕk (i) = j. This mapping ϕk allows each party to translate its local records into the unified indexing of the union. All of the above should be achieved without any party learning which of its identifiers were or were not present in other parties’ datasets (thus, intersection membership remains private). Next, we describe our solution to this problem.
4
Our Proposed PSU Solution
Our pipeline proceeds in four stages (see Figure 4), to enable VFL PPEA without revealing intersection membership: 1. n-gram Tokenization of Identifiers: We first split each identifier in Iraw,k (which may be a composite of multiple fields) into a set of overlapping substrings of length n, known as n-grams. This helps standardize the format and allows for partial matching to accommodate error tolerance. 2. Hashing of Identifiers: The n-grams are hashed to fixed-length values. Hashing ensures a uniform representation (e.g., fixed-size bit strings or integers) for tokens, and provides a layer of one-way protection so that plaintext identifier values are not directly used in the cryptographic protocol. 3. PSU Protocol: Next, we perform a multi-party PSU protocol on the sets of hashed n-grams to obtain the union and the index mappings. Our PSU protocol uses commutative encryption in the cyclic group of quadratic residues to hide identifier values and achieve the required privacy properties. 5
PRIME AI paper
Figure 4: Pipeline of the proposed PSU protocol for multi-party VFL. 4. Synthetic Data Completion: After aligning on the union and obtaining universal indices, each party fills missing feature values for non-overlapping entities using privacy-preserving synthetic data generators, enabling downstream FL training without sharing raw data. The algorithms we propose are a generalization of [26, Algorithm 1, page 5], with the following additional features. • They work for P parties, where P ≥ 2. • Different identifier features are treated separately. • Each identifier’s feature is split in n-grams of assigned length. Conceptually, we distinguish two cases for the alignment problem. First, we consider alignment with exact hashes, where each identifier is represented as an ordered sequence of n-grams and two records are deemed equal only if all tokens match in the same order (Section 4.3). This regime is theoretically optimal when all parties store clean, consistently formatted identifiers, but it is less realistic in practice, where fields may be split, reordered, or contain typos. Second, we introduce a noisy matching regime that operates on unordered multisets of n-grams (Section 4.4). This ‘‘without order’’ variant is not exact even under ideal conditions, but in practice gives a very good approximation while being substantially more robust to noisy and heterogeneous identifier fields. Both cases share the same cryptographic PSU core; they differ only in how identifiers are tokenized and compared. In general, the PSU protocol is designed and analyzed in the group of quadratic residues modulo a safe prime. Specifically, let p be a safe prime, i.e., p is prime and (p − 1)/2 is also prime. Denote by Zp = {[0]p , [1]p , . . . , [p − 1]p } the ring of integers mod p, and by Z∗p = {[1]p , [2]p , . . . , [p − 1]p } the multiplicative group of integers mod p. We define the group of quadratic residues modulo p as QR Z⋆p := [x]p ∃y ∈ Z, y 2 ≡ x ̸≡ 0 (mod p) . (4.1) In other words, QR Z⋆p is the subgroup of Z∗p consisting of all non-zero squares mod p. By using the properties of the additive group (Zp , +) and the cyclic group Z⋆p , ∗ , it is possible to prove that QR Z⋆p , ∗ is a group of order p−1 2 . The security of the algorithms is based on the decisional Diffie-Hellman assumption [3], which stipulates that in the discrete group (4.1), performing the power (encryption) is easy, whereas performing the logarithm (decryption) is hard. As such, for our algorithms, all the operations will be taken modulo p or q = p−1 2 , where p is a safe prime number.
6
PRIME AI paper
4.1
n-gram Tokenization of Identifiers
For each party Fk and each raw identifier id ∈ Iraw,k , the identifier is decomposed into n-grams. An identifier id may be a single string (e.g., a customer ID) or a tuple of attributes (e.g., first name, last name, address, etc.). Formally, for every k = 0, . . . , P − 1, party Fk possesses an identifiers set Iraw,k . A raw identifier id ∈ Iraw,k is a vector id = id1 , . . . , iddmatch ∈ Rdmatch . Without loss of generality, assume each component idr can be represented as a string (we can stringify numeric fields as well): S := {s | s Python string} . We can cast in-place each component of the identifier id as a Python string. Then, id = id1 , . . . , iddmatch ∈ S dmatch . All parties F0 , . . . , FP −1 agree on the length nr of the n-grams in which component r of identifiers will be split, for each r ∈ {1, . . . , dmatch }. Moreover, in order to perform a proper n-grams splitting, they need to agree on a length for the string of each component of identifiers: let Lr be the established length of the component r of identifiers; if nr > Lr , we redefine Lr ← nr . For every k = 0, . . . , P − 1, for any identifier id ∈ Iraw,k , for each r ∈ {1, . . . , dmatch }, • if the length of the string idr is smaller than Lr , then Lr − length (idr ) empty spaces are added; • if the length of the string idr is greater than Lr , then the last length (idr ) − Lr characters are removed. At this stage, we can separate idr in Lr − nr + 1 nr -grams, using a sliding window approach. Namely, for l ∈ {0, . . . , Lr − nr }, the l-th nr -grams of idr is cr,l := (idr,l , . . . , idr,l+nr −1 ) . For k = 0, . . . , P − 1, set Iseparated-raw,k := (ci,r,l )i,r,l
i ∈ {0, . . . , Nk − 1} , r ∈ {1, . . . , dmatch } , l ∈ {1, . . . , Lr − nr + 1} .
The motivation for n-gram separation is twofold. First, it provides a flexible way to handle minor discrepancies in strings (e.g., typos or different formatting). Concretely, it allows our protocol to align identifiers such as ‘‘123 Main St.’’ stored as a single field with records where the street number and name are split across fields (‘‘123’’ and ‘‘Main St.’’), and to match ‘‘123 Main St.’’ against variants like ‘‘123 Main Street’’, ‘‘123 main st’’, or ‘‘123 Main Str’’. Similarly, it is robust to differences in capitalization (‘‘SMITH’’ vs. ‘‘Smith’’), accent marks (‘‘José’’ vs. ‘‘Jose’’), and small typographical errors. Because such representations still share most of their n-grams, they are treated as near-matches in the unordered case. Second, it can improve matching accuracy by ensuring that tokens are compared at a granular level rather than via whole-string comparisons. Our use of n-gram hashing is related to prior work on deep structured semantic models for web search, where n-gram vectors are used as inputs to neural networks, and 3-grams are found to offer a good compromise between robustness to small variations and the rate of hash collisions when order is not preserved [12]. In our setting, such noisy matching naturally induces two types of errors: (E1) false negatives, where records that truly exist in both parties are not linked, and (E2) false positives, where records belonging to different individuals are incorrectly linked. Since E2 is typically much more harmful in privacy-preserving entity resolution, we choose the similarity threshold in our matching step to strongly penalize E2-type errors, accepting a small number of E1 errors as the cost of avoiding incorrect links. Moreover, while additional neural layers on top of n-gram vectors can make direct inference of the original identifiers more difficult, they are generally designed to preserve enough information to approximately reconstruct the input and should not be seen as a primary privacy mechanism. In our protocol, n-gram noisy matching is used to enhance robustness in record linkage, while strong privacy guarantees are provided by the subsequent encryption layer. 7
PRIME AI paper
4.2
Hashing of Identifiers
After tokenization, each party hashes its n-grams to obfuscate their values and to enable efficient cryptographic processing. This second part of our solution addresses the hashing of n-grams, mapping raw feature values into the group defined in Equation (4.1). Our hashing procedure mainly consists of two steps: 1. Hashing by SHA3-256 and casting to int; 2. Projection onto QR Z⋆p . The composition of the above two operations defines a mapping: h : S −→ QR Z⋆p , where S := {s | s Python string} . For every k = 0, . . . , P − 1, the hashed identifiers set will be denoted by Ik . We have n o Ik = h (c) c ∈ Iseparated-raw,k . Hashing provides a layer of privacy (an adversary must invert the hash to guess the original token) and also standardizes the representation length of tokens. Most importantly, all parties use the same hash function h, so if two parties have an identical n-gram, they will end up with the same hash value. From this point onward, our protocol operates on these hashed identifiers. 4.2.1
Commutative Encryption
Our PSU protocol utilizes the group QR Z⋆p , defined earlier, as the space for commutative encryption. We choose a large safe prime p (on the order of 2048 bits or larger for security) and let q = (p − 1)/2 (which is prime). All operations on hashed identifiers will be performed modulo p, and some index arithmetic will be modulo P (for party indices). Figure 5 illustrates the first phase of the commutative encryption process that underpins the PSU protocol. Each party (A and B in the example) begins by hashing its identifiers and encrypting them with its local secret exponent. The encrypted identifiers are then shuffled and exchanged between the parties. Upon receiving the counterpart’s encrypted set, each party re-encrypts the values with its own secret exponent and shuffles them again before returning them. This iterative, commutative exchange ensures that identifiers are doubly encrypted under both parties’ keys while preserving the property that identical identifiers yield identical ciphertexts, a prerequisite for performing the secure union. Each party Fk generates a secret exponent sk (in practice, multiple exponents per party are used for different protocol phases, denoted sk1 , sk2 , sk3 ∈ {0, . . . , q − 1}). We define the encryption function es for exponent s applied on hashed token x ∈ Zp as: es,one component (x) = xs
mod p .
(4.2)
We extend this to an identifier’s tokens (across all features) by applying es to each token: let an identifier be represented as a tuple (xr,l ) where r is the index of the feature (from 1 to dmatch ) and l is the index of the n-gram within that feature (from 1 to Lr − n + 1, assuming Lr is the length of feature r for that identifier). Next, we define the following vectorized encryption functions. Let s ∈ {0, . . . , q − 1} and dmatch
es : (xr,l )r∈{1,...,d
Y
"L −n +1 r Y r
r=1
l=1
#
dmatch
Zp −→
Y
"L −n +1 r Y r
r=1
l=1
match },l∈{1,...,Lr −nr +1}
7−→ xsr,l r∈{1,...,d
# Zp
match },l∈{1,...,Lr −nr +1}
where σ : {0, . . . , Nk − 1} −→ {0, . . . , Nk − 1} is a random permutation. 8
,
PRIME AI paper
Figure 5: Scheme describing the main steps of the first part of the Diffie-Hellman protocol employed for PSU. By the commutativity of the product in Zp , es1 ◦ es2 = es2 ◦ es1 , for some s1 , s2 in {0, . . . , q − 1}. Because exponentiation is applied independently to each token, two identical identifiers (same tokens in the same order) encrypted with the same exponent s yield identical outputs, while identifiers that differ in any token produce different encrypted outputs (up to hash or exponent collisions). Moreover, since es1 ◦ es2 = es2 ◦ es1 for any s1 , s2 ∈ {0, . . . , q − 1}, applying exponents in any order is equivalent to a single exponentiation by s1 s2 mod q. This commutativity is what enables our multi-party PSU construction. From a cryptographic standpoint, this layer is not a new primitive but the standard Diffie--Hellman exponentiation in the safe-prime subgroup QR(Z∗p ), i.e., the mapping x 7→ xs mod p for a secret exponent s ∈ {1, . . . , q − 1}. We deliberately use this primitive in a deterministic, commutative masking mode rather than as a randomized public-key encryption scheme. This is essential for PSU: (i) exponentiations under different parties’ secret exponents must commute, so that applying all exponents in any order yields the same masked identifier, and (ii) identical identifiers must remain identical after all exponentiations, so that the server can compute the union by equality tests on the resulting masked values. Standard randomized public-key encryption schemes would typically destroy these properties, since encrypting the same value twice yields unrelated ciphertexts and encryptions under different keys do not commute. Our choice therefore, provides exactly the algebraic structure needed for multi-party PSU without a trusted third party. The privacy analysis is carried out in the semi-honest model and relies on the standard Decisional Diffie--Hellman assumption in QR(Z∗p ).
9
PRIME AI paper
Figure 6: Scheme describing the main steps of the second part of the Diffie-Hellman protocol employed for PSU. Figure 6 illustrates the second phase of the commutative encryption process, which determines the final mapping between local identifiers and their encrypted counterparts in the union. After the initial doubleencryption round (Figure 5), each party performs additional encryption operations using its remaining secret keys and returns the results to the other party. The active party then computes the fully encrypted union and derives the mapping between each local record and the corresponding universal index. This phase finalizes the secure exchange while maintaining the commutativity property, which prevents either participant from learning the intersection membership. Let us also define ês as the operation of applying es to an entire set of identifiers (for example, an entire party’s set Ik ) and also randomly permuting the order of identifiers. Specifically, for every k = 0, . . . , P − 1,
ebs :
NY k −1 dmatch Y
"L −n +1 r Y r
l=1
k=0
r=1
# Zp
−→
7−→ match },l∈{1,...,Lr −nr +1}
(xi,r,l )i∈{0,...,Nk −1},r∈{1,...,d
NY k −1 dmatch Y k=0
xsσ(i),r,l
r=1
"L −n +1 r Y r l=1
# Zp
i∈{0,...,Nk −1},r∈{1,...,dmatch },l∈{1,...,Lr −nr +1}
,
where σ : {0, . . . , Nk − 1} −→ {0, . . . , Nk − 1} is a permutation. We allow each party to re-index (shuffle) its set after encryption to hide any information that could be inferred from the ordering of identifiers (for example, if one party’s dataset is sorted in some way, a shuffle breaks that correlation). We denote by σ a random permutation on the index set {0, . . . , Nk − 1} used by party Fk during encryption. The commutativity still holds: applying ebs1 and then ebs2 (with independent random permutations) to a vector of identifiers yields the same vector as ebs2 followed by ebs1 – only the overall order might differ, but since we treat the final results as sets, order does affect correctness.
10
PRIME AI paper
Let us now define the notion of the product of encryption functions. Let {s1 , . . . , sn } ⊂ {0, . . . , q − 1}, for some n ∈ N \ {0}. Let n Y esi = esn ◦ · · · ◦ es1 i=1
and
n Y
ebsi = ebsn ◦ · · · ◦ ebs1 .
i=1
Qn2 esi , the Whenever the index range is empty, i.e., when n1 > n2 in an expression of the form i=n 1 corresponding composition is defined to be the identity map. Q Since the composition of encryption functions is commutative, the product operator defined above is well-posed. Using this commutative encryption scheme, we can construct Algorithm 1, which outlines the PSU protocol with order preservation. 4.3
PSU Protocol with Order (Exact)
We now describe the order–preserving variant of our PSU protocol. This corresponds to the exact-hash alignment regime described in the previous Section. In this case, each identifier id ∈ Iraw,k is first tokenized Qdmatch QLr −nr +1 into n-grams per feature and hashed into Ik ⊂ r=1 QR(Z∗p ) as in Section 4.2; the relative order l=1 of n-grams within each feature is treated as semantically meaningful. The goal is to compute a universal set of encrypted identifiers U that represents the union of all parties’ (ordered) hashed identifiers while revealing nothing about intersection membership, together with local mappings φk : Iraw,k → V that align each party’s records to the universal index set V . Algorithm 1 depicts the pseudocode of our solution. At a high level, it proceeds in three phases: 1. Key setup and first commutative pass. Each party Fk samples exponents sk1 , sk2 , sk3 ∈ {0, . . . , q−1}. Using the commutative mappingQes (·) = (·)s mod p and its setwise/shuffled lift ebs , the parties cyclically apply ebsk1 to every Ik1 , yielding bsl1 Ik1 at the initiator Fk1 without exposing which tokens are shared. le 2. Provisional union The active party FP −1 forms the duplicate-free provisional S and Q re-randomization. Q union Iun,prov = k bsl1 Ik and encodes it by applying l ebsl3 sl2 , producing the final encrypted universal le Q identifiers U = bsl3 sl2 Iun,prov , which are then broadcast to all parties. le 3. Private matching and index assignment. Each Fk locally re-encrypts its own Ik with esk2 and relays the result through a second commutative pass of exponents {sℓ1 , sℓ2 , sℓ3 }. By commutativity, every element of Ik is transformed into the same ciphertext as its counterpart in U , enabling Fk to determine φk by testing membership in U without revealing whether any particular identifier belongs to the intersection. The ordered treatment of tokens ensures that two identifiers match if and only if all their feature-wise n-gram sequences coincide, yielding exact row alignment when inputs are consistently formatted. Security follows from applying only exponentiations in the subgroup QR(Z∗p ) under the decisional Diffie–Hellman assumption, together with full-set shuffling ebs and a final joint re-randomization, which hides intersection membership while preserving the union. The dominant cost arises from modular exponentiations during the two commutative passes; as noted below, these operations are parallel and can be executed efficiently in a multi-threaded or distributed manner.
11
PRIME AI paper
Algorithm 1: PSU protocol, with order. Qd
QL −n +1
r r match QR Z⋆p , with p prime Data: For every k = 0, . . . , P − 1, a set of hashed identifiers Ik ⊂ r=1 l=1 p−1 and q := 2 prime. All the operations on identifiers will be taken modulo p. All the operation on indices k ∈ {0, . . . , P − 1} will be taken modulo P . Result: Set V of universal indices (UI) and, for any k = 0, . . . , P − 1, map
φk : Iraw,k −→ V associating each identifier id ∈ Iraw,k (of the local dataset Dk ) to the corresponding index in the set of universal indices (UI) V . Initialization. for k ← 0 to P − 1 do party Fk randomly generates three secret exponents sk1 , sk2 and sk3 in {0, . . . , q − 1}. These will be used in different rounds of encryption. First Round – Commutative Encryption of Local Sets. for k1 ← 0 to P − 1 do party Fk1 computes b esk1 Ik1 , 1
and sends it to the next party Fk1 +1 (indices mod P so that e.g. FP is F0 ). We now start an additional encryption pipeline, where each subsequent party Fk2 (for k2 = k1 + 1 up to P − 1 and then wrapping around to 0, . . . , k1 − 1) encrypts as follows. for k2 ← 0, k2 , ̸= k1 to P − 1 hdo i When party Fk2 receives
Qk2 −1
l=0,l̸=k1
b e sl b esk1 Ik1 , it computes 1 1 # " k 2 Y esk1 Ik1 , b e sl b 1
1
l=0,l̸=k1
and sends it to Fk2 +1 . QP −1 When Fk1 receives back l=0 b esl Ik1 , it stops and sends it to FP −1 . 1
Union Computation (Provisional). FP −1 performs the union (repetitions must be avoided) P −1 P −1
Iun,prov :=
[ Y
b esl Ik . 1
k=0 l=0
Now the active party FP −1 orchestrates a second round of encryption on the provisional union to further blind the values. for k ← P − 1 to 0 do party Fk computes P −1
Y
b esl sl Iun,prov , 3 2
l=k
and sends it to Fk−1 . Once FP −1 receives P −1
Y
b esl sl Iun,prov , 3 2
l=0
party FP −1 determine U , the set of encrypted universal identifiers (UID) P −1
U :=
Y
b esl sl Iun,prov . 3 2
l=0
12
PRIME AI paper
Algorithm 1: PSU protocol, with order (continued). for k ← 0 to P − 1 do Party FP −1 sends the set of encrypted universal identifiers (UID) to party Fk . Private Matching of Identifiers. Finally, each party determines the mapping ϕk between its local identifiers and the universal set. This is done by each party independently (in parallel) using the secret exponents and the encrypted data. for k1 ← 0 to P − 1 do for any x ∈ Ik1 , party Fk1 computes esk1 x and sends it to Fk1 +1 . 2
for k ← 1 to P − 1 do When Fk1 +k receives k−1
esk1
Y
2
esk1 +l sk1 +l sk1 +l x, 3
2
1
l=1
it computes esk1
k Y
2
esk1 +l sk1 +l sk1 +l x, 3
2
1
l=1
and sends it to Fk1 +k . When Fk1 receives back P −1 2
Y
esk1
esk2 sk2 sk2 3
k2 =0, k2 ̸=k1
x,
1
2
party Fk1 computes P −1
Y
esk2 sk2 sk2 3
2
x
1
k2 =0
and party Fk1 stores φ̃k1 : Ik1 −→ U P −1
x 7−→
Y
esk2 sk2 sk2 3
2
x
1
k2 =0
and determines φk1 : Ik1 −→ V.
At the end of Algorithm 1, all parties share a common indexing of the union of identifiers, and none of them has learned which identifiers are exclusively held by which party. The intersection information is protected because any identifier in the intersection appears in U just like any other, with no party knowing if it came from one or multiple datasets. Complexity. The first round of the algorithm involves each party’s dataset traversing the network of P parties, resulting in P transmissions per dataset (total transmissions of P 2 in the worst case). The second round similarly involves P transmissions of the union (which size N could be larger than individual set sizes). The final matching step involves each identifier being sent through P parties (so Nk × P operations for party k). The computational cost is dominated by the modular exponentiations on possibly large sets; however, these are commutative (no interactive OT or public-key operations per item beyond exponentiation). Since the modular exponentiations on each token are independent, the protocol can be efficiently parallelized across threads or distributed parties. In large-scale deployments, a lightweight pre-alignment or ‘‘blocking’’ stage could be introduced before the cryptographic protocol to reduce the number of candidate comparisons. For example, each party could exchange salted hash summaries (e.g., SHA-256) of identifiers to exclude obviously non-matching entries, thereby decreasing computational load while preserving privacy. 4.4
PSU Protocol without Order (Noisy)
Next, we describe the variant of the protocol that does not preserve the order of n-grams within each identifier’s features. This corresponds to the more practical ‘‘noisy matching’’ alignment regime, designed to handle noisy and heterogeneous identifier fields. This ‘‘without order’’ PSU variant is designed to tolerate
13
PRIME AI paper
typographical variations or inconsistencies in identifiers by treating each as an unordered multiset of tokens. In this case, two identifiers can be considered a match (representing the same entity) even if their tokens are in a different order or one identifier has an extra token that the other lacks, as long as a majority of tokens overlap. This is essentially a private noisy matching of identifiers. The overall structure of the protocol remains similar to the with-order case, but there are two key differences. • In the encryption steps, we introduce an additional random permutation of token positions within each identifier’s feature. Previously, es mapped each token but kept its position fixed in its feature. Now, we modify es to also randomly permute the positions of the n-grams in each feature (or use a fixed permutation νr per exponent) so that the token order information is eliminated (see Definition (4.3)). • In the union matching step, because tokens are now unordered, we cannot simply take identical encrypted identifiers as an one-to-one match. Two identifiers that represent the same entity might not encrypt to an identical tuple if one had an extra token or tokens were in a different order originally. To address this, we implement a special comparison sub-protocol (Algorithm 2) which privately tests if two encrypted identifiers approximately match, given a tolerance threshold λ. This comparison algorithm essentially counts the number of encrypted tokens two identifiers have in common and determines that they are the same if a sufficiently large fraction of tokens match. We introduce a threshold parameter 0 < λ ≤ 1 which governs the matching criterion. For each feature r, let Lr − n + 1 be the total number of n-grams for that feature in a fully formatted identifier (assuming no missing tokens). We assume that each identifier has at least ⌈λ(Lr − n + 1)⌉ tokens for feature r (this is reasonable if λ is, say, 0.8, ensuring we only consider matches if both have a significant portion of the full token set). Algorithm 2 takes two encrypted identifiers (each a set of tokens per feature) and returns 1 if they are deemed a match (same entity) or 0 otherwise, without revealing any additional information. Let s ∈ {0, . . . , q − 1} and dmatch
es : (xr,l )r∈{1,...,d
match
Y
"L −n +1 r Y r
r=1
l=1
#
dmatch
Zp −→
Y
"L −n +1 r Y r
r=1
l=1
s − 7 → x r,ν (l) },l∈{1,...,Lr −nr +1} r
# (4.3)
Zp
r∈{1,...,dmatch },l∈{1,...,Lr −nr +1}
and, for every k = 0, . . . , P − 1, # " # " NY NY k −1 dmatch k −1 dmatch Y Lr −n Yr +1 Y Lr −n Yr +1 Zp −→ Zp ebs : j=0
r=1
r=1
j=0
l=1
(xj,r,l )j∈{0,...,Nk −1},r∈{1,...,d
match },l∈{1,...,Lr −nr +1}
7−→
xsσ(j),r,νr (l)
l=1
j∈{0,...,Nk −1},r∈{1,...,dmatch },l∈{1,...,Lr −nr +1}
with νr : {1, . . . , Lr − nr + 1} −→ {1, . . . , Lr − nr + 1} and σ : {0, . . . , Nk − 1} −→ {0, . . . , Nk − 1} random permutations (the index r ∈ {1, . . . , dmatch }). Here νr is a permutation of the positions for feature r. This essentially jumbles the token order for each feature before applying the exponent. Each party can choose a random νr when applying its exponent, or a deterministic one, such as sorting by token value; the important part is that the order is not preserved through encryption. By the commutativity of the product in Zp , es1 ◦ es2 ≃ es2 ◦ es1 , for some s1 , s2 in {0, . . . , q − 1}, the symbol ≃ meaning equality up to a permutation of the n-grams. Namely, for r ∈ {1, . . . , dmatch }, there exist a permutation ωr : {1, . . . , Lr − nr + 1} −→ {1, . . . , Lr − nr + 1}, such that, for any " # dmatch Lr −nr +1 Y Y (xr,l )r∈{1,...,d Zp , },l∈{1,...,Lr −nr +1} ∈ match
r=1
l=1
we have es1 ◦ es2 (xr,l )r∈{1,...,d
match },l∈{1,...,Lr −nr +1}
= es2 ◦ es1
14
xr,ωr (l) r∈{1,...,d
match },l∈{1,...,Lr −nr +1}
(4.4)
PRIME AI paper
(xi,j,r,l )i∈{0,...,n},j∈{0,...,Nk −1},r∈{1,...,d
match },l∈{1,...,Lr −nr +1}
7−→ (x̃j,r,l )j∈0,...,Nb−1 ,r∈{1,...,d
match },l∈{1,...,Lr −nr +1}
Let {s1 , . . . , sn } ⊂ {0, . . . , q − 1}, for some n ∈ N \ {0}. Define n Y
esi = esn ◦ · · · ◦ es1
i=1
and
n Y
ebsi = ebsn ◦ · · · ◦ ebs1 .
i=1
Qn2 . . . , if n1 > n2 , the result is defined as the identity. In products i=n 1 P b := n+1 Nk . We define the concatenation operator as Let N k=0 ! dmatch Lr −nr +1 bY N −1 dmatch PY −1 NY k −1 Y Y Y Zp −→ Λ: k=0
j=0
r=1
j=0
l=1
and x̃j,r,l = xi,bj ,r,l , by setting b j := j −
r=1
Lr −n Yr +1
! Zp
l=1
Pk−1
k=0 Nk and for
k ∈ {0, . . . , P − 1} , (k−1 ) i X X j∈ Nk , . . . , Nk − 1 , k=0
k=0
r ∈ {1, . . . , dmatch } , l ∈ {1, . . . , Lr − nr + 1} . Before defining the main Algorithm 3, we need to define an algorithm for comparing two encrypted identifiers as shown below.
15
,
PRIME AI paper
Algorithm 2: Encrypted Identifier Comparison. Data: Encrypted identifiers dmatch
(xr,l )r∈{1,...,d
Y
"p1,r Y
r=1
l=1
dmatch
Y
"p2,r Y
r=1
l=1
∈
match },l∈{1,...,p1,r }
# Zp
and (yr,l )r∈{1,...,d
match },l∈{1,...,p2,r }
∈
# Zp .
Threshold λ ∈ (0, 1]. Assume pi,r ∈ [⌈λLr − nr + 1⌉, Lr − nr + 1], for r ∈ {1, . . . , dmatch }. Result: 1 if the encrypted identifiers match. 0 otherwise. If 1, return listmatch . Initialization. Set listmatch ← [ ] . Comparison. for r ← 1 to dmatch do Set listmatch,r ← [ ] . for l1 ← 0 to p1,r do for l2 ← 0 to p2,r do If xr,l1 = yr,l2 and l1 does not belong to listmatch,r , append l1 to listmatch,r . If the cardinality of listmatch,r is greater than ⌈λLr − nr + 1⌉, return 0. Else, append listmatch,r to listmatch . Return 1 and listmatch .
Remark 4.1 (Equivalence). Observe that algorithm (2) defines a relation between " # dmatch p1,r Y Y Zp r=1
l=1
dmatch
Y
"p2,r Y
r=1
l=1
and
# Zp ,
where two respective elements x := (xr,l )r∈{1,...,d
match },l∈{1,...,p1,r }
and y := (yr,l )r∈{1,...,d
match },l∈{1,...,p2,r }
are related if algorithm (2) applied to (x, y) returns 1. However, this relation may not be an equivalence relation, since it may not be transitive. An adaptive selection of the matching threshold λ could further improve PPEA accuracy by adjusting it according to data quality or field variability. For instance, domain-specific calibration (e.g., different λ values for names and addresses) or automatic tuning using validation data could balance recall and precision in noisy matching without altering the cryptographic design. Further extensions could integrate alternative similarity metrics, such as edit distance or locality-sensitive hashing (LSH) [13] , enabling matching beyond token overlap while maintaining privacy-preserving properties. Next, we present the main algorithm for our PSU without order.
16
PRIME AI paper
Algorithm 3: PSU protocol, without order. QL −n +1
Qd
r r match QR Z⋆p , with p prime Data: For every k = 0, . . . , P − 1, a set of hashed identifiers Ik ⊂ r=1 l=1 p−1 and q := 2 prime. All the operations on identifiers will be taken modulo p. All the operation on indices k ∈ {0, . . . , P − 1} will be taken modulo P . Threshold λ ∈ (0, 1]. Result: Set V of universal indices (UI) and, for any k = 0, . . . , P − 1, map
φk : {0, . . . , Nk − 1} −→ V associating each index i of the local dataset Dk to the corresponding index in the set of universal indices (UI) V . Initialization. for k ← 0 to P − 1 do party Fk randomly generates sk1 , sk2 and sk3 in {0, . . . , q − 1}. First Round – Commutative Encryption of Local Sets. for k1 ← 0 to P − 1 do party Fk1 computes b esk1 Ik1 , 1
and sends it to Fk1 +1 . for k2 ← 0, k2 , ̸= k1 to hP − 1 do When Fk2 receives
i b e sl b esk1 Ik1 , it computes 1 1 # " k 2 Y esk1 Ik1 , b e sl b
Qk2 −1
l=0,l̸=k1
1
1
l=0,l̸=k1
and sends it to Fk2 +1 . QP −1 When Fk1 receives back l=0 b esl Ik1 , it stops and sends it to FP −1 . 1
Union Computation (Provisional). FP −1 define a vector Vun,prov := Λ
P −1
P −1
P −1
Y
Y
Y
b e sl I 0 , . . . , 1
l=0
b esl Ik , . . . , 1
l=0
! b esl In . 1
l=0
We have
b = lengthfirst axis (Vun,prov ) . N
(4.5)
b − 1 do for k1 ← 0 to N b − 1 do for k2 ← k1 to N
FP −1 applies algorithm 2 to Vun,prov,k1 , with Vun,prov,k2 . If the output is 1, remove Vun,prov,k2 and remove from Vun,prov,k1 n-grams indicated in listmatch .
From elements of Vun,prov,k1 , party FP −1 removes randomly components to reduce length of each element to ⌈λLr − nr + 1⌉. FP −1 defines Iun,prov :=
n
Vun,prov,l
o
l ∈ {1, . . . , lengthfirst axis (Vun,prov )} ,
where lengthfirst axis (Vun,prov ) may have changed, with respect to (4.5), because of the removals. for k ← P − 1 to 0 do party Fk computes P −1
Y
b esl sl Iun,prov , 3 2
l=k
and sends it to Fk−1 . Once FP −1 receives P −1
Y
b esl sl Iun,prov , 3 2
l=0
17
PRIME AI paper
Algorithm 3: PSU protocol, without order (continued). for i ← 1 to P − 1 do party FP −1 sends PY −1
ebsl3 sl2 Iun,prov ,
l=0
to Fk . Party FP −1 determines U the set of encrypted universal identifiers (UID) U :=
PY −1
ebsl3 sl2 Iun,prov .
l=0
for k ← 0 to P − 1 do Party FP −1 sends the set of encrypted universal identifiers (UID) to party Fk . Private Matching of Identifiers. for k1 ← 0 to P − 1 do for any x ∈ Ik1 , party Fk1 computes esk1 x and sends it to Fk1 +1 . 2 for k ← 1 to P − 1 do When Fk1 +k receives k−1 Y esk1 esk1 +l sk1 +l sk1 +l x, 2
3
l=1
2
1
it computes esk1 2
k Y
esk1 +l sk1 +l sk1 +l x, 3
l=1
2
1
and sends it to Fk1 +k . When Fk1 receives back esk1 2
PY −1
esk2 sk2 sk2 x, 3
k2 =0, k2 ̸=k1
2
1
party Fk1 computes PY −1 k2 =0
esk2 sk2 sk2 x. 3
2
(4.6)
1
Party Fk1 checks the existence of an element x̂ ∈ U , having ⌈λLr − nr + 1⌉ n-grams in common, with (4.6). If this element exists, party Fk1 stores φ̃k1 : Ik1 −→ U x 7−→ x̂ and determines φi1 : Ii1 −→ V.
18
PRIME AI paper
Remark 4.2. In case the order of n-grams is not preserved, to reduce the computational cost as well as save memory, Bloom filters (bit arrays) are used to store encrypted identifiers, i.e., an encrypted identifier " # dmatch Lr −nr +1 Y Y (xr,l )r∈{1,...,d Zp , (4.7) },l∈{1,...,Lr −nr +1} ∈ match
r=1
l=1
p
is represented by a Bloom filter (bitarray) b ∈ {0, 1} by setting b (xr,l ) = 1, ∀ (r, l) ∈ {1, . . . , dmatch } × {1, . . . , Lr − nr + 1} and 0 elsewhere. We highlight two properties of this representation: 1. Two identifiers that are equivalent according to (4.4) produce the same Bloom filter, since Bloom filters defined in (4.7) are insensitive to n-gram order. 2. Two identifiers that are not equivalent according to (4.4) may still produce the same Bloom filter, because the Bloom filters in (4.7) ignore both n-gram order and feature order. This may lead to false matches. Using a separate Bloom filter per feature would reduce this effect, but here we use a single Bloom filter for all features to save memory. In future implementations, precision could be further improved by adopting multiple Bloom filters (one per identifier feature) or by applying multiple hash functions per token, thereby reducing false positives while maintaining reasonable memory use. In scenarios where a subset of entities already share persistent global identifiers (e.g., national or organizational IDs), these records can be excluded from the PSU protocol and directly merged, with the alignment executed only on the remaining unmatched entities. This optimization preserves security while avoiding redundant computation in practical deployments. An additional layer of formal privacy could be incorporated by introducing DP perturbations, such as dummy identifiers or randomized mappings, to protect against membership inference in extreme asymmetric cases. Finally, Bloom filter construction can be parallelized over data blocks, offering substantial runtime reductions for large-scale datasets, as shown in other parallel PSU implementations such as PULSE [6]. 4.5
Synthetic Data Completion
During model training, each party must generate a synthetic dataset to fill in the missing features in its local data, i.e., those present in the datasets of other parties but absent locally. To this end, the Synthetic Data Vault (SDV) [21] is the state-of-the-art open-source library for generating high-quality synthetic data. SDV uses ML models to capture the statistical properties and dependencies of real datasets, enabling the creation of synthetic data that preserves both structure and utility, while protecting individual privacy. It supports tabular, time-series, and relational data and provides tools for evaluating data fidelity and privacy. By offering privacy-compliant data, SDV facilitates secure data sharing, model testing, and training in sensitive domains such as healthcare and finance, without compromising confidentiality. Two SDV backends are particularly suitable for our purpose: Gaussian Copula and Conditional Tabular Generative Adversarial Network (CTGAN). The Gaussian Copula backend employs statistical modeling through copulas, i.e., functions that describe dependencies between random variables, to generate synthetic data. Each feature is first fitted to an appropriate marginal distribution (e.g., Gaussian, Exponential) and normalized within a uniform range (0, 1) via cumulative distribution functions (CDFs). Correlations among variables are captured by a correlation matrix that models the linear dependence between transformed variables. Synthetic samples are then generated from the fitted Gaussian Copula model and inverse-transformed back to the original feature space. By operating in a transformed space and focusing on correlations rather than exact values, this method ensures that individual-level information is not reproduced while maintaining realistic relationships among variables. Gaussian Copula is particularly effective for tabular data of moderate dimensionality, capturing non-linear dependencies with low computational cost. The CTGAN backend extends the standard Generative Adversarial Network (GAN) architecture to tabular data with mixed types, imbalanced distributions, and/or categorical features. It consists of two neural components: (i) a generator, which produces synthetic records, and (ii) a discriminator, which distinguishes real from synthetic samples. Continuous features are normalized using min–max scaling and mode-specific 19
PRIME AI paper
normalization, which increases representation in dense data regions, while categorical variables are transformed into binary vectors. CTGAN selects a column at random during training as a conditioning variable and samples data accordingly, allowing the generator to learn relationships between that column and the rest of the dataset. After training, the generator produces realistic synthetic rows from random noise and conditional inputs, which are then inverse-transformed to match the original data types and distributions. This approach performs particularly well when the underlying data relationships are complex and traditional statistical models fail to capture them. From the perspective of missing-data theory, our synthetic completion step can be viewed as a form of model-based imputation, where unobserved features are generated conditional on the observed ones. Classical approaches distinguish between (i) data imputation, which replaces missing values by point estimates or draws from the posterior predictive distribution (e.g., via the EM algorithm or multiple imputation), and (ii) marginalization, where learning and inference integrate over the distribution of missing values without explicitly filling them in [2, 22, 19, 23]. Our PSU-based framework is compatible with both views: the synthetic features we generate correspond to imputations of unobserved modalities, while downstream federated models could in principle be trained in a marginalization style by averaging over multiple synthetic completions, leveraging the rich toolbox developed in the missing-data literature.
5
Conclusions
In this paper, we presented the Sherpa.ai multi-party PSU protocol for PPEA in VFL. The proposed method enables multiple parties to align their datasets without revealing intersection membership, thereby strengthening privacy guarantees in collaborative ML settings. The protocol generalizes the prior two-party PSU approaches to a multi-party scenario with low communication overhead. Two complementary variants were presented: an order-preserving version for exact alignment and an unordered version that supports noisy matching, tolerant to typographical and formatting inconsistencies. Together, these algorithms offer a flexible trade-off between precision and robustness, depending on data quality and application context. Beyond the core design, we discussed implementation aspects, including Bloom filter representations, adaptive thresholds, and parallelization strategies, to enhance scalability. Through secure and accurate entity alignment, the proposed Sherpa.ai PSU protocol empowers organizations to collaborate on VFL applications in a privacypreserving manner, enabling practical, privacy-preserving VFL across sensitive domains, including healthcare, finance, manufacturing, aerospace, cybersecurity, and the defense industry. In practice, both exact and noisy PSUs can be integrated with a paradigm such as SBVFL [1], which establishes a new benchmark in privacy preservation while enhancing computational efficiency. This paradigm achieves stronger confidentiality guarantees than conventional aggregation methods, alongside faster convergence and improved scalability. SBVFL thus represents a safer and more resilient framework for the next generation of secure, privacy-preserving, and collaborative intelligence.
Contributions and Acknowledgments Daniel M. Jimenez-Gutierrez Dario Pighin Enrique Zuazua Georgios Kellaris Joaquin Del Rio Oleksii Sliusarenko Xabi Uribe-Etxebarria The authors are presented in alphabetical order by first name.
20
PRIME AI paper
References [1] A. Acero, D. M. Jimenez-Gutierrez, D. Pighin, E. Zuazua, J. Del Rio, and X. Uribe-Etxebarria. The sherpa. ai blind vertical federated learning paradigm to minimize the number of communications. arXiv preprint arXiv:2510.17901, 2025. [2] A. P. Dempster, N. M. Laird, and D. B. Rubin. Maximum likelihood from incomplete data via the em algorithm. Journal of the royal statistical society: series B (methodological), 39(1):1--22, 1977. [3] W. Diffie and M. Hellman. New directions in cryptography. IEEE transactions on Information Theory, 22(6):644--654, 1976. [4] E. A. Durham, M. Kantarcioglu, Y. Xue, C. Toth, M. Kuzu, and B. Malin. Composite bloom filters for secure record linkage. IEEE transactions on knowledge and data engineering, 26(12):2956--2968, 2013. [5] K. Frikken. Privacy-preserving set union. In International Conference on Applied Cryptography and Network Security, pages 237--252. Springer, 2007. [6] J. Gao, S. Nguyen, M. Blanton, and N. Trieu. Pulse: Parallel private set union for large-scale entities. Cryptology ePrint Archive, 2025. [7] J. Gao, S. Nguyen, and N. Trieu. Toward a practical multi-party private set union. Cryptology ePrint Archive, 2023. [8] Y. Gao, X. Zheng, and C. Hu. A multi-party private set union protocol against malicious adversary. In International Conference on Innovative Computing, pages 159--167. Springer, 2024. [9] A. Gkoulalas-Divanis, D. Vatsalan, D. Karapiperis, and M. Kantarcioglu. Modern privacy-preserving record linkage techniques: An overview. IEEE Transactions on Information Forensics and Security, 16:4966--4987, 2021. [10] S. Gopi, P. Gulhane, J. Kulkarni, J. H. Shen, M. Shokouhi, and S. Yekhanin. Differentially private set union. In International Conference on Machine Learning, pages 3627--3636. PMLR, 2020. [11] Y. He, X. Tan, J. Ni, L. T. Yang, and X. Deng. Differentially private set intersection for asymmetrical id alignment. IEEE Transactions on Information Forensics and Security, 17:3479--3494, 2022. [12] P.-S. Huang, X. He, J. Gao, L. Deng, A. Acero, and L. Heck. Learning deep structured semantic models for web search using clickthrough data. In Proceedings of the 22nd ACM international conference on Information & Knowledge Management, pages 2333--2338, 2013. [13] P. Indyk and R. Motwani. Approximate nearest neighbors: towards removing the curse of dimensionality. In Proceedings of the thirtieth annual ACM symposium on Theory of computing, pages 604--613, 1998. [14] Y. Jia, S.-F. Sun, H.-S. Zhou, J. Du, and D. Gu. Shuffle-based private set union: Faster and more secure. In 31st USENIX Security Symposium (USENIX Security 22), pages 2947--2964, 2022. [15] Y. Jia, S.-F. Sun, H.-S. Zhou, and D. Gu. Scalable private set union, with stronger security. In 33rd USENIX Security Symposium (USENIX Security 24), pages 6471--6488, 2024. [16] D. M. Jimenez-Gutierrez, Y. Falkouskaya, J. L. Hernandez-Ramos, A. Anagnostopoulos, I. Chatzigiannakis, and A. Vitaletti. On the security and privacy of federated learning: A survey with attacks, defenses, frameworks, applications, and future directions. arXiv preprint arXiv:2508.13730, 2025. [17] L. Kissner and D. Song. Privacy-preserving set operations. In Annual International Cryptology Conference, pages 241--257. Springer, 2005. [18] V. Kolesnikov, M. Rosulek, N. Trieu, and X. Wang. Scalable private set union from symmetric-key techniques. In International Conference on the Theory and Application of Cryptology and Information Security, pages 636--666. Springer, 2019. [19] R. J. Little and D. B. Rubin. Statistical analysis with missing data. John Wiley & Sons, 2019. [20] B. McMahan, E. Moore, D. Ramage, S. Hampson, and B. A. y Arcas. Communication-efficient learning of deep networks from decentralized data. In Artificial intelligence and statistics, pages 1273--1282. PMLR, 2017. [21] N. Patki, R. Wedge, and K. Veeramachaneni. The synthetic data vault. In 2016 IEEE International Conference on Data Science and Advanced Analytics (DSAA), pages 399--410, 2016. [22] D. B. Rubin. Inference and missing data. Biometrika, 63(3):581--592, 1976. [23] J. L. Schafer. Analysis of incomplete multivariate data. CRC press, 1997. 21
PRIME AI paper
[24] R. Schnell, T. Bachteler, and J. Reiher. Privacy-preserving record linkage using bloom filters. BMC medical informatics and decision making, 9(1):1--11, 2009. [25] J. H. Seo, J. H. Cheon, and J. Katz. Constant-round multi-party private set union using reversed laurent series. In International Workshop on Public Key Cryptography, pages 398--412. Springer, 2012. [26] J. Sun, X. Yang, Y. Yao, A. Zhang, W. Gao, J. Xie, and C. Wang. Vertical federated learning without revealing intersection membership. arXiv preprint:2106.05508, 2021. [27] B. Tu, Y. Bai, C. Zhang, Y. Cao, and Y. Chen. Fast enhanced private set union in the balanced and unbalanced scenarios. Cryptology ePrint Archive, 2025. [28] B. Tu, Y. Chen, Q. Liu, and C. Zhang. Fast unbalanced private set union from fully homomorphic encryption. In Proceedings of the 2023 ACM SIGSAC Conference on Computer and Communications Security, pages 2959--2973, 2023. [29] E. Uzun, S. P. Chung, V. Kolesnikov, A. Boldyreva, and W. Lee. Fuzzy labeled private set intersection with applications to private {Real-Time} biometric search. In 30th USENIX Security Symposium (USENIX Security 21), pages 911--928, 2021. [30] F. Wang, B. Mi, and R. Zeng. Efficient private set intersection for vertical federated learning in iov. In International Conference on Frontiers in Cyber Security, pages 120--130. Springer, 2024. [31] J. Wang, E. X. Huang, P. Duan, H. Wang, and K.-Y. Lam. Psa: private set alignment for secure and collaborative analytics on large-scale data. IEEE Transactions on Dependable and Secure Computing, 2025. [32] J. Wen, Z. Zhang, Y. Lan, Z. Cui, J. Cai, and W. Zhang. A survey on federated learning: challenges and applications. International journal of machine learning and cybernetics, 14(2):513--535, 2023. [33] Y. Xi, Y. Guo, S. Xu, C. Cai, and X. Jia. Private sample alignment for vertical federated learning: An efficient and reliable realization. IEEE Transactions on Information Forensics and Security, 2025. [34] Q. Yang, Y. Liu, Y. Cheng, Y. Kang, T. Chen, and H. Yu. Horizontal federated learning. In Federated learning, pages 49--67. Springer, 2022. [35] C. Zhang, Y. Chen, W. Liu, L. Peng, M. Hao, A. Wang, and X. Wang. Unbalanced private set union with reduced computation and communication. In Proceedings of the 2024 on ACM SIGSAC Conference on Computer and Communications Security, pages 1434--1447, 2024. [36] C. Zhang, Y. Chen, W. Liu, M. Zhang, and D. Lin. Linear private set union from {Multi-Query} reverse private membership test. In 32nd USENIX Security Symposium (USENIX Security 23), pages 337--354, 2023. [37] Z. Zhao, X. Liang, H. Huang, and K. Wang. Deep federated learning hybrid optimization model based on encrypted aligned data. Pattern Recognition, 148:110193, 2024.
22