Paper deep dive
Sherpa.ai Privacy-Preserving Multi-Party Entity Alignment without Intersection Disclosure for Noisy Identifiers
Daniel M. Jimenez-Gutierrez, Enrique Zuazua, Georgios Kellaris, Joaquin Del Rio, Oleksii Sliusarenko, Xabi Uribe-Etxebarria
Intelligence
Status: succeeded | Model: Gemma-4-26B-A4B | Prompt: intel-v1 | Confidence: 96%
Last extracted: 4/26/2026, 11:02:29 PM
Summary
The paper introduces the Sherpa.ai multi-party Private Set Union (PSU) protocol designed for Privacy-Preserving Entity Alignment (PPEA) in Vertical Federated Learning (VFL). Unlike traditional Private Set Intersection (PSI) which leaks intersection membership, this protocol uses a commutative encryption-based approach to construct a shared universal index from the union of identifiers. It supports both an order-preserving (exact) matching regime and an unordered (noisy) matching regime using n-gram tokenization to handle typographical errors and formatting inconsistencies. The protocol is designed to be scalable for multiple parties and avoids the need for a trusted third party, making it suitable for real-world cross-domain collaborations like healthcare or finance.
Entities (7)
Relation Signals (4)
Sherpa.ai → developed → Sherpa.ai PSU protocol
confidence 100% · In this paper, we introduce the Sherpa.ai multi-party PSU protocol for VFL
Sherpa.ai PSU protocol → enables → Privacy-Preserving Entity Alignment
confidence 100% · the Sherpa.ai multi-party PSU protocol for VFL, a PPEA method that hides intersection membership
Commutative Encryption → isbasedon → Diffie-Hellman key exchange
confidence 100% · formalize the commutative encryption process based on the Diffie–Hellman key exchange principle
n-gram tokenization → supports → noisy matching
confidence 100% · n-gram tokenization preprocessing step that enhances robustness to formatting inconsistencies and typographical errors, supporting both order-preserving (exact) and unordered (noisy) matching
Cypher Suggestions (0)
No Cypher suggestions yet.
Abstract
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 this http URL 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.
Tags
Links
- Source: https://arxiv.org/abs/2604.19219v1
- Canonical: https://arxiv.org/abs/2604.19219v1
Trouble viewing inline? Open PDF directly →
Full Text
65,068 characters extracted from source content.
Expand or collapse full text
Sherpa.ai Privacy-Preserving Multi-Party Entity Alignment without Intersection Disclosure for Noisy Identifiers Sherpa.ai research@sherpa.ai 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. Income Gender ID $80,000 Male John Doe $85,000 Female Jane Smith Zip Code Address ID 04173 42 Oak Ave John Doe 07204 5 River Lane Jane Smith Party A Party B Zip Code Address Income Gender ID 04173 42 Oak Ave $80,000 Male John Doe 07204 5 River Lane $85,000 Female Jane Smith Privacy Preserving Entity Alignment Aligned Data 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 arXiv:2604.19219v1 [cs.CR] 21 Apr 2026 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 (i) 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 (i) 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 ann-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 toPparties and introducesn-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 introducingn-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 onn-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, (i) naturally extends to more than two parties via a commutative-encryption design, and (i) 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. Standard Entity Alignment (PSI) Standard PSU Sherpa.ai PSU Raw identifiers exchanged✓ No✓ No✓ No Intersection revealed ✗ Yes✓ No✓ No Multi-party✓ Yes✗ No✓ Yes Noisy alignment✗ No✗ No✓ Yes Table 1: Comparison of the privacy properties of different entity alignment protocols. 4 PRIME AI paper 3 Problem Formulation We consider a set ofPparties wishing to perform VFL. Without loss of generality, assume there areP −1 passive parties F 0 ,...,F P−2 and an active party F P−1 . For eachk ∈0,...,P−1, partyF k owns a datasetD k = ⃗x i k i∈0,...,N k −1 consisting ofN k data examples (rows), where each example (or row) ⃗x i k ∈R d k , N k ∈N\0 and d k ∈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 byd match the number of such identifying features (this d match is the same for every party). Let π k :R d k −→R d match , be the projection that extracts thed match identifying attributes from partyF k ’s feature space. Each party can then derive from its dataset a set of raw identifiers (one identifier per example) as I raw,k : = π k ⃗x i k | k = 0,...,N k − 1 . fork= 0,...,P −1. In other words,I raw,k is the set of identifier tuples (such as personal data fields) for the records held by partyF k . 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 [ k=0 I raw,k .(3.1) Let N =|U| be the total number of unique identifiers across all parties. 2.Define Universal Indices. Assign each identifier in the unionUa 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 partyF k , determine a mapping φ k :0,...,N k − 1−→ V,(3.2) which maps each local indexi(the position of a record in partyF k ’s dataset) to the corresponding universal index inV. In other words, ifπ k (x i k )∈Uends up as thej-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 inI raw,k (which may be a composite of multiple fields) into a set of overlapping substrings of lengthn, known as n-grams. This helps standardize the format and allows for partial matching to accommodate error tolerance. 2. Hashing of Identifiers: Then-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 hashedn-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 ofn-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 ofn-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, letpbe a safe prime, i.e.,pis prime and (p−1)/2 is also prime. Denote byZ p = [0] p , [1] p ,..., [p− 1] p the ring of integers modp, and byZ ∗ 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 ofZ ∗ p consisting of all non-zero squares modp. By using the properties of the additive group(Z p , +)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 partyF k and each raw identifierid∈ I raw,k , the identifier is decomposed into n-grams. An identifier idmay be a single string (e.g., a customer ID) or a tuple of attributes (e.g., first name, last name, address, etc.). Formally, for everyk= 0,...,P −1, partyF k possesses an identifiers setI raw,k . A raw identifierid∈ I raw,k is a vector id = id 1 ,..., id d match ∈R d match . Without loss of generality, assume each componentid r 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 = id 1 ,..., id d match ∈S d match . All partiesF 0 ,...,F P−1 agree on the lengthn r of then-grams in which componentrof identifiers will be split, for eachr ∈1,...,d match . Moreover, in order to perform a propern-grams splitting, they need to agree on a length for the string of each component of identifiers: letL r be the established length of the component r of identifiers; if n r > L r , we redefine L r ← n r . For every k = 0,...,P − 1, for any identifier id∈ I raw,k , for each r ∈1,...,d match , • if the length of the string id r is smaller than L r , then L r − length (id r ) empty spaces are added; •if the length of the stringid r is greater thanL r , then the lastlength (id r )− L r characters are removed. At this stage, we can separateid r inL r − n r + 1n r -grams, using a sliding window approach. Namely, for l∈0,...,L r − n r , the l-th n r -grams of id r is c r,l : = (id r,l ,..., id r,l+n r −1 ). For k = 0,...,P − 1, set I separated-raw,k : = (c i,r,l ) i,r,l i ∈ 0,...,N k − 1, r ∈ 1,...,d match , l ∈ 1,...,L r − n r + 1 . The motivation forn-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 theirn-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 ofn-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 ofn-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 itsn-grams to obfuscate their values and to enable efficient cryptographic processing. This second part of our solution addresses the hashing ofn-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 I k . We have I k = n h (c) c∈ I separated-raw,k o . 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 identicaln-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 groupQR Z ⋆ p , defined earlier, as the space for commutative encryption. We choose a large safe primep(on the order of 2048 bits or larger for security) and letq= (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 partyF k generates a secret exponents k (in practice, multiple exponents per party are used for different protocol phases, denoteds k 1 ,s k 2 ,s k 3 ∈ 0,...,q−1). We define the encryption functione s for exponents applied on hashed token x∈Z p as: e s,one component (x) = x s mod p.(4.2) We extend this to an identifier’s tokens (across all features) by applyinge s to each token: let an identifier be represented as a tuple (x r,l ) whereris the index of the feature (from 1 tod match ) andlis the index of the n-gram within that feature (from 1 toL r − n+ 1, assumingL r is the length of featurerfor that identifier). Next, we define the following vectorized encryption functions. Let s∈0,...,q− 1 and e s : d match Y r=1 " L r −n r +1 Y l=1 Z p # −→ d match Y r=1 " L r −n r +1 Y l=1 Z p # (x r,l ) r∈1,...,d match ,l∈1,...,L r −n r +1 7−→ x s r,l r∈1,...,d match ,l∈1,...,L r −n r +1 , where σ :0,...,N k − 1−→0,...,N k − 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 inZ p ,e s 1 ◦ e s 2 =e s 2 ◦ e s 1 , for somes 1 ,s 2 in0,...,q− 1. Because exponentiation is applied independently to each token, two identical identifiers (same tokens in the same order) encrypted with the same exponentsyield identical outputs, while identifiers that differ in any token produce different encrypted outputs (up to hash or exponent collisions). Moreover, sincee s 1 ◦ e s 2 =e s 2 ◦ e s 1 for anys 1 ,s 2 ∈0,...,q−1, applying exponents in any order is equivalent to a single exponentiation by s 1 s 2 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 subgroupQR(Z ∗ p ), i.e., the mappingx7→ x s mod pfor 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 (i) 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 double- encryption 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ˆe s as the operation of applyinge s to an entire set of identifiers (for example, an entire party’s setI k ) and also randomly permuting the order of identifiers. Specifically, for everyk= 0,...,P −1, be s : N k −1 Y k=0 d match Y r=1 " L r −n r +1 Y l=1 Z p # −→ N k −1 Y k=0 d match Y r=1 " L r −n r +1 Y l=1 Z p # (x i,r,l ) i∈0,...,N k −1,r∈1,...,d match ,l∈1,...,L r −n r +1 7−→ x s σ(i),r,l i∈0,...,N k −1,r∈1,...,d match ,l∈1,...,L r −n r +1 , where σ :0,...,N k − 1−→0,...,N k − 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 set0,...,N k − 1used by partyF k during encryption. The commutativity still holds: applyingbe s 1 and thenbe s 2 (with independent random permutations) to a vector of identifiers yields the same vector asbe s 2 followed bybe s 1 – 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. Lets 1 ,...,s n ⊂0,...,q− 1, for some n∈N\0. Let n Y i=1 e s i = e s n ◦·◦ e s 1 and n Y i=1 be s i = be s n ◦·◦be s 1 . Whenever the index range is empty, i.e., whenn 1 > n 2 in an expression of the form Q n 2 i=n 1 e s i , the corresponding composition is defined to be the identity map. Since the composition of encryption functions is commutative, the product operator Q 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 identifierid∈ I raw,k is first tokenized inton-grams per feature and hashed intoI k ⊂ Q d match r=1 Q L r −n r +1 l=1 QR (Z ∗ p ) as in Section 4.2; the relative order ofn-grams within each feature is treated as semantically meaningful. The goal is to compute a universal set of encrypted identifiersUthat represents the union of all parties’ (ordered) hashed identifiers while revealing nothing about intersection membership, together with local mappingsφ k :I raw,k →Vthat 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 partyF k samples exponentss k 1 ,s k 2 ,s k 3 ∈ 0,...,q−1. Using the commutative mappinge s (·) = (·) s mod pand its setwise/shuffled liftbe s , the parties cyclically applybe s k 1 to everyI k 1 , yielding Q l be s l 1 I k 1 at the initiatorF k 1 without exposing which tokens are shared. 2.Provisional union and re-randomization. The active partyF P−1 forms the duplicate-free provisional unionI un,prov = S k Q l be s l 1 I k and encodes it by applying Q l be s l 3 s l 2 , producing the final encrypted universal identifiers U = Q l be s l 3 s l 2 I un,prov , which are then broadcast to all parties. 3.Private matching and index assignment. EachF k locally re-encrypts its ownI k withe s k 2 and relays the result through a second commutative pass of exponentss ℓ 1 ,s ℓ 2 ,s ℓ 3 . By commutativity, every element ofI k is transformed into the same ciphertext as its counterpart inU, enablingF k 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 subgroupQR(Z ∗ p ) under the decisional Diffie–Hellman assumption, together with full-set shufflingbe s 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. Data: For every k = 0,...,P − 1, a set of hashed identifiers I k ⊂ Q d match r=1 Q L r −n r +1 l=1 QR Z ⋆ p , with p prime andq : = p−1 2 prime. All the operations on identifiers will be taken modulop. 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 : I raw,k −→ V associating each identifier id∈ I raw,k (of the local dataset D k ) to the corresponding index in the set of universal indices (UI) V . Initialization. for k ← 0 to P − 1 do partyF k randomly generates three secret exponents s k 1 , s k 2 and s k 3 in 0,...,q− 1. These will be used in different rounds of encryption. First Round – Commutative Encryption of Local Sets. for k 1 ← 0 to P − 1 do partyF k 1 computes be s k 1 1 I k 1 , and sends it to the next partyF k 1 +1 (indices mod P so that e.g. F P is F 0 ). We now start an additional encryption pipeline, where each subsequent partyF k 2 (fork 2 =k 1 + 1 up toP −1 and then wrapping around to 0,...,k 1 − 1) encrypts as follows. for k 2 ← 0,k 2 ,̸= k 1 to P − 1 do When partyF k 2 receives h Q k 2 −1 l=0,l̸=k 1 be s l 1 i be s k 1 1 I k 1 , it computes " k 2 Y l=0,l̸=k 1 be s l 1 # be s k 1 1 I k 1 , and sends it toF k 2 +1 . WhenF k 1 receives back Q P−1 l=0 be s l 1 I k 1 , it stops and sends it toF P−1 . Union Computation (Provisional). F P−1 performs the union (repetitions must be avoided) I un,prov : = P−1 [ k=0 P−1 Y l=0 be s l 1 I k . Now the active partyF P−1 orchestrates a second round of encryption on the provisional union to further blind the values. for k ← P − 1 to 0 do partyF k computes P−1 Y l=k be s l 3 s l 2 I un,prov , and sends it toF k−1 . OnceF P−1 receives P−1 Y l=0 be s l 3 s l 2 I un,prov , partyF P−1 determine U, the set of encrypted universal identifiers (UID) U : = P−1 Y l=0 be s l 3 s l 2 I un,prov . 12 PRIME AI paper Algorithm 1: PSU protocol, with order (continued). for k ← 0 to P − 1 do PartyF P−1 sends the set of encrypted universal identifiers (UID) to partyF k . 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 k 1 ← 0 to P − 1 do for any x∈ I k 1 , partyF k 1 computes e s k 1 2 x and sends it toF k 1 +1 . for k ← 1 to P − 1 do WhenF k 1 +k receives e s k 1 2 k−1 Y l=1 e s k 1 +l 3 s k 1 +l 2 s k 1 +l 1 x, it computes e s k 1 2 k Y l=1 e s k 1 +l 3 s k 1 +l 2 s k 1 +l 1 x, and sends it toF k 1 +k . WhenF k 1 receives back e s k 1 2 P−1 Y k 2 =0, k 2 ̸=k 1 e s k 2 3 s k 2 2 s k 2 1 x, partyF k 1 computes P−1 Y k 2 =0 e s k 2 3 s k 2 2 s k 2 1 x and partyF k 1 stores ̃φ k 1 : I k 1 −→ U x7−→ P−1 Y k 2 =0 e s k 2 3 s k 2 2 s k 2 1 x and determines φ k 1 : I k 1 −→ 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 inUjust 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 ofP parties, resulting inPtransmissions per dataset (total transmissions ofP 2 in the worst case). The second round similarly involvesPtransmissions of the union (which sizeNcould be larger than individual set sizes). The final matching step involves each identifier being sent throughPparties (soN k ×Poperations 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 ofn-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,e s mapped each token but kept its position fixed in its feature. Now, we modifye s to also randomly permute the positions of then-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 featurer, letL r − n+ 1 be the total number ofn-grams for that feature in a fully formatted identifier (assuming no missing tokens). We assume that each identifier has at least⌈λ(L r − n+ 1)⌉tokens for featurer(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 e s : d match Y r=1 " L r −n r +1 Y l=1 Z p # −→ d match Y r=1 " L r −n r +1 Y l=1 Z p # (4.3) (x r,l ) r∈1,...,d match ,l∈1,...,L r −n r +1 7−→ x s r,ν r (l) r∈1,...,d match ,l∈1,...,L r −n r +1 and, for every k = 0,...,P − 1, be s : N k −1 Y j=0 d match Y r=1 " L r −n r +1 Y l=1 Z p # −→ N k −1 Y j=0 d match Y r=1 " L r −n r +1 Y l=1 Z p # (x j,r,l ) j∈0,...,N k −1,r∈1,...,d match ,l∈1,...,L r −n r +1 7−→ x s σ(j),r,ν r (l) j∈0,...,N k −1,r∈1,...,d match ,l∈1,...,L r −n r +1 withν r :1,...,L r − n r + 1−→1,...,L r − n r + 1andσ:0,...,N k − 1−→0,...,N k − 1random permutations (the index r ∈1,...,d match ). Hereν r is a permutation of the positions for featurer. 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 inZ p ,e s 1 ◦e s 2 ≃ e s 2 ◦e s 1 , for somes 1 ,s 2 in0,...,q− 1, the symbol ≃meaning equality up to a permutation of then-grams. Namely, forr ∈ 1,...,d match , there exist a permutation ω r :1,...,L r − n r + 1−→1,...,L r − n r + 1, such that, for any (x r,l ) r∈1,...,d match ,l∈1,...,L r −n r +1 ∈ d match Y r=1 " L r −n r +1 Y l=1 Z p # , we have e s 1 ◦ e s 2 (x r,l ) r∈1,...,d match ,l∈1,...,L r −n r +1 = e s 2 ◦ e s 1 x r,ω r (l) r∈1,...,d match ,l∈1,...,L r −n r +1 (4.4) 14 PRIME AI paper (x i,j,r,l ) i∈0,...,n,j∈0,...,N k −1,r∈1,...,d match ,l∈1,...,L r −n r +1 7−→ ( ̃x j,r,l ) j∈ 0,..., b N−1 ,r∈1,...,d match ,l∈1,...,L r −n r +1 , Let s 1 ,...,s n ⊂0,...,q− 1, for some n∈N\0. Define n Y i=1 e s i = e s n ◦·◦ e s 1 and n Y i=1 be s i = be s n ◦·◦be s 1 . In products Q n 2 i=n 1 ... , if n 1 > n 2 , the result is defined as the identity. Let b N : = P n+1 k=0 N k . We define the concatenation operator as Λ : P−1 Y k=0 N k −1 Y j=0 d match Y r=1 L r −n r +1 Y l=1 Z p ! −→ b N−1 Y j=0 d match Y r=1 L r −n r +1 Y l=1 Z p ! and ̃x j,r,l = x i, b j,r,l , by setting b j : = j− P k−1 k=0 N k and for k ∈0,...,P − 1, j ∈ ( k−1 X k=0 N k ,..., i X k=0 N k − 1 ) , r ∈1,...,d match , l∈1,...,L r − n r + 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 (x r,l ) r∈ 1,...,d match ,l∈ 1,...,p 1,r ∈ d match Y r=1 " p 1,r Y l=1 Z p # and (y r,l ) r∈ 1,...,d match ,l∈ 1,...,p 2,r ∈ d match Y r=1 " p 2,r Y l=1 Z p # . Threshold λ∈ (0, 1]. Assume p i,r ∈ [⌈λL r − n r + 1⌉,L r − n r + 1], for r ∈1,...,d match . Result: 1 if the encrypted identifiers match. 0 otherwise. If 1, return list match . Initialization. Set list match ← [ ]. Comparison. for r ← 1 to d match do Set list match,r ← [ ]. for l 1 ← 0 to p 1,r do for l 2 ← 0 to p 2,r do If x r,l 1 = y r,l 2 and l 1 does not belong to list match,r , append l 1 to list match,r . If the cardinality of list match,r is greater than ⌈λL r − n r + 1⌉, return 0. Else, append list match,r to list match . Return 1 and list match . Remark 4.1 (Equivalence). Observe that algorithm (2) defines a relation between d match Y r=1 " p 1,r Y l=1 Z p # and d match Y r=1 " p 2,r Y l=1 Z p # , where two respective elements x : = (x r,l ) r∈1,...,d match ,l∈1,...,p 1,r and y : = (y r,l ) r∈1,...,d match ,l∈1,...,p 2,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. Data: For every k = 0,...,P − 1, a set of hashed identifiers I k ⊂ Q d match r=1 Q L r −n r +1 l=1 QR Z ⋆ p , with p prime andq : = p−1 2 prime. All the operations on identifiers will be taken modulop. 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,...,N k − 1−→ V associating each indexiof the local datasetD k to the corresponding index in the set of universal indices (UI) V . Initialization. for k ← 0 to P − 1 do partyF k randomly generates s k 1 , s k 2 and s k 3 in 0,...,q− 1. First Round – Commutative Encryption of Local Sets. for k 1 ← 0 to P − 1 do partyF k 1 computes be s k 1 1 I k 1 , and sends it toF k 1 +1 . for k 2 ← 0,k 2 ,̸= k 1 to P − 1 do WhenF k 2 receives h Q k 2 −1 l=0,l̸=k 1 be s l 1 i be s k 1 1 I k 1 , it computes " k 2 Y l=0,l̸=k 1 be s l 1 # be s k 1 1 I k 1 , and sends it toF k 2 +1 . WhenF k 1 receives back Q P−1 l=0 be s l 1 I k 1 , it stops and sends it toF P−1 . Union Computation (Provisional). F P−1 define a vector V un,prov : = Λ P−1 Y l=0 be s l 1 I 0 ,..., P−1 Y l=0 be s l 1 I k ,..., P−1 Y l=0 be s l 1 I n ! . We have b N = length first axis (V un,prov ).(4.5) for k 1 ← 0 to b N − 1 do for k 2 ← k 1 to b N − 1 do F P−1 applies algorithm 2 to V un,prov,k 1 , with V un,prov,k 2 . If the output is 1, remove V un,prov,k 2 and remove from V un,prov,k 1 n-grams indicated in list match . From elements of V un,prov,k 1 , partyF P−1 removes randomly components to reduce length of each element to ⌈λL r − n r + 1⌉.F P−1 defines I un,prov : = n V un,prov,l l∈1,..., length first axis (V un,prov ) o , where length first axis (V un,prov ) may have changed, with respect to (4.5), because of the removals. for k ← P − 1 to 0 do partyF k computes P−1 Y l=k be s l 3 s l 2 I un,prov , and sends it toF k−1 . OnceF P−1 receives P−1 Y l=0 be s l 3 s l 2 I un,prov , 17 PRIME AI paper Algorithm 3: PSU protocol, without order (continued). for i← 1 to P − 1 do partyF P−1 sends P−1 Y l=0 be s l 3 s l 2 I un,prov , toF k . PartyF P−1 determines U the set of encrypted universal identifiers (UID) U : = P−1 Y l=0 be s l 3 s l 2 I un,prov . for k ← 0 to P − 1 do PartyF P−1 sends the set of encrypted universal identifiers (UID) to partyF k . Private Matching of Identifiers. for k 1 ← 0 to P − 1 do for any x∈ I k 1 , partyF k 1 computes e s k 1 2 x and sends it toF k 1 +1 . for k ← 1 to P − 1 do WhenF k 1 +k receives e s k 1 2 k−1 Y l=1 e s k 1 +l 3 s k 1 +l 2 s k 1 +l 1 x, it computes e s k 1 2 k Y l=1 e s k 1 +l 3 s k 1 +l 2 s k 1 +l 1 x, and sends it toF k 1 +k . WhenF k 1 receives back e s k 1 2 P−1 Y k 2 =0, k 2 ̸=k 1 e s k 2 3 s k 2 2 s k 2 1 x, partyF k 1 computes P−1 Y k 2 =0 e s k 2 3 s k 2 2 s k 2 1 x.(4.6) PartyF k 1 checks the existence of an elementˆx∈ U, having⌈λL r − n r + 1⌉ n-grams in common, with (4.6). If this element exists, partyF k 1 stores ̃φ k 1 : I k 1 −→ U x7−→ ˆx and determines φ i 1 : I i 1 −→ V. 18 PRIME AI paper Remark 4.2. In case the order ofn-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 (x r,l ) r∈1,...,d match ,l∈1,...,L r −n r +1 ∈ d match Y r=1 " L r −n r +1 Y l=1 Z p # ,(4.7) is represented by a Bloom filter (bitarray) b∈0, 1 p by setting b (x r,l ) = 1,∀ (r,l)∈1,...,d match ×1,...,L r − n r + 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 bothn-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 (i) 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 (i) 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 privacy- preserving 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. Chatzi- giannakis, 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 privateReal-Timebiometric 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 fromMulti-Queryreverse 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