xDup: Privacy-Preserving Deduplication for Humanitarian Organizations using
Fuzzy PSI This is the full version of the conference paper published at the IEEE Symposium on Security and Privacy 2026. This version includes extended appendices. Please cite the conference version.
Tim Rausch, Sylvain Chatel, Wouter Lueks
arXiv:2604.08019v1 [cs.CR] 9 Apr 2026
CISPA Helmholtz Center for Information Security, Saarbrücken, Germany {tim.rausch, sylvain.chatel, lueks}@cispa.de Abstract—Humanitarian organizations help to ensure people’s livelihoods in crisis situations. Typically, multiple organizations operate in the same region. To ensure that the limited budget of these organizations can help as many people as possible, organizations perform cross-organizational deduplication to detect duplicate registrations and ensure recipients receive aid from at most one organization. Current deduplication approaches risk privacy harm to vulnerable aid recipients by sharing their data with other organizations. We analyzed the needs of humanitarian organizations to identify the requirements for privacy-friendly cross-organizational deduplication fit for real-life humanitarian missions. We present xDup, a new practical deduplication system that meets the requirements of humanitarian organizations and is two orders of magnitude faster than current solutions. xDup builds on Fuzzy PSI, and we present otFPSI, a concretely efficient Fuzzy PSI protocol for Hamming Space without input assumptions. We show that it is more efficient than existing Fuzzy PSI protocols.
1. Introduction Humanitarian organizations assist people who have been affected by crises and situations caused by, for example, natural disasters, armed conflict, health crises, or famine. They support people’s livelihoods by providing essential goods like food or hygiene items, and (health) services. Yet, the financial resources of these organizations are limited. Thus, they take measures to ensure that their limited resources can help as many people as possible. Our conversations with humanitarian organizations highlighted deduplication [14], [27], [29], [40] as a key measure. In crisis situations, typically many organizations are involved in assisting affected populations [26], [50]. As a result, aid recipients could – accidentally or on purpose – register with several organizations at once, potentially resulting in others not receiving the assistance they need [85]. Duplicate registrations are estimated as high as 15 % [29], [50]. A deduplication process enables organizations to check whether newly registered recipients are already registered with another organization and enables organizations to take action in these cases. Any deduplication system must provide strong privacy guarantees as humanitarian aid recipients
are an extremely vulnerable population [102]. For recipients, refusing to receive aid is typically not an option – yet they can suffer dire consequences when their privacy is not sufficiently safeguarded [23], [46]. Organizations can deduplicate recipients based on three categories of data: unique identifiers, biometrics, and biographical data [50]. Each approach has its unique challenges: Reliable unique identifiers like (government-issued) identity documents are often unavailable in the regions and settings humanitarian organizations operate in. Biometric data (e.g., fingerprints, iris scans) [36], [100] is inherently sensitive, and its collection can be seen as a substantial intrusion into recipients’ privacy. Biographical data of recipients (e.g., name, date of birth, gender) is typically manually collected during registration and may be error-prone, requiring privately comparing inconsistent data [28], [41], [50]. Organizations increasingly use biographical data [27], [29], [39], [42] to abstain from the highly privacy-invasive collection of biometric data [25], [45], [48], [73], [84] and to avoid relying on externally issued unique identifiers. In this paper, we address the challenge of privacypreserving deduplication based on biographical data by proposing xDup, a new cross-organizational deduplication system. We elicit requirements for such a system from several discussions with organizations and a review of humanitarian publications, and tailor xDup to these requirements: (1) Privacy of recipients must be ensured: No information about non-duplicates should be leaked to other organizations, protecting not only recipients but also NGOs. (2) The deduplication process must be fine-tuned to prioritize a low false-positive rate, so that recipients are not falsely flagged. False positives require manual handling, causing manual effort and leakage about non-duplicate registrations. (3) The system must scale: Each organization records in the order of 100 000 registrations [33], [98], [99], and may register thousands of new recipients per week [86], [87]. Existing building blocks cannot satisfy these requirements. Fuzzy matching techniques [31], [32], [54], [64], [74], [81], [82], [91], [92] based on Bloom filters are efficient but susceptible to privacy leakage [22], [62], [70], [94], [95]. To preserve privacy, many approaches have been proposed that use secure multi-party computation (SMC) to privately compare pairs of records. While these methods
support a large range of similarity metrics – and maintain privacy – they are inefficient at the scale of typical aid programs. Differential privacy techniques can reduce the number of comparisons [44], but cannot guarantee the absence of leakage of recipients’ data. Finally, existing Fuzzy Private Set Intersection (FPSI) protocols [6], [13], [16], [19], [35], [61], [77], [88], [89], [90] solve a related problem, but require embedding registration records into a metric space. However, existing embeddings that preserve the similarity of biographical data [8], [66], [80] typically embed into a highdimensional Euclidean space, and existing FPSI protocols for Euclidean space do not scale well to high dimensions. In this paper, we propose xDup, a new deduplication system that combines an embedding into Hamming space with an FPSI protocol for Hamming space: Organizations locally transform their records into representations in Hamming space and then use an FPSI protocol to find pairs of similar records in Hamming space. Existing FPSI protocols are not applicable since they rely on potentially unmet assumptions on the structure of input data, approximate with insufficient accuracy, or are inefficient in our scenario (see §7.2). We thus present otFPSI, a practically efficient FPSI mechanism that builds on SHADE [11] and relies only on Oblivious Transfer (OT). We evaluate otFPSI extensively and show that, in this setting, otFPSI outperforms all proposed FPSI protocols. The main strength of otFPSI is not only that it is more efficient for many parameters, but it does so while returning exact results and without assumptions on the structure of input data. For our target size, our system takes 3 h to perform deduplication. This is a reduction by 84 × compared to existing methods (see §7.5). For ethical reasons, we evaluated our system on a synthetic dataset and did not work with real humanitarian data. We modeled duplicates based on common errors and show that xDup’s embedding with an exact FPSI protocol only misses 0.6 % of duplicates. Our Contribution. We summarize our contributions. ✓ We gather and formalize requirements for a humanitarian deduplication system working on biographical data based on literature and conversations with NGOs (§2). ✓ We propose xDup, an end-to-end private deduplication system that is fit for use by humanitarian organizations (§4). ✓ We show that deduplication can be reduced to Hamming FPSI, retaining the accuracy of plaintext matching (§5) ✓ We present otFPSI, an OT-based FPSI protocol that does not rely on input assumptions (§6). ✓ Our extensive benchmarks show that this approach is more efficient than all existing FPSI protocols (§7.2). ✓ We evaluate the end-to-end cost of xDup and show that it satisfies the real-world humanitarian requirements (§7.4).
2. System Overview We present the system model and design overview of
xDup. The definition of problem, entities, and requirements
result from a review of humanitarian deduplication [2], [14], [27], [28], [29], [30], [39], [40], [41], [42], [50], [98], [99] and several discussions with humanitarian organizations.
2.1. Entities Our deduplication system involves the following entities: Field Teams. Field teams are responsible for providing humanitarian aid (e.g., food, essential items, services) to aid recipients. Field teams can be regional and country offices of large international humanitarian organizations (e.g., ICRC, UN OCHA, MSF, and UNRWA), or local organizations (e.g., national societies of the Federation of the Red Cross). Field teams operate aid programs, and register recipients to whom they provide aid. Multiple independent field teams can operate in the same area. Field teams are local, often operating in difficult circumstances in crisis-affected areas with limited digital resources: Hardware might be limited to laptops or simple desktops, and internet connectivity may not be reliable. To effectively distribute aid, field teams typically rely on access to their recipients’ registration data. Headquarters. Many field teams are part of a larger international humanitarian organization (NGO), whose headquarters (e.g., located in Geneva, Switzerland, or New York) have access to better resources and connectivity. Headquarters do not directly take part in the aid distribution or deduplication process. Yet, they want to ensure a fair distribution of humanitarian aid. We use headquarters to provide the computing resources and connectivity necessary to operate our privacy-friendly deduplication system. Headquarters of large organizations may be protected by privileges and immunities [7]. Recipients. People in crisis-affected areas want to receive aid from humanitarian organizations. To do so, they register with a field team or aid program as an aid recipient. As part of this process, they provide basic biographical information (e.g., first and last name, date of birth, place of origin, and information about the household composition). Field teams use this information to register recipients and allocate and distribute appropriate assistance. As a result of the field conditions, the recorded biographical information often contains errors. For example, names might be recorded with slight variations due to differences in transcribing, and dates of birth are sometimes approximated because the true date of birth is unknown. As registration is a manual process, simple typos can also occur. Deduplication should work despite such differences in records. We assume that registration data is not maliciously incorrect (see §2.6). Additionally, strong unique identifiers like personal ID numbers or phone numbers are often not available, or unreliable. While recipients are more likely to have a phone number than a personal ID, these numbers are subject to frequent change or shared, especially as people move around. When available, field teams record these identifiers, but this is often not the case. Therefore, in our work, we assume unique identifiers are not available.
2.2. Overview of Humanitarian Deduplication We outline the high-level registration and deduplication process resulting from conversations with NGOs and as described in documents published by NGOs [27], [30], [40].
Step 1: Find potential duplicates
System Inputs: new + old registrations Output: potential duplicate registrations
Step 2: Adjudication of duplicates Inputs: - Potential duplicate registrations - Auxiliary records information Output: - Discuss and agree on the duplicates
Figure 1. High-level deduplication process
Most organizations currently use an asynchronous deduplication process, which xDup supports. Yet, xDup can also provide an online deduplication mechanism (like Janus [33]), but this still requires asynchronous manual verification. Step 0. Registering Aid Recipients. Field teams register aid recipients for the aid programs they operate. As part of the registration process, and to fit recipients’ needs, field teams collect biographical information (names, date of birth, etc.) from aid recipients. As explained above, this information is not necessarily fully correct, and small errors are possible. During the registration process, field teams immediately perform local deduplication to verify that the new recipient did not already register with them. Step 1. Identifying Potential Duplicates. Because NGOs have limited resources to provide assistance, they wish to help as many people as possible. Thus, they want to detect recipients that register – purposefully or not – with multiple teams and would unfairly receive additional assistance. The goal of our system is to identify these crossorganizational duplicates, i.e., newly registered recipients that are also registered with any other field team active in the same region. Because registration data can be inconsistent, the deduplication process must be robust to small differences in registration data. It is this identification of potential crossorganizational duplicates that we focus on in our work. As we explain in Section 3, current approaches fail to protect the privacy of recipients, are impractical, or fail to detect (most) duplicates. xDup provides strong privacy protection, is efficient, and finds 99.4 % of duplicates. As field teams may not have access to reliable network connections, the system needs to support offline operation: The field teams need to be able to perform the registration offline and submit their registrations to the deduplication system at a later time. However, if a network connection is available, an online operation mode is preferable so that the field team immediately learns about possible duplicates. This feedback allows field teams to directly gather additional information from the recipient – which may be especially useful in cases of accidental duplicate registrations. xDup supports both modes of operation: an offline mode to deduplicate a batch of new registrations, and an online mode to deduplicate a single new registration in real-time. Step 2. Verifying Duplicates. The final step is to verify which potential duplicates are true duplicate registrations. This is a manual process: In fixed intervals, the deduplication committee gathers and discusses the potential duplicates
[27] (independent of whether they were discovered in online or offline mode). Each field team sends a representative who has access to the list of new potential duplicates as well as that team’s full registration information. For each identified duplicate, the representatives compare the full registration data to assess whether this recipient is truly a duplicate. The manual nature of this process rules out potential false positives, ensures that field teams can incorporate all information available about aid recipients (not all of this information is necessarily used during step 1), and that appropriate measures can be taken when they do detect duplication.
2.3. Goals and Non-Goals The goal in our work is to build a cross-organizational deduplication system for humanitarian organizations that uses biographical data to determine potential duplicates. Ideal Functionality. We formalize the deduplication functionality we aim to provide: A querying organization wishes to determine which of their new registrations are potential duplicates in the set of all registrations held by a responding organization. To this end, the querying organization inputs a single new registration (in online mode) or a batch of new registration records (in offline mode), and the responding organization inputs all registration records (new and old). Our functionality compares records and outputs which querier record’s similarity to a responder record exceeds a threshold. Non-goals. From discussions with NGOs and analysis of their requirements, we made the following design decisions. Not an automated decision-making system. We deliberately did not design an automated decision-making system. Our goal is only to identify potential duplicate registrations, that subsequently have to be manually checked in an adjudication process [27], [28], [50]. Do not rely on unique identifiers. Our system has been designed to function in a common setting where reliable unique identifiers (e.g., personal ID or phone numbers) are unavailable. When such identifiers are available [101], simpler solutions are possible.
2.4. Requirements We summarize functional, security, privacy, and deployment requirements for cross-organizational deduplication identified from humanitarian publications and discussions with humanitarian organizations. Functional Requirements. xDup must satisfy the following: RQ.F1: Identification of Duplicates. The system should identify which of the newly registered recipients of one field team are also registered with another field team. It should do so with high recall. RQ.F2: No IDs. The system should not rely on unique fixed identifiers for the recipients. RQ.F3: Fuzzy matching. The system should support fuzzy matching on quasi-identifers (e.g., name, DoB, gender). Privacy Requirements. To protect the privacy of vulnerable recipients, xDup must provide the following properties.
RQ.P1: Low False-Positive Rate. The system should have a low false-positive rate (FPR), i.e., ensure that very few of the new registrations are falsely flagged as duplicates. A low FPR reduces the privacy impact on non-duplicate recipients. Recall that, for each potential duplicate identified in step 1, the organization subsequently shares this data with other organizations in step 2. The fewer duplicates our system incorrectly identifies, the better we can protect privacy. A low FPR also reduces the workload on the deduplication committee. We thus aim for an FPR of 0.1 % to ensure that only a small fraction of the discussed potential duplicates turns out to be false. RQ.P2: No Leakage. During deduplication, the responding field team should learn no information about the queried records and the querying field team should learn nothing about non-matching responder records. The headquarters should learn no information about individual registrations. Deployment Requirements. We require our system to be suitable for real-world deployment. RQ.D1: Support Offline Operation. Field teams operate in challenging environments in which internet access may be unreliable. Thus, any system should support an offline mode where field teams submit a batch of queries and later retrieve responses, without requiring them to be online. RQ.D2: Support Online Operation. If field teams have network access during registration, the system should support online operation, performing deduplication of a single record within seconds; thus enabling the field team to take immediate action (such as requesting more information). RQ.D3: Efficient for Field Teams. The system should work with the limited compute and communication resources available to field teams. RQ.D4: Scalability. The system should be able to cope with realistic population sizes. A single humanitarian program typically serves less than 100k people [33], [96], [99], and we assume that submitted batches in offline mode contain up to around 2k new registrations. Current Deduplication Does not Satisfy these Requirements. The approaches used by humanitarian organizations right now (if any) for cross-organizational deduplication do not satisfy the requirements set out above. Methods based on direct data sharing or plaintext similarity matching fail to satisfy the privacy requirement RQ.P2 because they potentially reveal a lot of registration information about nonduplicates. To reduce leakage, some humanitarian actors instead apply cryptographic hash functions to all (or a carefully chosen subset) of the registration data and then share these hashes [29], [41], [50]. While this is better than directly sharing the data, these hashes are still vulnerable to membership inference attacks (where it is trivial to check whether a specific person appears) as well as brute-force reconstruction attacks. As a result, these approaches do not satisfy RQ.P2. Moreover, as a result of applying a hashfunction, small changes in the records can now result in duplicates not being found. Thus, these approaches cannot provide high recall (violating RQ.F1) or can do so only at the cost of many false positives (violating RQ.P1).
2.5. Threat Model Headquarters. Large NGOs like the UN or ICRC are protected by privileges and immunities [7]. While we assume that their headquarters are resistant to coercion, they may still be compromised [1], [49]. We model headquarters as honest-but-curious and assume the organizations’ headquarters do not collude with each other. Field Teams. We assume that field teams perform the recipient registration honestly since biographical deduplication relies on the trustworthiness of registration data. Yet – because field teams operate in challenging circumstances and are therefore vulnerable to compromise and coercion (e.g., by local actors) – we consider them malicious in the deduplication process to ensure that coercion of one field team does not reveal information about recipients registered with other field teams. Recipients. Similar to the NGOs’ current processes [27], we assume that there is a verification mechanism in place to ensure the validity of registration data, and thus most errors are accidental. To ensure validity, humanitarian organizations often consult appropriate sources – for example, elders in the communities that these organizations target.
2.6. Limitations Any deduplication system brings privacy risks through the ideal deduplication functionality. We acknowledge these risks and stress that they are inherent to all deduplication systems and must be mitigated using out-of-band measures. Malicious Registrants. Deduplication based on biographical data hinges on self-reported recipient data being trustworthy and, hence, organizations need a mechanism to enforce correctness. If registration data cannot be trusted, e.g., because recipients can lie without being detected, deduplication methods based on biographical data are inappropriate. In practice, organizations have found such validation mechanisms [27], [50] and use biographical data for deduplication. Additionally, malicious registrants could abuse the deduplication system to extract information about other individuals: They could try to register with another individual’s personal data to find out whether this individual is already registered with any organization. This attack can only be avoided if there are mechanisms in place to ensure registrants cannot lie during registration. Compromised Field Teams. Every query inherently reveals some information about the responder’s database. A compromised field team may, e.g., perform a dictionary attack to enumerate the databases of other organizations. Every deduplication mechanism is vulnerable to such attacks, and their impact can only be controlled through rate imitating.
2.7. Design Overview We address the requirements set out in the previous section: To maintain privacy (RQ.P2) we use a cryptographically-secure matching mechanism to compare individual records. However, existing matching protocols
HQ B
HQ A
As mentioned in §2.4, current deduplication mechanisms for NGOs rely on collision-resistant hash functions. Yet, this approach (i) leaks personal information about the recipients, and (ii) is not robust to slight perturbations in the attributes that can naturally occur during registration.
identify all pairs of records – with potentially varying sets of attributes in different databases – that correspond to the same individual [21]. Most PPRL approaches rely on a matching functionality that compares two records. To ensure robustness to small perturbations of attributes, early works use different similarity metrics built on top of Bloom filters [31], [32], [54], [64], [74], [81], [82], [91], [92]. Yet, revealing these Bloom Filters to other parties without additional privacy mechanisms is vulnerable to attacks [22], [62], [70], [94], [95]. A different research direction provides private implementations of matching using homomorphic encryption [51], [56], [63]; and generic SMC techniques [18], [65], [83], or PSI [34], [72], [104]. Yet, comparing all pairs of records of two datasets using these relatively expensive matching protocols is costly and impractical for our scenario: MainSEL’s SMC [83] would require about 10 days to perform the same task that our construction can do in hours (see §7.5). To reduce the number of potentially costly comparisons, several works use a blocking mechanism that identifies candidate pairs and then only apply matching to these candidate pairs [44], [55], [80]. Yet, this can lead to leakage about nonmatching records [15] and cannot always guarantee that all matching pairs are identified, leading to false negatives. A popular way to implement blocking is by deterministically assigning records to buckets and only comparing records assigned to the same bucket. Yet, the composition of these buckets can reveal information. This issue is typically addressed using differential privacy and variants thereof [44], [52] but without strong cryptographic privacy guarantees. Wei and Kerschbaum [97] present a blocking mechanism that provides cryptographic security. It uses bucketization with frequency smoothing [38] in combination with private bin join [60]. Still, their approach leaks some information via the number of performed comparisons. While offering good performance, their implementation currently does not perform any fuzzy matching (i.e, it only considers strict equality of 16-bit integers). Thus, it is unclear how this solution would perform in real-world record linkage use cases involving larger data sizes and fuzzy matching. Finally, blocking mechanisms typically compare two sets of records – which only applies to our offline operation mode. For online operations with only a single query, blocking mechanisms do not improve performance. In a different vein, Locality-Sensitive Hashing (LSH) can reduce PPRL to Private Set Intersection (PSI) [3], [43]. We evaluate this approach and observe that it does not provide the required accuracy in our setting – it provides only 86.5 % recall compared to our 99.4 % (see Appendix C.5). More works on PPRL exist, yet many do not provide strong security guarantees or are prohibitively expensive. We refer readers to surveys for details [37], [93].
3.1. Privacy-Preserving Record Linkage
3.2. Fuzzy Private Set Intersection
To solve the privacy issue, NGOs could rely on PrivacyPreserving Record Linkage (PPRL): In this setting, two (or more) parties hold databases of records and want to
Instead of PPRL techniques, NGOs could also rely on modern Fuzzy Private Set Intersection (FPSI) approaches. While PSI computes the intersection of two sets, FPSI
② Outsourced otFPSI ⓪ setup HQ A ④ update DB ① sharing
③
Field Team 1
HQ B ⓪ setup ④ update DB ③ shared result
Field Team 2
Field Team n
Figure 2. Illustration of xDup.
using generic Secure Multi-Party Computation (SMC) or Homomorphic Encryption (HE) are too costly to fulfill the scalability requirement (RQ.D4). This is especially the case for the online operation mode, where the responding party inherently needs to perform computation linear in the database size. Many existing mechanisms to reduce the number of comparisons typically assume that the querier holds a set of records instead of just one, and are not applicable in our online mode. To overcome these limitations, we first transform the structured registration records into fixed-length bit strings, such that similar records have a small Hamming distance. We then use our new otFPSI protocol, an FPSI protocol for Hamming space, to privately compare the embedded records. otFPSI utilizes a concretely efficient matching mechanism built on OT. To address the challenge of limited computational resources (RQ.D3) and online/offline requirements (RQ.D1 and RQ.D2), see Figure 2, we outsource the computation to two more powerful compute nodes operated by two organizations’ headquarters, each holding secret-shared databases of the embeddings of all field teams’ registration records 0 . When a field team wants to use xDup to check one or multiple new registrations, it locally computes their embedding and sends secret shares to both compute nodes 1 . The compute nodes then run an outsourced variant of otFPSI to compare the new registrations to all registrations in their databases 2 . Finally, they send the secret-shared result back to the querying field team 3 and add the new registrations to their databases 4 .
3. Related Work
computes which elements are close with regard to a distance metric d and a threshold τ . In our setting, the parties would individually transform their records to a metric space (e.g., Euclidean or Hamming space) such that matching records are close in that metric space. Then, the parties use a (compatible) FPSI protocol to find matches while preserving the privacy of non-matching records. Several works exist that transform records into Euclidean space [8], [66], [80]. However, these approaches result in high-dimensional embeddings – for our NGOs’ setting, we expect a dimensionality of more than 50 (see Appendix C.2). The embeddings into Euclidean space could be combined with an FPSI protocol for Euclidean space [35], [77], [89], [90]. Yet, these protocols come with significant drawbacks: They place potentially restrictive assumptions on the structure of the input data and many of these protocols do not scale well to high dimensions. For instance, the stateof-the-art work by Van Baarsen and Pu [90] proposes two protocols. √ The first√requires the parties’ data points to be at least 2τ l or 2τ ( l + 1) apart, but has a runtime linear in 2l l, where l is the data dimension and τ the distance threshold. We infer from their work that the cost of this protocol is prohibitively high for l ≥ 50. Their second protocol, which is linear in lτ , and thus has better asymptotics, relies on the even stronger assumption that each data point’s projections on each dimension are at least 2τ apart from all other points. We cannot rely on this assumption to hold for large datasets with existing embeddings. Similar limitations also apply to other FPSI protocols for Euclidean space [35], [77], [89]. Another line of FPSI protocols [6], [13], [16], [19], [35], [61], [88] operates in Hamming space. However, these FPSI protocols have significant drawbacks: Some approximate the Hamming distance and do not achieve the accuracy required in our setting [13], [16], [88]. For our embedding, we need a relatively high-dimensional Hamming space (l ≈ 512) and a high distance threshold (τ ≈ l/4) (see Appendix C.1). For these parameters, existing FPSI protocols have unfulfillable input assumptions [19], [35], or are inefficient since their runtime depends on the threshold or is super-linear in the dimension [6], [13], [16], [35], [88] (see §7.2). While using an embedding with an FPSI protocol seems a promising direction, existing works can not be easily combined.
4. xDup We now present the design overview of xDup. We present the high-level building design rationale, introduce our building blocks, and detail our system design.
4.1. Design Rationale One of the design challenges of xDup is to provide a query mechanism that allows one organization to perform a query when all other organizations may be offline (RQ.D1). This requirement and field teams’ limited resources (RQ.D3) preclude the direct use of interactive SMC protocols. While HE appears to be auspicious for this model – as it might allow outsourcing to a single untrusted server – it also
Parameters: Dimension l, distance metric d, threshold τ , set sizes nQ and nR 1) Receive Q = {q1 , . . . , qnQ } ⊆ {0, 1}l from Q and R = {r1 , . . . , rnR } ⊆ {0, 1}l from R. 2) Send {(i, j) | i ∈ [nQ ], j ∈ [nR ], d(qi , rj ) ≤ τ } to Q. Figure 3. FFPSI , Ideal functionality for FPSI between querier Q with input Q and responder R with input R. [n] = {1, ..., n}.
brings challenges. First, the key management is non-trivial: under which key are the ciphertexts encrypted, who performs the decryption, etc. Second, secret-key holders must be online for decryption. One potential solution would be to operate under the querying organization’s key. To guarantee privacy in this setting, the querying organization must not collude with the compute server. Yet, as the compute server will likely be operated by one of the organizations, this noncollusion assumption may be hard to warrant. A non-collusion assumption between two servers operated by two different organizations is a more natural fit for the humanitarian setting. These servers may be operated by the organizations’ headquarters, which typically have sufficient resources available, want to assist the aid distribution process, and, for some organizations, are protected (e.g., against coercion) by special privileges and immunities [7]. Thus, xDup relies on outsourcing the computation and communication of its interactive FPSI protocol to two noncolluding compute nodes operated by two headquarters. This design has another advantage: It remains secure if field teams act maliciously – all they can do is send queries to the compute nodes (which may still leak, see §2.6).
4.2. Building Blocks We rely on a novel approach that combines an embedding mechanism into Hamming space with an FPSI protocol. This approach enables us to provide high performance (using efficient FPSI protocols), while being agnostic to the properties of the records (using a suitable embedding). Embedding. Given a universe of records R, an embedding E : R → {0, 1}l maps records to fixed-length bit strings. An embedding should map two records r, r′ ∈ R that match (i.e., correspond to the same individual) to similar bit strings. This means that dH (E(r), E(r′ )) ≤ τ where dH denotes the Hamming distance and τ is a constant threshold. Fuzzy Private Set Intersection. Figure 3 formalizes FFPSI , the ideal functionality of FPSI for identifying which elements from Q and R are close w.r.t. a distance metric d and a threshold τ . To allow outsourcing computation to two untrusted compute nodes, xDup uses an FPSI protocol that can operate on secret-shared inputs and outputs. We formalize this functionality in Fig. 4. In secret-shared FPSI, two compute nodes S1 and S2 each hold one secret share of each of the input sets Q and R. Secret-shared FPSI first reconstructs these shares, compares all records, and finally outputs one share of the result to each party.
Parameters: Dimension l, distance metric d, threshold τ , set sizes nQ and nR 1) Receive Q = {q1 , . . . , qnQ }, R = {r1 , . . . , rnR } ⊆ {0, 1}l b = {qb1 , . . . , qd b from S1 and Q nQ }, R = {rb1 , . . . , rd nR } ⊆ {0, 1}l from S2 . 2) Compute qi = qi ⊕ qbi and rj = rj ⊕ rbj for i ∈ [nQ ], j ∈ [nR ]. c ←$ {0, 1}nQ ×nR and send M c to S2 . 3) Sample M ci,j ⊕ (d(qi , rj ) ≤ τ ) for i ∈ 4) Compute M as M i,j = M [nQ ], j ∈ [nR ] and send M to S1 . Figure 4. FssFPSI , Ideal secret-shared FPSI functionality between node S1 b R b. The output is secret-shared with input Q, R and node S2 with input Q, c. across M and M
Ti : One-Time Setup
Si : One-Time Setup
L1 , L2 ← [ ] for r ∈ Ri :
for j ∈ [nT ] : Receive Dj from Tj
s ←$ {0, 1}l L1 .append(s) L2 .append(s ⊕ E(r)) Send L1 to S1 and L2 to S2
Figure 5. One-time setup procedures with embedding E .
Ti : Query
Si : Process
Q1 , Q 2 ← [ ] for q ∈ Q :
Receive Qi from Tj D̸=j ← [ ] // Collect registrations for k ∈ [nT ] \ {j} : D̸=j .insert(Dk )
s ←$ {0, 1}l Q1 .append(s) Q2 .append(s ⊕ E(q)) Send Q1 to S1 and Q2 to S2
M (i) ← ssFPSIi (D̸=j , Qi ) L ← [Dk .length() | k ∈ [nT ]] L[j] ← 0 // maps records to orgs Dj .insert(Qi ) // save new data
Make M (i) , L available to Tj
Ti : Retrieve
Retrieve M (1) and L from S1 , and M (2) from S2 nQ , nR ← M (1) .size() for q ∈ [nQ ] : o ← 1; // organization counter for j ∈ [nB ] : if j > Σok=1 L[k] : o←o+1 (1)
(2)
if Mq,j ⊕ Mq,j = 1 : o−1 r = j − Σk=1 L[k]
output Duplicate query q with record r of To
4.3. System Description We now present xDup in more detail. We assume there are nT field teams T1 , . . . , TnT . To enable online queries, the compute nodes S1 , S2 hold a secret-shared database of all registrations that is continuously updated after each query. Parameter Selection. All field teams agree on the following parameters of the system: • Embedding: An embedding mechanism to transform records to Hamming space with dimension l. • Compute Nodes: Two non-colluding nodes S1 and S2 . This role can be taken by two headquarters (see §2.1). One-Time Setup. In the setup phase (Fig. 5) each field team Ti submits its pre-existing registration database (which is assumed to be without duplicates) to the compute nodes. To do so, Ti embeds all records in its registration database Ri into Hamming space, creates secret shares of the embeddings, and sends them to the compute nodes S1 and S2 . Deduplication. To query xDup with a set of new registrations Q (which contains only one element in the online case), field team Ti performs the following steps (see Fig. 6): 1) Local Deduplication: First, Ti locally deduplicates, that is, it identifies new registrations in Q that are already registered with Ti itself. This process happens locally and, hence, is done in plaintext and may happen each time a new registration is recorded. 2) Query: Ti embeds its query set Q, creates secret shares, and sends one each to S1 and S2 . 3) Process: S1 and S2 run a secret-shared FPSI protocol to compare Ti ’s new registrations Q to all stored registrations of the other field teams Tj̸=i . Both compute nodes append the secret shares of the new registrations to the existing registrations of the querying field team. 4) Retrieve: Ti retrieves the secret-shared results from S1 and S2 and reconstructs the result. For each query record,
Figure 6. Deduplication procedures.
it identifies whether there is a duplicate and, if so, with which other field team. Manual Verification. At fixed intervals, all field teams join the deduplication committee with additional information about the potential duplicates discovered in the previous step to perform the adjudication process (§2.2).
5. Embedding We are not aware of an existing embedding that matches the requirements imposed by our humanitarian use case. Hence, we use a new embedding strategy which, at its core, uses Locality-Sensitive Hashing (LSH): l LSH functions each convert the q -grams (i.e., all substrings of length q ) of the record into a single bit. The final embedding is the concatenation of these l bit digests. By properties of LSH, the more similar the input records are, the more individual bit digests match. To compare two embeddings, we use the Hamming distance and two records are deemed duplicates if the Hamming distance is below a threshold τ . We provide more details in Appendix C.1. To validate our embedding, we evaluate it using a synthetic dataset representative of humanitarian deduplication tasks (see Appendix C.3). The deduplication of a single record in a large database (131 072 records) leads to a falsenegative rate of 0.57 % at a false-positive rate of 0.098 % (RQ.P1) (with embedding size of l = 511 bits and a Hamming distance threshold of τ = 132). We consider these accuracy results to fulfill the xDup’s requirements (RQ.P1, RQ.F1) and choose l = 511 and τ = 132 as the operating parameters for xDup. For lower dimensions, we
can only achieve higher false-negative rates at the target false-positive rate, but still need τ ≈ l/4. The accuracy of our embedding is on par with existing plaintext matching algorithms (Appendix C.1). Nevertheless, xDup is agnostic to the concrete embedding used, and this construction may be easily replaced.
6. otFPSI Since existing FPSI protocols are not suitable for our purpose (§3.2), we introduce otFPSI, a Hamming FPSI protocol that is correct, assumption-free, threshold-independent, and quasi-linear in the dimension. At its core, our protocol utilizes the SHADE construction [11] construction to privately compute Hamming distances. We combine SHADE with an efficient threshold comparison step, extend it to support secret-sharing, and enhance it with a batching method for secret-shared FPSI. We evaluate the performance of otFPSI in §7.1 and show it outperforms all existing protocols.
6.1. Oblivious Transfer A key building block of otFPSI is Oblivious Transfer (OT). A 1-out-of-N OT is a two-party functionality between a responder R holding N messages m0 , . . . , mN −1 and a querier Q with a choice index c ∈ ZN . OT enables Q to learn mc while hiding the choice c from R and all other messages mi for i ∈ ZN \ {c} from Q. Different OT functionalities are classified by how much control the responder has over the messages. In chosen OT, messages are chosen by the responder, while in random OT, they are chosen at random by the protocol. Correlated OT chooses one message at random and derives the remaining messages using correlation functions. We specify the functionality of OT variants in Appendix A.
6.2. Protocol Description otFPSI computes a secure comparison between two bit strings (i.e., the embeddings): q held by the querier Q and r held by the responder R. The result bit b = (dH (q, r) ≤ τ ) is only known to Q. This comparison is applied to all pairs of records in the sets Q and R to achieve FPSI (Fig. 3). Our secure comparison protocol consists of two steps: First, it computes secret-shares of the Hamming distance dH (q, r) and, second, compares the distance to the threshold τ to determine the result bit. Both steps rely on OT. We detail in the following subsections how these steps are performed and how we can optimize them.
6.3. A Single Comparison For now, we only consider the distance computation and threshold comparison between two bit strings. Model. Assume the bit string q (resp. r) is held by Q (resp. R). Both q and r have l bits, let q[i] be the i-th bit of q . We set p = l + 1 (not necessarily prime). By [n], we denote the set {1, . . . , n}. We denote assignment modulo p as ←p .
Computing the Distance. To compute secret-shares of the Hamming distance, we use the SHADE [11] construction: Computation. For each bit i ∈ [l], R samples mi from Zp and computes both mi,0 = mi + r[i] mod p and mi,1 = mi + (1 ⊕ r[i]) mod p. We then run a 1-out-of-2 chosen OT (see §6.1): R inputs the messages mi,0 and mi,1 , and Q inputs q[i] as the choice bit, and receives di = mi,q[i] . Pl After looping over all l bits, Q computes D = i=1 di and Pl R computes M = i=1 mi . Correctness and Security. By construction, di = mi,q[i] = mi + (q[i] ⊕ r[i]) mod Pl p. With p > dH (q, r), it follows that D − M mod p = i=1 q[i] ⊕ r[i] = dH (q, r). SHADE is secure in the semi-honest setting assuming the underlying OT is secure in the semi-honest setting [10], [11]. Correlated OT. Bringer et al. [10] observe that correlated OT is sufficient for SHADE. In correlated OT, the sender gets a single random value sampled by the protocol and inputs a correlation function determining the second value. Here, the protocol can sample m1,0 , . . . , ml,0 and then R can compute mi = mi,0 −r[i] mod p and mi,1 = mi +(1⊕r[i]) mod p. Using correlated OT can reduce communication cost compared to chosen OT (see Appendix A) . Comparing to τ . To privately compare dH (q, r) = D − M mod p to the threshold τ , we combine SHADE with an additional 1-out-of-l OT: R computes the result bit of the comparison for all p possible values of D: vi = (i − M mod p ≤ τ ) for i ∈ Zp and Q gets the result vD by OT. Correctness and Security. By construction, Q learns b = vD = (D−M mod p ≤ τ ) = (dH (q, r) ≤ τ ). The security guarantees of the threshold comparison follow directly from those of OT: R learns no information and Q only learns the intended output bit.
6.4. Full otFPSI Construction With the comparison mechanism for bit strings in place, we now build the full otFPSI protocol to implement the FPSI functionality (Fig. 3). Consider Q (resp. R) holds the set of elements Q (resp. R). Batching. When computing the distances between one element q held by Q and all elements in R, Q’s input does not change (i.e., it is always q[i] for the i-th bit computation). Following SHADE [11], we batch these into one (correlated) OT. This strategy reduces the number of OTs from nR l to l. While it requires larger OT messages, this can be achieved inexpensively using pseudo-random functions (see Appendix A). This batching allows us to reduce computation cost. Full Construction. We present the full otFPSI protocol in Fig. 7. To compare two sets Q and R, it loops over each q ∈ Q, computes the distances to all r ∈ R using batching, and compares each computed distance to the threshold τ . We proof correctness and security of otFPSI in Appendix B. Complexity. We analyze the asymptotic complexity of otFPSI. The distance computation step performs nQ l 1-out-of-2 chosen OTs with a message length of nR log p. As p ∈ O(l), this results in a communication and computation complex-
Querier Q = {q1 , . . . , qnQ } ⊂ {0, 1}l 1 I ← ∅ 2 for i ∈ [nQ ]: #” 3 Di ← 0nR 4 for j ∈ [l]: 5 c ← qi [j] 6 7 8 9 10 11
# ” ← OTrecv(c) m i,j #” #” # ” Di ←p Di + m i,j for k ∈ [nR ]:
12 13
#” bi,k ← OTrecv(Di [k]) 15 if bi,k = 1: 16 I ← I ∪ {(i, k)} 17 return I 14
Responder R = {r1 , . . . , rnR } ⊂ {0, 1}l for i ∈ [nQ ]: #” Mi ← 0nR for j ∈ [l]: #” ←$ ZnR m p #” r ← (r1 [j], · · · , rnR [j])T # ”← m #” + r m p 0 #m” ← m #” + (1nR ⊕ #” r) p 1 # #” OTsend(m” 0 , m1 ) #” # ” #” Mi ←p Mi + m for k ∈ [nR ]: for m ∈ Zp : #” vm ← (m− Mi [k] mod p) ≤ τ OTsend(v0 , . . . , vp−1 )
Server S1 Q = {q1 , . . . , qnQ } ⊂ {0, 1}l R = {r1 , . . . , rnQ } ⊂ {0, 1}l n ×nR 1 D, P ← 0 Q 2 for i ∈ [nQ ], j ∈ [nR ]: 3 for k ∈ [l]: b ← qi [k] ⊕ rj [k] 4 5 6 7 8 9
mi,j,k ← OTRecv(b) Di,j ←p Di,j + mi,j,k
10 11 12 13 14 15
P i,j ← OTrecv(Mi,j ) return P
Server S2 l b = {qb1 , . . . , qd Q nQ } ⊂ {0, 1} l b = {rb1 , . . . , rd R nQ } ⊂ {0, 1} M, Pb ← 0nQ ×nR for i ∈ [nQ ], j ∈ [nR ] for k ∈ [l]: b b ← qbi [k] ⊕ rbj [k] m ←$ Zp m0 ←p m + b b m1 ←p m + (1 ⊕ b b) OTSend(m0 , m1 ) Mi,j ←p Mi,j + m Pbi,j ←$ {0, 1} for m ∈ Zp : vm ← (m − Mi,j mod p ≤ τ ) vm ← vm ⊕ Pbi,j OTSend(v0 , . . . , vp−1 )
return Pb
Figure 8. Full otFPSI-ss protocol.
Figure 7. Full otFPSI protocol. Lines 3-10 are the SHADE construction.
ity of O(nQ nR l log l). The threshold comparison step performs nQ nR 1-out-of-p chosen 1-bit OTs, resulting in a communication and computation complexity of O(nQ nR l). Assuming nQ , nR ∈ O(n), otFPSI is quadratic in n. This is asymptotically worse than existing protocols that have communication (and, for Fmap-FPSI [35], computation) only (quasi-)linear in n. However, these protocols only achieve this by relying on restrictive input assumptions [19], [35] or suboptimal complexities in the dimension [35] or threshold [6], [35]. In §7.2, we show that otFPSI is concretely more efficient than these protocols for most practical parameters.
6.5. Secret-Shared otFPSI As described in §4, xDup relies on a secret-shared FPSI protocol (Fig. 4). This allows Q and R to outsource the computation and communication cost of the FPSI protocol to two non-colluding compute nodes S1 and S2 . To do so, Q and R generate bitwise secret-shares of their input sets b and R = R⊕R b. Both parties then send one share Q = Q⊕Q to each of the two non-colluding nodes, which then run a secret-shared FPSI protocol. Q can retrieve the secret-shares of the result from the nodes and reconstruct the result. In this section, we describe otFPSI-ss and otFPSI-ssb, two secret-shared variants of otFPSI. Single Comparison. For a single comparison, operating on bitwise secret shares is straightforward: Assume S1 holds secret shares q , r and S2 holds qb, qb where q ⊕ qb = q and r⊕ rb = r. Observe that dH (q, r) = wH (q ⊕r) = wH (q ⊕r⊕ qb ⊕ rb) = dH (q ⊕ r, qb ⊕ rb) where wH denotes the Hamming weight. Thus, S1 and S2 can locally XOR their shares q ⊕ r and qb ⊕ rb, and invoke the private comparison protocol from otFPSI. To create secret-shared outputs, we modify the threshold comparison as follows: S2 samples a random bit Pb and uses it to mask the comparison results: vi = (i − M
mod p ≤ τ ) ⊕ Pb for i ∈ Zp . Server S1 retrieves P = vD through OT and outputs P , S2 outputs Pb. Correctness. By construction, we have D − M mod p = dH (q⊕r, qb⊕rb) = dH (q, r) and P = (D−M mod p ≤ τ )⊕ Pb = (dH (q, r) ≤ τ ) ⊕ Pb, hence P ⊕ Pb = (dH (q, r) ≤ τ ). otFPSI-ss. Our first secret-shared FPSI protocol, otFPSI-ss, applies the single comparison outlined above to all pairs of records across Q and R. Fig. 8 presents the full protocol. We prove correctness and security in Appendix B. Batching. We cannot apply the same batching strategy as in otFPSI to the secret-shared setting. In otFPSI, Q’s OT inputs are determined by q only and are the same when comparing one q to any r ∈ R. In otFPSI-ss, S1 ’s OT inputs are determined by q ⊕ r, which differs for different r ∈ R. otFPSI-ssb. Performing many OTs is expensive (although the choice of OT may allow a trade-off between communication and computation). Our second secret-shared FPSI protocol, otFPSI-ssb, utilizes a different batching approach to reduce the number of OTs from nQ nR l to (nQ + nR )l at the cost of additional communication. otFPSI-ssb can concretely reduce cost for nQ > 1 (see §7.3). Using 1-out-of-4 OT. The otFPSI-ssb protocol relies on 1-out-of-4 OT for the distance computation step: When comparing the k -th bit of the secret-shared bit strings q and r, both parties run a 1-out-of-4 OT into which S1 inputs the two bits q[k] and r[k] individually instead of their XOR. As before, S2 samples a random mask m ←$ Zp and computes four OT messages m0 , . . . , m3 . S1 chooses the message indexed by c = 2q[k] + r[k]. As for plaintext comparison (§6.3), we want that mc − m mod p = q[k] ⊕ r[k] = q[k] ⊕ r[k] ⊕ qb[k] ⊕ rb[k]. We can achieve this by setting the four OT messages for bb = qb[k] ⊕ rb[k] as m0 = m3 = m + bb mod p and m1 = m2 = m + (1 ⊕ bb) mod p. Correctness. If q[k] ⊕ r[k] = 0, we have mc − m mod p = bb = qb[k] ⊕ rb[k] = q[k] ⊕ r[k] ⊕ qb[k] ⊕ rb[k] = q[k] ⊕ r[k]. If
q[k] ⊕ r[k] = 1, then mc − m mod p = 1 ⊕ bb = 1 ⊕ qb[k] ⊕ rb[k] = q[k] ⊕ r[k] ⊕ qb[k] ⊕ rb[k] = q[k] ⊕ r[k]. Naor-Pinkas construction. The Naor-Pinkas construction [68] allows us to implement a random 1-out-of-4 OT running two independent random 1-out-of-2 OTs. In random OT, S2 does not choose the OT messages, but learns the randomly chosen messages ω0 , . . . , ω3 during the protocol. More precisely, for S1 ’s choice c = 2q[k]+r[k], both parties run one random 1-out-of-2 OT for each input bit q[k] and r[k]. In the first OT, S2 learns two random messages α0 , α1 , and S1 learns αq[k] . In the second OT, S2 learns β0 , β1 and S1 learns βr[k] . Using a family of pseudo-random functions Fk : {0, 1}∗ → Zp for k ∈ {0, 1}λ , S2 can compute the four random OT messages ω0 , . . . , ω3 as ωj = Fαj1 (j)+Fβj2 (j) mod p where j = 2j1 + j2 . By construction, Q can only compute ωc = Fαq[k] (j) + Fβr[k] (c). Correlated OT. As with the plaintext comparison, correlated OT (see Appendix A) can be used instead of chosen OT. Let m0 ∈ Zp be the random message chosen by correlated OT. Then, we set m = m0 − bb mod p and compute the remaining messages as m3 = m0 and m1 = m2 = m + (1 ⊕ bb) mod p. The Naor-Pinkas construction provides a random 1-outof-4 OT. To implement chosen OT, S2 can use the random messages to mask its actual messages and send them to S1 . Implementing correlated OT is cheaper and can be done by only sending three messages: Let ω1 , . . . , ω3 ∈ Zp be the random OT messages. S2 sets m0 = ω0 and computes m1 , m2 , m3 as above. Then, S2 masks the m1 , m2 , m3 as µi = mi − ωi mod p and sends µ1 , µ2 , µ3 to S1 , which can unmask mc = µc + ωc mod p where µ0 = 0. The Key Observation. With the Naor-Pinkas construction, we can compare two secret-shared bit strings by running individual and independent OTs for each secret share held by S1 . When dealing with two secret-shared sets Q and R instead of two strings, we observe that for all comparisons of a specific q ∈ Q to any r ∈ R, S1 ’s input in the first OT of the Naor-Pinkas construction for the k -th bit is always q[k]. Similarly, when comparing a specific r ∈ R to any q ∈ Q, Q’s input to the second OT for the k -th bit is always rb[k]. This key observation allows us to reduce the number of random 1-out-of-2 OTs we need: Instead of running one OT for each bit of every comparison (as otFPSI-ss), we only need one OT for each bit of every input share – which is an improvement for nQ , nR > 1. The Full Protocol. Figure 9 presents the full protocol. For every bit, we first run one (random) OT for every share held by S1 (lines 3-8), resulting in the random seeds Xi for i ∈ [nQ ] and Yj for j ∈ [nR ]. For each bit comparison z , S2 derives the random OT messages ωz,x (lines 12-14) and computes the mz,x as outlined above (lines 15-17). Afterwards, S2 masks the other three OT messages using the random Naor-Pinkas OT messages and sends these masked values to S1 (lines 18-20), who reconstructs d = mc (lines 13, 14, 21). After computing the distances for all pairs of bit strings, S1 and S2 run the same secret-shared threshold comparison protocol as in otFPSI-ss. We prove the correctness and security of otFPSI-ssb in Appendix B.
Server S1 Q = {q1 , . . . , qnQ } ⊂ {0, 1}l R = {r1 , . . . , rnQ } ⊂ {0, 1}l n ×nR 1 D, P ← 0 Q 2 for k ∈ [l]: 3 for i ∈ [nQ ]: 4 5 6
Xi,k ← OTRecv(qi [k])
for j ∈ [nR ]:
9 10 11
0 , X1 ) OTSend(Xi,k i,k
for j ∈ [nR ]: 0 , Y 1 ← {0, 1}λ Yj,k j,k
7 8
Server S2 l b = {qb1 , . . . , qd Q nQ } ⊂ {0, 1} l b = {rb1 , . . . , rd R nQ } ⊂ {0, 1} n ×n M, Pb ← 0 Q R for k ∈ [l]: for i ∈ [nQ ]: 0 , X 1 ← {0, 1}λ Xi,k i,k
Yj,k ← OTRecv(rj [k])
for i ∈ [nQ ], j ∈ [nR ]: z ← (i, j, k) cz ← 2qi [k] + rj [k]
12 13
fz ←p FXi,k (z, cz )
14
fz ←p fz + FYj,k (z, cz )
15 16 17 18 19
µz,1 , µz,2 , µz,3 ← Recv() dz ←p fz + µz,cz 22 Di,j ←p Di,j + dz 23 for i ∈ [nQ ], j ∈ [nR ]: 20
0 ,Y 1 ) OTSend(Yj,k j,k
for i ∈ [nQ ], j ∈ [nR ]: z ← (i, j, k) b bz ← qbi [k] ⊕ rbj [k] for x = (x1 , x0 ) ∈ {0, . . . , 3}: ωz,x ←p FX x1 (z, x) i,k
ωz,x ←p ωz,x + FY x0 (z, x) j,k
mz,0 , mz,3 ←p ωz,0 mz ←p ωz,0 − b bz mz,1 , mz,2 ←p mz + (1 ⊕ b bz ) for x ∈ {1, . . . , 3}: µz,x ←p mz,x − ωzx Send(µz,1 , µz,2 , µz,3 )
21
24
for m ∈ Zp : vm ← (m − Mi,j mod p ≤ τ ) vm ← vm ⊕ Pbi,j
25 26 27 28 29
Mi,j ←p Mi,j + mz for i ∈ [nQ ], j ∈ [nR ]: Pbi,j ←$ {0, 1}
P i,j ← OTRecv(Mi,j ) return P
OTSend(v0 , . . . , vp−1 )
return Pb
Figure 9. Full otFPSI-ssb protocol.
7. Evaluation Implementation. To demonstrate the performance of xDup, we implement the core FPSI construction in C++ and provide extensive benchmarks. We publish this implementation as part of our artifact [75]. For 1-out-of-2 OT, we use SilentOT [9] provided by the libOTe library [78] (in Appendix D.1, we also provide evaluations with SoftSpokenOT [79]). We implement the 1-out-of-l OT required for the distance comparison from 1-out-of-2 OT using the Naor-Pinkas construction [68]. This approach proved more efficient than 1-out-of-N OT [58] as l is relatively small, and we only need 1-bit messages. We implement the PRF using AES-CTR. Environment. Prior FPSI works often benchmark their protocols in high-resource environments [16], [35], [88]. To showcase the practical performance of otFPSI, we deliberately choose a relatively low-resource environment: All our experiments run on a single Google Cloud Platform C4D VM with 4 cores of an AMD EPYC Turin CPU and 30 GB of RAM. Both parties run the computation single-threaded. While our approach is computation-efficient, it has a
TABLE 1. RUN TIME AND COMMUNICATION OF OT FPSI USING S ILENT OT FOR QUERIER SET SIZE nQ , RESPONDER SET SIZE nR , AND DIMENSION l ( THRESHOLD τ = ⌊l/16⌋). l = 127
l = 511
l = 8191
nQ
nR
Gigabit
Slow
Comm
Gigabit
Slow
Comm
Gigabit
Slow
Comm
64 256 1024 4096
64 256 1024 4096
0.031 s 0.278 s 4.41 s 70.1 s
0.862 s 1.34 s 7.39 s 103 s
0.622 MiB 8.26 MiB 130 MiB 2.03 GiB
0.080 s 1.05 s 16.5 s 267 s
1.01 s 2.67 s 29.6 s 462 s
2.67 MiB 40.7 MiB 649 MiB 10.1 GiB
1.24 s 24.7 s 418 s 6806 s
4.14 s 49.1 s 895 s 15 000 s
68.2 MiB 1.06 GiB 17.0 GiB 272 GiB
1 1 1 1
16 384 131 072 524 288 1 048 576
0.078 s 0.536 s 2.12 s 4.21 s
1.02 s 1.70 s 4.12 s 7.43 s
2.13 MiB 16.3 MiB 65.0 MiB 130 MiB
0.261 s 1.98 s 7.81 s 15.6 s
1.42 s 4.71 s 15.2 s 29.8 s
10.3 MiB 81.3 MiB 325 MiB 649 MiB
4.60 s 36.5 s 146 s 293 s
13.7 s 103 s 367 s 726 s
272 MiB 2.13 GiB 8.50 GiB 17.0 GiB
TABLE 2. O NLINE AND TOTAL COMPUTATION TIME OF FLPSI [88] ( EXCLUDING COMMUNICATION , SUB - SAMPLING PARAMETERS t = 2, T = 64) AND TOTAL RUN TIME OF OT FPSI (nQ = 1, τ = 25) OVER GIGABIT AND SLOW NETWORK WITH S ILENT OT ( l = 256 ). otFPSI
200
nR
Online
Total
Comm
Gigabit
Slow
Comm
100
104 105 106
0.523 s 4.45 s 44.0 s
1.46 s 8.53 s 81.5 s
12.1 MiB 20.4 MiB 40.8 MiB
0.112 s 0.825 s 8.72 s
1.06 s 2.46 s 16.0 s
3.22 MiB 31.2 MiB 311 MiB
0
comparatively high communication cost. To provide a meaningful evaluation, we simulate two network connections: a high-quality LAN with 1 Gbit/s and 0.5 ms latency, and a slower connection of 250 Mbit/s with 20 ms latency. For a fair comparison with prior work, we match their respective network conditions. As we observed little variance in preliminary runs, we report numbers from single runs.
213
0
Approx-PSI
Table 1 shows the runtime and communication cost of
To validate the performance of otFPSI, we compare it to prior FPSI protocols. Except for Fmap-FPSI [35], the code of existing FPSI protocols was not public at the time of writing. Hence, we can only compare to the numbers the authors report in the respective paper. For a fair comparison, we match protocol parameters and network setting. While we cannot replicate the original hardware, we use a relatively low-resource environment compared to the environments of prior work (Appendix, Table 12).
211 Dimension l
21
23 Threshold τ
25
TABLE 3. RUN TIME AND COMMUNICATION OF A PPROX -PSI [19] ( GAP t = log l ) AND OT FPSI WITH S ILENT OT BY SET SIZE n = nQ = nR (l = 128, τ = 4, GIGABIT NETWORK ).
otFPSI with SilentOT for a symmetric setting where both
7.2. Comparison to Existing FPSI Protocols
29
1000
Figure 10. Runtime otFPSI with SilentOT, DA-PSI, and Approx-PSI (nQ = nR = 100, 320 Mbit/s, 20 ms latency).
7.1. Performance of otFPSI
parties hold a set of the same size, and an asymmetric setting where the querier only holds one record. We add a large dimension for comparison, yet our xDup does not need l = 8191. Our results confirm that run time and communication of otFPSI are linear in the number of comparisons nQ nR . We confirm that the network setting influences the run time of otFPSI, as it is relatively communication-heavy.
Time [s]
Time [s]
FLPSI
otFPSI DA-PSI Approx-PSI t=8 Approx-PSI t=16
2000
300
otFPSI
n
Run time
Comm
Run time
Comm
256 1024 4096
38.7 s 148 s 570 s
466 MiB 1.74 GiB 6.71 GiB
0.310 s 4.60 s 72.8 s
9.22 MiB 145 MiB 2.27 GiB
TABLE 4. RUN TIME OF F MAP -FPSI [35] AND OT FPSI WITH S ILENT OT BY ( A ) THRESHOLD τ ( l = 512 , nQ = nR = 512 ) AND ( B ) DIMENSION l (τ = l/16, nQ = nR = 128). 10 Gibit/s, 0.02 ms LATENCY. Fmap-FPSI Total
otFPSI
τ /l
Online
Comm
Total
Comm
τ
1 2 4 8 16 ≥ 32
1.19 s 316 s 293 MiB 1.91 s 476 s 439 MiB 3.24 s 795 s 733 MiB 28.0 s 1460 s 1.29 GiB 64.8 s 2970 s 2.73 GiB Unsupported parameters.
4.58 s 4.58 s 4.59 s 4.58 s 4.59 s 4.58 s
187 MiB 187 MiB 187 MiB 187 MiB 187 MiB 187 MiB
l
64 128 256 512 1024
0.942 s 30.4 s 30.3 MiB 3.48 s 115 s 116 MiB 12.9 s 447 s 455 MiB 48.6 s 1760 s 1800 MiB Ran out of memory.
0.067 s 0.093 s 0.175 s 0.308 s 0.588 s
1.16 MiB 2.40 MiB 5.23 MiB 11.8 MiB 27.8 MiB
We evaluate and compare at different dimensions and thresholds. Yet, for our humanitarian use case, we aim for a dimension l ≈ 512 and a threshold of τ ≈ l/4 (Section 5). FLPSI [88]. We compare the run time of otFPSI (including communication) to the computation time of FLPSI (excluding communication) and present the results in Table 2. We observe that otFPSI has consistently better run times, even when run over slow networks: For a database size of 1 000 000, otFPSI achieves a reduction of 9.3 × compared to total computation and 5.0 × compared to online computation. Performance is not the only advantage of otFPSI: It provides exact results, while FLPSI relies on sub-sampling to approximate the Hamming distance which is fundamentally unable to provide sufficient accuracy (see Appendix D.2.1). Bui and Cong [13] build an FPSI protocol on the same sub-sampling approach, suffering from the same limitations. Still, their protocol is significantly slower than otFPSI. DA-PSI [16]. The Distance-Aware PSI protocol provides a matching protocol with dimension-independent communication cost (but heavily dependent on the threshold [16, Fig 12]). To fairly compare to their benchmarks, we evaluate otFPSI with a 320 Mbit/s connection and a latency of 10 ms. Fig. 10 shows that otFPSI is generally faster than DAPSI. Even for l = 8192, otFPSI is 41.7 × faster. Additionally, while otFPSI is not affected by the Hamming distance threshold τ , DA-PSI becomes highly impractical for large τ : e.g., otFPSI outperforms DA-PSI by a factor 358 × for τ = 32. Even for small thresholds, their protocol is not efficient enough: We estimate that an offline query at our target set sizes would take over 17 days even for τ = 4 – and DA-FPSI would miss over 90 % of duplicates when used for deduplication (Appendix, Table 7). Finally, DA-FPSI only approximates the distance causing a false-positive rate of 5 %, violating RQ.P1. Approx-PSI [19]. The Approx-PSI protocol has a communication and computation complexity near-linear in the set sizes. It assumes that all input data x, y ∈ Q∪R either match (i.e., wH (x, y) ≤ τ ) or are far apart: dH (x, y) ≥ tτ for some gap t > 3 (with t ∈ O(log l) for near-linear complexity). This assumption can be overly restrictive for large thresholds: For our intended parameters of τ ≈ l/4, there is no bit-string set of size three that fulfills this assumption, even for t = 3. This assumption is a severe limitation, making Approx-PSI inapplicable to our scenario. For the parameters used by the authors (l = 128 and τ = 4), Approx-PSI would miss around 90 % of duplicates (Appendix, Table 7). Still, otFPSI consistently outperforms Approx-PSI (Fig. 10). For gap t = 8 and l = 8192, otFPSI is faster by a factor of 56.4 ×. Table 3 compares to Approx-PSI for larger sets at their parameterization point: dimension l = 128, low threshold τ = 4, and large gap t = log l. We compare results in our gigabit setting to emulate their LAN. Even at these parameters, advantageous to Approx-PSI, otFPSI still outperforms Approx-PSI by 7.8 × at a set size of 4096. Fmap-FPSI [35]. Fmap-FPSI features both communication and computation linear in the input set sizes by using a new Fuzzy Mapping (Fmap) primitive (which maps elements to a set of IDs such that matching elements will have at least one
TABLE 5. RUN TIME AND COMMUNICATION OF PE-FPSI [6] AND OT FPSI WITH S ILENT OT BY SET SIZE n = nQ = nR ( l = 512 , UNLIMITED NETWORK ) PE-FPSI (τ = 2)
PE-FPSI (τ = 16)
otFPSI
n
Time
Comm
Time
Comm
Time
Comm
32 64 128 256
3.7 s 14.0 s 54.3 s 214 s
35.4 MiB 69.3 MiB 173 MiB 273 MiB
28.8 s 110 s 432 s 1710 s
259 MiB 517 MiB 1.01 GiB 2.01 GiB
0.0293 s 0.0841 s 0.291 s 1.12 s
0.846 MiB 3.06 MiB 11.8 MiB 46.9 MiB
ID in common). Their Fmap relies on a stringent assumption on the input data which limits the threshold τ relative to the dimension l. We experimentally evaluate Fmap-FPSI by running the authors’ code in our environment and find that Fmap-FPSI does not scale to higher thresholds (Table 4) – their implementation does not support our target parameters of l ≈ 512 and τ ≈ 128. Table 4 shows that Fmap-FPSI does not scale to large dimensions at τ = l/16, whereas we are aiming for τ = l/4. Even for l = 512 and τ = 32, which Fmap-FPSI only supports for very small sets, the protocol would miss over 73 % of duplicates when used for deduplication (Appendix, Table 7). Lastly, Fmap-FPSI relies on an expensive offline phase, making otFPSI much more competitive even for low thresholds (Table 4). These observations render Fmap-FPSI less suited for our humanitarian use case (see Appendix D.2.2 for more details). PE-FPSI [6]. The PE-FPSI protocol has linear communication complexity and no input assumptions; it uses predicate encryption. While its communication is asymptotically optimal in the set sizes, its computation is threshold-dependent and concretely inefficient: The largest set sizes evaluated are nQ = nR = 256. Compared to their benchmarks (192 vCPUs, 384 GiB RAM, no latency), and on our more constrained hardware, otFPSI is still faster than PE-FPSI (see Table 5): otFPSI is 1530 × faster for set size 256 and τ = 16, while reducing communication by 44.0 ×. Finally, using PE-FPSI for deduplication at the authors’ parameters (l = 512, τ = 16) would miss over 90 % of duplicates (Appendix, Table 7).
7.3. Performance of otFPSI-ss and otFPSI-ssb Table 6 shows the run time and communication cost of our secret-shared FPSI protocols, otFPSI-ss and otFPSI-ssb. Compared to plaintext otFPSI, otFPSI-ss increases runtime around 5 × (on fast networks) and communication by only about 10 %. Most of the additional run time is due to computation of the additional OTs which could be parallelized. otFPSI-ssb reduces the number of OTs at the cost of additional communication. Over gigabit networking and for nQ > 1, otFPSI-ssb is about 50 % faster than otFPSIss while increasing communication by around 2.5 ×. The benefit of otFPSI-ssb is more visible when instantiated with a more communication-heavy OT like SoftSpokenOT (Appendix, Table 10). Here, otFPSI-ssb reduces communication by 61 % and run time on slow networks by 53 %.
TABLE 6. RUN TIME AND COMMUNICATION OF PLAINTEXT OT FPSI AND SECRET- SHARED OT FPSI- SS AND OT FPSI- SSB WITH S ILENT OT FOR QUERIER SET SIZE nQ AND RESPONDER SET SIZE nR ( DIMENSION l = 511 , THRESHOLD τ = ⌊l/16⌋ = 31 ). otFPSI
otFPSI-ss
otFPSI-ssb
nQ
nR
Gigabit
Slow
Comm
Gigabit
Slow
Comm
Gigabit
Slow
Comm
64 256 1024 4096
64 256 1024 4096
0.080 s 1.05 s 16.5 s 267 s
1.01 s 2.67 s 29.6 s 462 s
2.67 MiB 40.7 MiB 649 MiB 10.1 GiB
0.356 s 5.39 s 84.2 s 1380 s
1.37 s 7.33 s 101 s 1660 s
2.94 MiB 44.8 MiB 714 MiB 11.2 GiB
0.201 s 2.65 s 41.9 s 674 s
1.24 s 5.08 s 86.8 s 1460 s
7.25 MiB 114 MiB 1.78 GiB 28.4 GiB
1 1 1
16 384 131 072 524 288
0.261 s 1.98 s 7.81 s
1.42 s 4.71 s 15.2 s
10.3 MiB 81.3 MiB 325 MiB
1.37 s 10.6 s 42.1 s
2.61 s 13.3 s 50.2 s
11.3 MiB 89.3 MiB 357 MiB
7.4. End-to-End Evaluation of xDup We evaluate the communication and computation cost of
xDup to show that it is practical and fulfills the requirements
outlined in §2.4. Fulfilling RQ.D4, we assume there are 131 072 existing registrations and 2048 new registrations. We assume l = 511 and τ = 132 (see §5). Setup. Recall that during the setup phase, all field teams embed their existing records and send their secret shares to the two compute nodes. Computing the embedding is done locally and is relatively cheap: For 131 072 records, embedding can be done in 388 s (see Appendix C.1) and can be easily parallelized. Using pseudo-random secret sharing with a 256-bit seed, a field team that submits 131 072 registrations has a total communication cost of 7.98 MiB. Offline Operation. The field team embeds the 2048 new records which takes 6.07 s. Sending secret-shared embeddings requires sending a total of 128 KiB to the compute nodes. The nodes run a secret-shared FPSI protocol to compare the 2048 new registrations to the 131 072 existing registrations of other organizations. Using otFPSI-ss with SilentOT, we estimate this takes a total of 359 min over gigabit networking, requiring a communication of 179 GiB. otFPSI-ssb can reduce the run time to 179 min with 456 GiB communication. On average, even otFPSI-ssb utilizes only about a third of the available bandwidth, and hence both protocols could further benefit from parallelized computation. Finally, the querier can retrieve the secret shares of the result (256 MiB) and recombine them. The offline operation mode (RQ.D1) of xDup only requires very limited communication and computation by the querying organization (RQ.D3), while no interaction is required by any other organization (RQ.D1). While the querier may need to wait multiple hours between submitting the new registrations and retrieving the results, there are typically no strict run time requirements for offline operation as long as the process can still happen, e.g., overnight. Online Operation. Embedding a single record takes 2.96 ms and its secret shares have a size of 96 B. The compute nodes can perform a query with otFPSI-ss and SilentOT in 10.6 s with 127 MB of communication. Using otFPSI-ss with SoftSpokenOT can reduce the run time of a query to 6.73 s at the cost of increased communication (see Appendix, Table 10). The querying organization can then retrieve
Batching not applicable for nQ = 1
the result shares which are 128 kB. xDup’s online mode also requires very little resources from the querying field team (fulfilling RQ.D3). It returns a result within seconds (RQ.D1), yet we acknowledge that a delay of 6.73 s to 10.6 s might slow down registration processes. We expect that this is still practical, since deduplication can be interleaved with other steps of the registration process.
7.5. Comparison to Related Work MainSEL [83]. Our embedding-based approach provides comparable accuracy to Stammler et al.’s SMC implementation [83] of the EpiLink matching algorithm for PPRL (see Appendix C.1). MainSEL is prohibitively expensive for deduplication. Even if with a parallelized implementation and using fewer fields (as the authors), we estimate that MainSEL would require over 10 days of computation and 154 TiB of communication to deduplicate a batch in offline mode. xDup with otFPSI-ssb can do this in only 179 min, reducing total cost by a factor of 84.1 × and communication by 347 ×. We further estimate that an online query with MainSEL would take a total of 440 s (78.6 s online computation). In contrast, otFPSI only takes 10.6 s in total. Funshade [47]. The Funshade protocol allows threshold distance comparisons of vectors using Π-secret sharing and Function Secret Sharing (FSS). As such, it may seem to be more naturally suited for two non-colluding compute nodes. However, the authors only evaluate their protocol with a trusted third party (TTP) to generate Π-shares and FSS keys. Even with a TTP, we estimate that Funshade’s setup phase for an online query would around 30 s over our slow network – and even more when replacing the TTP with SMC. In contrast, otFPSI-ssb only needs 13.3 s total. Lastly, since Π-shares embed Beaver triplets, in Funshade, they are re-created by the data holders for each comparison which does not work in our system model where data holders may be offline (violating RQ.D1) and putting load on the field teams (violating RQ.D3). Overall, Funshade is more expensive than otFPSI-ss and otFPSI-ssb, and does not work in our system model. We provide a more detailed analysis in the full version.
8. Conclusion In this work, we proposed xDup, a new privacy-preserving deduplication system for the humanitarian sector. We build on otFPSI, a new FPSI protocol that outperforms all existing FPSI protocol without restrictive input assumptions. Acknowledgements. Tim Rausch carried out this work as a member of the Saarbrücken Graduate School of Computer Science.
[3]
A. Adir, E. Aharoni, N. Drucker, E. Kushnir, R. Masalha, M. Mirkin, and O. Soceanu, “Privacy-Preserving Record Linkage Using Local Sensitive Hash and Private Set Intersection,” in ACNS, 2022.
[4]
A. Al-Lawati, D. Lee, and P. D. McDaniel, “Blocking-aware private record linkage,” in IQIS, 2005.
[5]
Amazon Web Services, Inc, “Amazon EC2 instance types,” Accessed 2025-09-24, 2025, https://aws.amazon.com/ec2/instance-types/.
[6]
E. Blass and G. Noubir, “Assumption-Free Fuzzy PSI via Predicate Encryption,” IACR Cryptol. ePrint Arch., 2025.
[7]
S. L. Blond, A. Cuevas, J. R. Troncoso-Pastoriza, P. Jovanovic, B. Ford, and J. Hubaux, “On Enforcing the Digital Immunity of a Large Humanitarian Organization,” in IEEE SP, 2018.
[8]
L. Bonomi, L. Xiong, R. Chen, and B. C. M. Fung, “Frequent grams based embedding for privacy preserving record linkage,” in ACM CIKM, 2012.
[9]
E. Boyle, G. Couteau, N. Gilboa, Y. Ishai, L. Kohl, P. Rindal, and P. Scholl, “Efficient Two-Round OT Extension and Silent NonInteractive Secure Computation,” in ACM CCS, 2019.
[10]
J. Bringer, H. Chabanne, M. Favre, A. Patey, T. Schneider, and M. Zohner, “GSHADE: faster privacy-preserving distance computation and biometric identification,” in ACM IH&MMSec, 2014.
[11]
J. Bringer, H. Chabanne, and A. Patey, “SHADE: Secure HAmming DistancE Computation from Oblivious Transfer,” in Financial Cryptography, 2013.
[12]
A. Z. Broder, M. Charikar, A. M. Frieze, and M. Mitzenmacher, “Min-Wise Independent Permutations,” J. Comput. Syst. Sci., 2000.
[13]
D. Bui and K. Cong, “Efficient Fuzzy Labeled PSI from Vector Ring-OLE,” IACR Cryptol. ePrint Arch., 2025.
[14]
CALP Network, “Registration, Targeting and Deduplication: Emergency Response inside Ukraine,” Accessed 2025-09-24, 2022, https://www.calpnetwork.org/wp-content/uploads/2022/09/ Registration-Targeting-and-Deduplication-Emergency-Responseinside-Ukraine-Thematic-paper-1.pdf.
[15]
J. Cao, F. Rao, E. Bertino, and M. Kantarcioglu, “A hybrid private record linkage scheme: Separating differentially private synopses from matching records,” in ICDE, 2015.
[16]
A. Chakraborti, G. Fanti, and M. K. Reiter, “Distance-Aware Private Set Intersection,” in USENIX Security, 2023.
[17]
M. Charikar, “Similarity estimation techniques from rounding algorithms,” in ACM STOC, 2002.
[18]
F. Chen, X. Jiang, S. Wang, L. M. Schilling, D. Meeker, T. Ong, M. E. Matheny, J. N. Doctor, L. Ohno-Machado, and J. Vaidya, “Perfectly secure and efficient two-party electronic-health-record linkage,” IEEE internet computing, 2018.
[19]
W. Chongchitmate, S. Lu, and R. Ostrovsky, “Approximate PSI with Near-Linear Communication,” IACR Cryptol. ePrint Arch., 2024.
[20]
T. Chou and C. Orlandi, “The Simplest Protocol for Oblivious Transfer,” in Latincrypt, 2015.
[21]
P. Christen, Data Matching - Concepts and Techniques for Record Linkage, Entity Resolution, and Duplicate Detection, ser. DataCentric Systems and Applications, 2012.
[22]
P. Christen, R. Schnell, D. Vatsalan, and T. Ranbaduge, “Efficient Cryptanalysis of Bloom Filters for Privacy-Preserving Record Linkage,” in PAKDD, 2017.
[23]
R. Ciesielski and M. Zierer, “How biometric devices are putting afghans in danger,” Accessed 2025-09-24, 2022, https://interaktiv. br.de/biometrie-afghanistan/en/index.html.
[24]
P. Contiero, A. Tittarelli, G. Tagliabue, A. Maghini, S. Fabiano, P. Crosignani, and R. Tessandori, “The EpiLink Record Linkage Software,” Methods of Information in Medicine, 2005.
Ethics Considerations During the course of our research, no harm was caused. We did not incorporate human subjects into our research, nor did we gather any data about people. We deliberately worked with synthetic evaluation dataset. We design a privacy-friendly deduplication system that guarantees strong privacy protection. Hence, it can be used in situations where non-private deduplication systems cannot and can offer assistance to more recipients. We have carefully considered the impact of incorrectly being singled out as a duplicate, and have minimized the risk of this happening in the first place, and clearly positioned our system within a bigger system with additional checks and balances. Yet, deduplication systems are not fully without a potential for harm, regardless of whether they are private or not. The first harm is to those correctly identified as duplicates which may be outweighed by the fact that more people can receive aid. Secondly, malicious recipients could extract information if registration data is not verified (§2.6). Lastly, deduplication systems can be used for other means such as migration enforcement [76]. However, non-private deduplication systems already exists and are in use. These can already be misused, and our system does not increase the potential for harm with respect to existing systems. We recognize that our construction could enable privacywashing – an inherent risk that can only thwarted by strong ethics considerations in its application.
LLM Usage Considerations An LLM-based tool (Grammarly) was used for editorial purposes in this manuscript, and all outputs were manually inspected and approved by the authors to ensure accuracy and originality.
References [1]
[2]
“Hacking attack on red cross exposes data of 515,000 vulnerable people,” Accessed 2025-09-24, 2022, https: //www.theguardian.com/world/2022/jan/20/hacking-attack-onred-cross-exposes-data-of-515000-vulnerable-people. “Ukraine cash working group task team 3: Deduplication and registration potential solutions for deduplication april 2022,” Accessed 2025-09-24, 2022, https://reliefweb.int/report/ukraine/ukrainecash-working-group-task-team-3-deduplication-and-registrationpotential-solutions-deduplication-april-2022.
[25]
P. Currion, “Eyes wide shut: The challenge of humanitarian biometrics,” Accessed 2025-09-24, 2015, https://www.thenewhumanitarian.org/opinion/2015/08/26/eyeswide-shut-challenge-humanitarian-biometrics.
[26]
DIGID Consortium, “The necessary interoperability of systems between organisations,” Accessed 2025-09-24, 2023, https://interoperability.ifrc.org/2023/05/23/the-necessaryinteroperability-of-systems-between-organisations/.
[27]
——, “Humanitarian data models for deduplication in cash coordination - internal briefing note,” Accessed 2025-09-24, 2024, https://interoperability.ifrc.org/wp-content/uploads/2024/10/ Deduplication briefing-note.pdf.
[28]
[29]
[30]
——, “Standardising humanitarian deduplication and adjudication processes in cash coordination,” Accessed 2025-0924, 2024, https://interoperability.ifrc.org/wp-content/uploads/2024/ 10/CCT-briefing 19092024.pdf. L. Douglas, “Deduplicating humanitarian aid in nigeria – pilot report,” Accessed 2025-09-24, 2023, https://www.frontiertechhub. org/s/DeDuplicatePilotReport-v2.pdf. L. Douglas and T. White, “De-duplicating aid to enhance the impact of humanitarian assistance,” Accessed 2025-09-24, 2023, https: //www.frontiertechhub.org/pilot-portfolio/deduplicatingaid-nigeria.
[31]
E. Durham, Y. Xue, M. Kantarcioglu, and B. Malin, “Private medical record linkage with approximate matching,” in AMIA Annual Symposium Proceedings, 2010.
[32]
E. A. Durham, M. Kantarcioglu, Y. Xue, C. Tóth, M. Kuzu, and B. A. Malin, “Composite Bloom Filters for Secure Record Linkage,” IEEE Trans. Knowl. Data Eng., 2014.
[33]
K. Edalatnejad, W. Lueks, J. Sukaitis, V. G. Narbel, M. Marelli, and C. Troncoso, “Janus: Safe Biometric Deduplication for Humanitarian Aid Distribution,” in IEEE SP, 2024.
[44]
X. He, A. Machanavajjhala, C. J. Flynn, and D. Srivastava, “Composing Differential Privacy and Secure Computation: A Case Study on Scaling Private Record Linkage,” in ACM SIGSAC, 2017.
[45]
K. Holloway, R. A. Masri, and A. A. Yahia, “Digital identity, biometrics and inclusion in humanitarian responses to refugee crises,” Accessed 2025-09-24, 2021, https://www.calpnetwork.org/wp-content/ uploads/2021/10/Digital IP Biometrics case study web.pdf.
[46]
Human Rights Watch, “UN Shared Rohingya Data Without Informed Consent,” Accessed 2025-09-24, 2021, https://www.hrw.org/news/ 2021/06/15/un-shared-rohingya-data-without-informed-consent.
[47]
A. Ibarrondo, H. Chabanne, and M. Önen, “Funshade: Function Secret Sharing for Two-Party Secure Thresholded Distance Evaluation,” Proc. Priv. Enhancing Technol., 2023.
[48]
ICRC, “Policy on the processing of biometric data by the ICRC,” Accessed 2025-09-24, 2019, https://www.icrc.org/sites/default/ files/document/file list/icrc biometrics policy adopted 29 august 2019 .pdf.
[49]
——, “Cyber attack on ICRC: What we know,” Accessed 2025-0804, 2022, https://www.icrc.org/en/document/cyber-attack-icrc-whatwe-know.
[50]
IFRC, “Deduplication of people, families or households,” Accessed 2025-09-24, 2023, https://interoperability.ifrc. org/wp-content/uploads/2023/11/DIGIDInteroperabilityDeduplicationofpeoplefamiliesorhouseholds.pdf.
[51]
A. Inan, M. Kantarcioglu, E. Bertino, and M. Scannapieco, “A Hybrid Approach to Private Record Linkage,” in ICDE, 2008.
[52]
A. Inan, M. Kantarcioglu, G. Ghinita, and E. Bertino, “A Hybrid Approach to Private Record Matching,” IEEE Trans. Dependable Secur. Comput., 2012.
[53]
Y. Ishai, J. Kilian, K. Nissim, and E. Petrank, “Extending Oblivious Transfers Efficiently,” in Crypto, 2003.
[34]
M. J. Freedman, K. Nissim, and B. Pinkas, “Efficient Private Matching and Set Intersection,” in Eurocrypt, 2004.
[54]
[35]
Y. Gao, L. Qi, X. Liu, Y. Luo, and L. Wang, “Efficient Fuzzy Private Set Intersection from Fuzzy Mapping,” in Asiacrypt, 2024.
A. Karakasidis and V. S. Verykios, “Secure Blocking + Secure Matching = Secure Record Linkage,” J. Comput. Sci. Eng., 2011.
[55]
[36]
GenKey, “6 facts about GenKey’s ABIS – lightning fast deduplication,” Accessed 2025-09-24, 2016, https://www.genkey.com/wpcontent/uploads/2016/12/GenKey-ABIS-eBook-version-2.0-1.pdf.
D. Karapiperis and V. S. Verykios, “An LSH-Based Blocking Approach with a Homomorphic Matching Technique for PrivacyPreserving Record Linkage,” IEEE Trans. Knowl. Data Eng., 2015.
[56]
H. Kasyap, U. I. Atmaca, C. Maple, G. Cormode, and J. He, “Privacy-preserving Fuzzy Name Matching for Sharing Financial Intelligence,” arXiv preprint, 2024.
[57]
F. Kerschbaum, H. Zhang, J. Premkumar, X. Li, F. Ebrahimianghazani, L. Gamez, K. Karabina, and P. Kotian, “White paper: AON-PRISMA all-or-nothing private similarity matching,” Accessed 2025-09-24, 2023, https://aon-prisma.dev/aonprisma.pdf.
[58]
V. Kolesnikov, R. Kumaresan, M. Rosulek, and N. Trieu, “Efficient Batched Oblivious PRF with Applications to Private Set Intersection,” in ACM CCS, 2016.
[59]
H. Köpcke, A. Thor, and E. Rahm, “Evaluation of entity resolution approaches on real-world match problems,” Proc. VLDB Endow., 2010.
[60]
S. Krastnikov, F. Kerschbaum, and D. Stebila, “Efficient Oblivious Database Joins,” Proc. VLDB Endow., 2020.
[61]
A. Kulshrestha and J. R. Mayer, “Identifying Harmful Media in Endto-End Encrypted Communication: Efficient Private Membership Computation,” in USENIX Security, 2021.
[62]
M. Kuzu, M. Kantarcioglu, E. Durham, and B. A. Malin, “A Constraint Satisfaction Cryptanalysis of Bloom Filters in Private Record Linkage,” in PETS, 2011.
[63]
M. Kuzu, M. Kantarcioglu, A. Inan, E. Bertino, E. Durham, and B. A. Malin, “Efficient privacy-aware record integration,” in EDBT, 2013.
[64]
P. K. Y. Lai, S. Yiu, K. Chow, C. F. Chong, and L. C. K. Hui, “An Efficient Bloom Filter Based Solution for Multiparty Private Matching,” in SAM, 2006.
[37]
A. Gkoulalas-Divanis, D. Vatsalan, D. Karapiperis, and M. Kantarcioglu, “Modern Privacy-Preserving Record Linkage Techniques: An Overview,” IEEE Trans. Inf. Forensics Secur., 2021.
[38]
P. Grubbs, A. Khandelwal, M. Lacharité, L. Brown, L. Li, R. Agarwal, and T. Ristenpart, “Pancake: Frequency Smoothing for Encrypted Data Stores,” in USENIX Security, 2020.
[39]
S. Haffar, “(1/3) Deep dive into beneficiary de-duplication in the nigerian context: Data management workflows,” Accessed 2025-0924, 2022, https://medium.com/frontier-technologies-hub/1-3-deepdive-into-beneficiary-de-duplication-in-the-nigerian-context-datamanagement-workflows-261181d03da9.
[40]
——, “Testing a new blockchain-based solution for addressing the beneficiary de-duplication problem,” Accessed 2025-09-24, 2022, https://medium.com/frontier-technologies-hub/testing-anew-blockchain-based-solution-for-addressing-the-beneficiary-deduplication-problem-ce0cc352df6.
[41]
——, “Blockchain-based deduplication: Towards a standardized data management practice,” Accessed 2025-09-24, 2023, https://medium.com/frontier-technologies-hub/blockchain-baseddeduplication-towards-a-standardized-data-management-practice32f80fb5c78c.
[42]
——, “Humanitarian aid deduplication using blockchain technology,” Accessed 2025-09-24, 2023, https://www.frontiertechhub.org/ insights/blockchain-de-duplication-6.
[43]
K. Han, S. Kim, and Y. Son, “Private Computation on Common Fuzzy Records,” Proc. Priv. Enhancing Technol., 2025.
[87]
——, “Refugee arrivals in white nile state, sudan,” Accessed 2025-09-24, 2025, https://www.unhcr.org/sites/default/files/202505/Flash%20Update%20%231%20-%20SSD%20arrivals%20in% 20White%20Nile%20State%202025-05-18.pdf.
[88]
G. S. Manku, A. Jain, and A. D. Sarma, “Detecting near-duplicates for web crawling,” in WWW, 2007.
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 USENIX Security, 2021.
[89]
[68]
M. Naor and B. Pinkas, “Oblivious Transfer and Polynomial Evaluation,” in STOC, 1999.
A. van Baarsen and S. Pu, “Fuzzy Private Set Intersection with Large Hyperballs,” in Eurocrypt, 2024.
[90]
[69]
——, “Efficient oblivious transfer protocols,” in ACM SODA, 2001, http://dl.acm.org/citation.cfm?id=365411.365502.
——, “Fuzzy Private Set Intersection from VOLE,” IACR Cryptol. ePrint Arch., 2025.
[91]
[70]
F. Niedermeyer, S. Steinmetzer, M. Kroll, and R. Schnell, “Cryptanalysis of Basic Bloom Filters Used for Privacy Preserving Record Linkage,” J. Priv. Confidentiality, 2014.
D. Vatsalan and P. Christen, “An Iterative Two-Party Protocol for Scalable Privacy-Preserving Record Linkage,” in AusDM, 2012.
[92]
——, “Scalable Privacy-Preserving Record Linkage for Multiple Databases,” in ACM CIKM, 2014.
[93]
D. Vatsalan, P. Christen, and V. S. Verykios, “A taxonomy of privacy-preserving record linkage techniques,” Inf. Syst., 2013.
[94]
A. Vidanage, P. Christen, T. Ranbaduge, and R. Schnell, “A Graph Matching Attack on Privacy-Preserving Record Linkage,” in ACM CIKM, 2020.
[95]
A. Vidanage, T. Ranbaduge, P. Christen, and R. Schnell, “Efficient Pattern Mining Based Cryptanalysis for Privacy-Preserving Record Linkage,” in IEEE ICDE, 2019.
[96]
B. Wang, W. Lueks, J. Sukaitis, V. G. Narbel, and C. Troncoso, “Not Yet Another Digital ID: Privacy-Preserving Humanitarian Aid Distribution,” in IEEE SP, 2023.
[65]
I. Lazrig, T. C. Ong, I. Ray, I. Ray, X. Jiang, and J. Vaidya, “Privacy Preserving Probabilistic Record Linkage Without Trusted Third Party,” in PST, 2018.
[66]
C. Li, L. Jin, and S. Mehrotra, “Supporting Efficient Record Linkage for Large Data Sets Using Mapping Techniques,” World Wide Web, 2006.
[67]
[71]
North Carolina State Board of Elections, “Voter Registration Data,” Accessed 2025-09-24, 2025, https://www.ncsbe.gov/resultsdata/voter-registration-data.
[72]
B. Pinkas, T. Schneider, and M. Zohner, “Scalable Private Set Intersection Based on OT Extension,” ACM Trans. Priv. Secur., 2018.
[73]
Z. Rahman, P. Verhaert, and C. Nyst, “Biometrics in the humanitarian sector,” Accessed 2025-09-24, 2018, https://policy-practice.oxfam.org/resources/biometrics-in-thehumanitarian-sector-620454/.
[74]
T. Ranbaduge, P. Christen, and D. Vatsalan, “Tree Based Scalable Indexing for Multi-Party Privacy-Preserving Record Linkage,” in AusDM, 2014.
[75]
T. Rausch, S. Chatel, and W. Lueks, “Artifact: xDup: PrivacyPreserving Deduplication for Humanitarian Organizations using Fuzzy PSI,” Apr. 2026, https://doi.org/10.5281/zenodo.19480020.
[97]
R. Wei and F. Kerschbaum, “Cryptographically Secure Private Record Linkage Using Locality-Sensitive Hashing,” Proc. VLDB Endow., 2023.
[76]
E. Reidy, “How a fingerprint can change an asylum seeker’s life,” Accessed 2025-09-24, 2017, https://webarchive.archive.unhcr.org/ 20230518182616/https://www.refworld.org/docid/5a1694724.html.
[98]
WFP, “Building blocks ukraine unintended assistance overlap prevention report,” Accessed 2025-09-24, 2022, https://docs.wfp.org/ api/documents/WFP-0000146541/download/.
[77]
D. Richardson, M. Rosulek, and J. Xu, “Fuzzy PSI via Oblivious Protocol Routing,” IACR Cryptol. ePrint Arch., 2024.
[99]
——, “Building blocks,” Accessed 2025-09-24, 2023, https://www. wfp.org/building-blocks.
[78]
P. Rindal and L. Roy, “libOTe: an efficient, portable, and easy to use Oblivious Transfer Library,” https://github.com/osu-crypto/libOTe.
[79]
L. Roy, “SoftSpokenOT: Communication-Computation Tradeoffs in OT Extension,” IACR Cryptol. ePrint Arch., 2022.
[100] WFP Scope, “User manual: Biometric deduplication,” Accessed 2025-09-24, https://usermanual.scope.wfp.org/cash-accounts/ content/intros to sections/deduplication.htm.
[80]
M. Scannapieco, I. Figotin, E. Bertino, and A. K. Elmagarmid, “Privacy preserving schema and data matching,” in ACM SIGMOD, 2007.
[81]
R. Schnell, T. Bachteler, and J. Reiher, “Privacy-preserving record linkage using Bloom filters,” BMC Medical Informatics Decis. Mak., 2009.
[82]
——, “A Novel Error-Tolerant Anonymous Linking Code,” SSRN Electronic Journal, 2011.
[83]
S. Stammler, T. Kussel, P. Schoppmann, F. Stampe, G. Tremper, S. Katzenbeisser, K. Hamacher, and M. Lablans, “Mainzelliste SecureEpiLinker (MainSEL): privacy-preserving record linkage using secure multi-party computation,” Bioinform., 2022.
[84]
[85]
[86]
The Engine Room, “Biometrics in the humanitarian sector,” Accessed 2025-09-24, 2023, https://www.theengineroom.org/wpcontent/uploads/2023/07/TER-Biometrics-Humanitarian-Sector.pdf. The Times of India, “Ghost anganwadi beneficiaries haunt govt,” Accessed 2025-09-24, 2011, https://timesofindia.indiatimes. com/city/bhubaneswar/ghost-anganwadi-beneficiaries-hauntgovt/articleshow/7300302.cms. UNHCR, “Over 3,000 congolese refugees arrive in uganda in three days,” Accessed 2025-09-24, 2020, https://www.unhcr.org/us/news/briefing-notes/over-3-000congolese-refugees-arrive-uganda-three-days.
[101] B. Wille, “You don’t need to demand sensitive biometric data to give aid. the ukraine response shows how.” Accessed 2025-09-24, 2023, https://www.thenewhumanitarian.org/opinion/2023/07/11/you-dontneed-demand-sensitive-biometric-data-give-aid-ukraine-responseshows. [102] B. Wille and K. L. Jacobsen, “The data of the most vulnerable people is the least protected,” Accessed 202509-24, 2023, https://www.adalovelaceinstitute.org/blog/data-mostvulnerable-people-least-protected/. [103] W. Wu, B. Li, L. Chen, J. Gao, and C. Zhang, “A Review for Weighted MinHash Algorithms,” IEEE Trans. Knowl. Data Eng., 2022. [104] Q. Ye, R. Steinfeld, J. Pieprzyk, and H. Wang, “Efficient Fuzzy Matching and Intersection on Private Datasets,” in ICISC, 2009.
Appendix A. Oblivious Transfer 1-out-of-N Oblivious Transfer (OT) is a two party functionality between a querier Q and a responder R that holds N messages m0 , . . . , mN −1 ∈ {0, 1}ℓ of length ℓ. OT allows Q to learn mc for an arbitrary choice c ∈ ZN such that (a) R learns no information about Q’s choice c (nor
the chosen message mc ), and (b) Q learns no information about the non-chosen messages mi for i ∈ ZN \ {c}. Variants. OT functionalities can be classified by how much control the sender has over the messages. In chosen OT (Fig. 11a), the sender can input a set of arbitrarily chosen messages. In random OT (Fig. 11b) the messages are randomly sampled by the protocol and then output to the sender, giving the sender no control over the messages. In correlated OT (Fig. 11c), only one message m0 is randomly chosen by the protocol. The remaining messages m1 , . . . , mN −1 are computed by evaluating arbitrary correlation functions f1 , . . . , fN −1 chosen by R on m0 . The querier Q learns mc = fc (m0 ) where f0 is the identity function. Implementations. Direct OT implementations typically rely on public-key techniques [20], [69]. Oblivious Transfer Extension (OTe) protocols [9], [53], [58], [79] can efficiently extend OTs – i.e., perform a large number of OTs given a few base OTs and typically using only symmetric key techniques. OTe protocols usually only provide random OT functionality [53], [79]. Constructions. Random OT can be transformed into chosen and correlated OT at the cost of additional communication. In both cases, Q and R run a random OT with choice c, returning the random messages ω0 , . . . , ωN −1 to R and ωc to Q. For chosen OT, R uses these random messages to mask the chosen messages as µi = mi ⊕ ωi and sends µ0 , . . . , µN −1 to Q, who can only reconstruct mc = µc ⊕ ωc . For correlated OT, R uses m0 = ω0 , computes µi = fi (m0 ) ⊕ ωi , and sends µ1 , . . . , µN −1 to Q, who can only reconstruct mc = µc ⊕ ωc (with µ0 = 0ℓ ). The construction for correlated OT requires one fewer message to be sent, making correlated OT from random OT (like OTe) more efficient that chosen OT from random OT. Large Messages. For large ℓ-bit messages, a random OT can also be implemented by executing a random OT for λ-bit messages (where λ is a security parameter) and then using λ ℓ a public pseudo-random function F : {0, 1} → {0, 1} to extend the random λ-bit messages into pseudo-random ℓbit messages. Combining this with the construction above provides 1-out-of-N chosen and correlated OT for ℓ-bit messages at the cost of one λ-bit random OT, N evaluations of F , and N ℓ bits of communication for chosen OT ((N − 1)ℓ bits for correlated OT).
Appendix B. Full Proofs otFPSI. otFPSI (Fig. 7) securely implements FFPSI (Fig. 3)
against semi-honest adversaries in the OT-hybrid model: Let otFPSI-h denote the hybrid protocol with an idealized OT. Correctness. Let FFPSI (Q, R) = (FFPSI,Q (Q, R), ⊥) be the ideal FPSI functionality (Fig. 3). We denote the output of an execution of otFPSI-h by outotFPSI-h (Q, R) = (outotFPSI-h (Q, R), ⊥). Q
c ∈ ZN
cOT
m0 , . . . , mN −1 ∈ {0, 1}ℓ
mc (a) Chosen OT.
c ∈ ZN
rOT m0 , . . . , mN −1 ∈ {0, 1}ℓ
mc
(b) Random OT.
c ∈ ZN
corOT
f1 , . . . , fN −1 : {0, 1}ℓ → {0, 1}ℓ m0 ∈ {0, 1}ℓ
fc (m0 ) (c) Correlated OT.
Figure 11. Overview over 1-out-of-N OT variants.
#” #” As for the single comparison (§6.3), Di [k] − Mi [k] mod p = dH (qi , rk ) holds for i ∈ [nQ ], k ∈ [nR ]. Hence, (i, k) ∈ outotFPSI (Q, R) ⇐⇒ bi,k = 1 Q #” #” ⇐⇒ Di [k] − Mi [k] mod p ≤ τ ⇐⇒ dH (qi , rk ) ≤ τ ⇐⇒ (i, k) ∈ FFPSI,Q (Q, R).
Thus, outotFPSI-h (Q, R) = FFPSI (Q, R) and otFPSI is correct. Security. A party P ’s view viewotFPSI-h (Q, R) consists of P its input and the messages it receives during the protocol execution. To prove security, we show that a party’s view of otFPSI-h can be simulated based on inputs and outputs of the idealized functionality FFPSI , and simulated views are indistinguishable from views in the hybrid protocol. Simulating R’s View. During the execution of otFPSI-h, R receives no messages. Its view consists only of its input and can be trivially simulated by SimR (R, ⊥) that only outputs R. The simulated and hybrid views follow the same distribution, i.e., {SimR (R, ⊥)}Q,R ≡ {viewotFPSI-h (Q, R)}Q,R . R Simulating Q’s View. During the execution of otFPSI-h, Q # ”, . . . , m # ” receives m 0,0 nQ ,l and b0,0 , . . . , bnQ ,nR . We construct # ”, . . . , m # ” a simulator SimQ (Q, I) which samples m 0,0 nQ ,l ←$ nR Zp , sets bi,k = ((i, k) ∈ I) for i ∈ [nQ ], k ∈ [nR ], and outputs the messages in the correct order. In otFPSI-h, the # ”, . . . , m # ” m 0,0 nQ ,l are uniformly random in Zp and the bi,k are an immediate encoding of the result FFPSI,Q (Q, R). Hence, simulated and hybrid views follow the same distribution: {SimQ (Q, FFPSI,Q (Q, R))}Q,R ≡ {viewotFPSI-h (Q, R)}Q,R . Q Therefore, otFPSI securely implements FFPSI . otFPSI-ss. otFPSI-ss (Fig. 8) securely implements FssFPSI in the OT-hybrid model against semi-honest adversaries. Let otFPSI-ss-h denote the hybrid protocol with idealized OT. Correctness. We denote the probabilistic FssFPSI functionality by FssFPSI (x, y) = (FssFPSI,1 (x, y), FssFPSI,2 (x, y)) with
b R) b . For (P , Pb) ← outotFPSI-ss (x, y): x = (Q, R) and y = (Q, P i,j = (Di,j − Mi,j mod p ≤ τ ) ⊕ Pbi,j = (dH (qi ⊕ rj , qbi ⊕ rbj ) ≤ τ ) ⊕ Pbi,j = (dH (qi , rj ) ≤ τ ) ⊕ Pbi,j .
Hence, outotFPSI-ss (x, y) = ((dH (qi , rj ) ≤ τ )i,j ⊕ Pb, Pb) where Pb is uniformly random. By definition, FssFPSI (x, y) = c, M c) with uniformly random M c. ((dH (qi , rj ) ≤ τ )i,j ⊕ M Hence, {FssFPSI (x, y)}x,y ≡ {outotFPSI-ss (x, y)}x,y holds. Simulating S2 ’s View. In the hybrid protocol otFPSI-ss-h, S2 receives no messages. As for R in otFPSI, a simulator Sim2 (y, ⊥) that outputs only S2 ’s input y perfectly simulates S2 ’s view, i.e., {Sim2 (y, ⊥)}x,y ≡ {viewotFPSI-ss-h (x, y)}x,y . 2 Hence, it follows that {Sim2 (y, ⊥), FssFPSI (x, y)}x,y ≡ {viewotFPSI-ss-h (x, y), outotFPSI-ss-h (x, y)}x,y . 2 Simulating S1 ’s view. In the hybrid otFPSI-ss-h, S1 receives the messages m1,1,1 , . . . , mnQ ,nR ,l and P 1,1 , . . . , P nQ ,nR . We construct a simulator Sim1 (x, M ) which samples m1,1,1 , . . . , mnQ ,nR ,l ←$ Zp , samples P 1,1 , . . . , P nQ ,nR ←$ {0, 1}, and outputs the messages in the correct order. As all messages received by S1 in otFPSI-ss-h are uniformly random, simulated views have the same distribution 1 {Sim1 (x1 , FssFPSI (x, y))}x,y ≡ {viewotFPSI-ss-h (x, y)}x,y . It 1 1 follows that {Sim1 (x, FssFPSI (x, y)), FssFPSI (x, y)}x,y ≡ {viewotFPSI-ss-h (x, y), outotFPSI-ss-h (x, y)}x,y . 1 We conclude that otFPSI-ss securely implements FssFPSI . otFPSI-ssb. otFPSI-ssb (Fig. 9) securely implements FssFPSI in the OT-hybrid model against semi-honest adversaries. Let otFPSI-ssb-h denote the hybrid protocol with idealized OT. Correctness. With i ∈ [nQ ], j ∈ [nR ], j ∈ [l], z = (i, j, k) it holds that dz = FXi,k (z, cz ) + FYj,k (z, cz ) + µz,cz mod p = FXi,k (z, cz ) + FYj,k (z, cz ) + mz,cz − FX qi [k] (z, cz ) − F rj [k] (z, cz ) mod p i,k
Yj,k
= mz,cz = mz,2qi [k]+rj [k] .
By construction, we have mz,2qi [k]+rj [k] = mz + (qi [k] ⊕ rj [k] ⊕ bbz ). Hence, dz − mz mod p = qi [k] ⊕ rj [k] ⊕ qbi [k] ⊕ Pl rbj [k] = qi [k] ⊕ rj [j]. Since Di,j = k=1 d(i,j,k) mod p Pl and Mi,j = m mod p , it follows that Di,j − (i,j,k) k=1 Mi,j mod p = dH (qi , rj ). The threshold comparison step of otFPSI-ssb is identical to otFPSI-ss. Using the same argument, it follows that the outputs of otFPSI-ssb and FssFPSI follow the same distribution: {FssFPSI (x1 , x2 )}x1 ,x2 ≡ {outotFPSI-ssb (x1 , x2 )}x1 ,x2 . Simulating S2 ’s View. As in otFPSI-ss-h, S2 ’s view can be perfectly simulated since S2 receives no messages. Simulating S1 ’s view. S1 receives the messages X1,1 , . . . , XnQ ,l , Y1,1 , . . . , YnR ,l , µ(1,1,1),1 , . . . , µ(nQ ,nR ,l),3 and P 1,1 , . . . , P nQ ,nR . We construct Sim1 (x1 , M ) that samples these messages uniformly random from their respective domain and outputs them in the correct order. Views generated by the simulator are computationally indistinguishable (c.id.) from views in the hybrid protocol: We first argue that,
for a single z = (i, j, k), the µz,1 , µz,2 , µz,3 in the hybrid view are c.id. from random. In the hybrid protocol, the ideal 0 OT perfectly hides one of the random PRF keys Xi,k and 1 0 1 Xi,k (and one of Yj,k and Yj,k ) from S1 . If cz = 0, all the µcz ,x contain at least one term that is an evaluation of the PRF F with a random key that is not contained in S1 ’s view. Since S2 does not evaluate F twice on the same input under the same key, these terms are c.id. from random by the PRF property of F . With this, the µz,1 , µz,2 , µz,3 in the view are also c.id. from random. If cz ̸= 0, the µz,x for x ̸= cz are c.id. from random following the same argument. Hence, they computationally hide information about mz,0 and mz,1 . The value µz,cz is a sum which contains mz,cz which in turn is a sum containing at least one PRF evaluation with a key not included in the view, rendering mz,cz c.id. from random. Thus, µz,cz is also c.id. from random. For one z , the µz,x in S1 ’s hybrid view can, hence, be replaced with random values while keeping the views c.id. Therefore, hybrid views are c.id. from intermediate hybrid views where the µz,x are replaced by random values for all z . Since all messages in these intermediate views have the same distribution as views generated by c 1 the simulator. Hence, {Sim1 (x1 , FssFPSI (x1 , x2 ))}x1 ,x2 ≡ otFPSI-ssb-h {view1 (x1 , x2 )}x1 ,x2 , and, as a result, it holds c 1 that {Sim1 (x1 , FssFPSI (x1 , x2 )), FssFPSI (x1 , x2 )}x1 ,x2 ≡ otFPSI-ssb-h otFPSI-ssb-h {view1 (x1 , x2 ), out (x1 , x2 )}x1 ,x2 Hence, otFPSI-ssb securely implements FssFPSI .
Appendix C. Embeddings and Matching C.1. Details about our Embedding We present our embedding strategy in more detail. Our survey of the literature did not highlight an embedding into Hamming space proposed in the record linkage domain that would be suitable for humanitarian organizations. Thus, we propose a new embedding E and evaluate it to show that it works well for humanitarian deduplication. That being said, we stress that xDup is agnostic to the concrete embedding used, and this construction may be easily replaced. Construction. To transform a record into a bit string, we first compute its set of q -grams (i.e., all substrings of length q ). We then construct the embedding by concatenating 1-bit locality-sensitive hash (LSH) values of the q -grams set. As LSH preserves the similarity of the input (i.e., the set of q -grams), the number of identical bits in embedded strings can be used to estimate the similarity of the sets of q -grams, and therefore the similarity of the original records. Embedding into Hamming Space. A locality-sensitive hashing scheme [17] is a family of functions H for a similarity function sim , such that Prh←$F [h(x) = h(y)] = sim (x, y). Charikar [17] proposes to embed a similarity with an LSH with range {0, 1} into Hamming space by concatenating l individual LSH values. The more similar two objects are, the more individual bit LSH values will match, and the lower
TABLE 7. FALSE - NEGATIVE RATES OF THE EMBEDDING WITH SMALLER THRESHOLDS . E MPTY CELLS : FPR EXCEEDS 0.1 %.
0.98 0.96 0.00
EpiLink Jaccard l = 127 l = 255 l = 384 l = 511 l = 2047
0.02 0.04 False Positive Rate
FPR/FNR
Recall
1.00 10−1
10−3 0.0
τ FPR FNR 0.1 0.2 0.3 0.4 Normalized Threshold
l
4
8
16
32
64
511 96.5 % 96.0 % 90.4 % 73.6 % 34.1 % 255 95.8 % 90.6 % 73.5 % 35.4 % 127 90.1 % 73.0 % 36.0 %
(a) ROC curve for embedding, EpiLink, (b) FPR and FNR over normalized and Jaccard baselines. threshold τ /l for l = 511.
Figure 12. Accuracy of classifying records as duplicate/non-duplicate in a database of 131 072 records (q = 2).
the Hamming distance will be. We apply this construction to the Minhash [12] LSH for the Jaccard similarity of sets. Handling Records. To apply Minhash to the structured registration records of humanitarian organizations, we first need to convert these records to sets. We do this by computing the q -grams of each attribute individually and then uniting these sets while keeping q -grams of different attributes domainseparated. Assuming a record x consists of the attributes x[1], . . . , x[na ], we convert x into the set [ X= (1) i∈[na ] {(i∥g) | g ∈ gramsq (x[i])} and then transform the set X to a bit string of length l using the Minhash-based embedding described above. Evaluation. As our work deals with recipients’ personal information, we do not work with real humanitarian data but with public, partially synthetic datasets. For a meaningful evaluation, we need a dataset with ground truth relevant for our use case. Prior works often used standard bibliographic, location, or e-commerce datasets [44], [59] whose attributes and duplicates are not representative of those encountered by humanitarian organizations. We curate a new dataset by extending the public North Carolina Voter Registration database [71], enabling us to imitate real duplicates in a controlled manner with a determined ground truth. We detail the preprocessing and synthetic duplicate generation in Appendix C.3. To match humanitarian use cases, the dataset consists of the following fields: first and last names, date of birth, gender, mother’s first and last name, and father’s first name. To illustrate the accuracy of our embedding, we compare it to the EpiLink matching algorithm [24] that has also been used to implement PPRL [83]. We expand on the parameter choices for EpiLink in Appendix C.4. We also compare our embedding to the Jaccard similarity on domain-separated q -grams as defined in Eq. (1). To compare all three methods, we sample a reference database of 131 072 records and a test dataset consisting of both test records that have a duplicate in the reference database and test records that do not. For each test record, we compute the similarity to all records in the reference database and determine the maximum similarity. We classify each test record as a duplicate or non-duplicate by comparing the maximum similarity to a range of thresholds.
Fig. 12a shows that EpiLink, the Jaccard similarity, and our embedding with l = 2047 essentially provide the same accuracy. It is only insignificantly worse for l = 511, but accuracy measurably degrades for smaller l. Optimal Threshold. To use the embedding with xDup, we need to set a Hamming distance threshold τ . To achieve the target false positive rate (FPR) of less than 0.1 % (RQ.P1) while keeping the false negative rate (FNR) low, we choose the maximum Hamming distance threshold satisfying this constraint. For l = 511, this point is at τ = 132 (see Fig. 12b). For this threshold, we achieve an FPR of 0.0977 % and an FNR of 0.574 %. For lower l, we observe a higher FNR at the same FPR: 1.25 % for l = 384 (τ = 95), 2.23 % for l = 255 (τ = 50), and 10.9 % for l = 127 (τ = 24). Our embedding is able to achieve the target false-positive rate (RQ.P1) while minimizing false negatives at τ ≈ l/4. Lower Thresholds. Existing FPSI protocols typically use a small threshold relative to the dimension. To evaluate how our embedding performs in such a situation, we report the false-negative rates at select thresholds in Table 7. Performance. Computing this embedding is done locally and offline by the party holding the registration records. The computation is cheap and can be easily parallelized for multiple records. Using a naive Python implementation, we can compute the embedding of one record for l = 511 in 2.96 ms. Take-away. Our embedding works well for deduplication as it provides high accuracy and can be computed efficiently. However, we stress that xDup is agnostic to the underlying embedding, given that each party can compute the embeddings of its records locally. Should this specific transformation not translate well to other applications, potential alternatives include working on subsets of attributes [43], weighted versions of Minhash [3], [103], SimHash [67], or approaches based on machine learning [57].
C.2. Embeddings into Euclidean Space In the following, we present embeddings of records into Euclidean space that were proposed in the record linkage domain and estimate the embedding dimension necessary in the context of humanitarian deduplication. We again assume that records consist of five string fields, a date of birth and a gender attribute. Li et al. [66] present StringMap, an algorithm to transform strings into vectors in Euclidean space for non-private record linkage. They embed each attribute individually and
recommend a dimension between 15 and 25 for each attribute. For our records consisting of five string fields (neglecting date of birth and gender), this would result in a total dimension of at least 75 to 125. However, their embedding algorithm operates on the database of all records in a nonprivate setting. It is unclear how this algorithm could be used in a private setting where records are distributed among multiple parties. Bonomi et al. [8] propose to transform records into vectors in Euclidean space based on the occurrence of frequent grams in the record. The frequent grams are extracted from the entire database using differentially-private methods. In their evaluation, they chose a dimension of 75 for one single attribute. Applying this approach to records with more attributes would likely require an even higher dimension. Scannapieco et al. [80] propose using SparseMap, a Lipschitz embedding that transforms records into vectors in Euclidean space by expressing them in terms of their similarity to a set of reference values. Their evaluation does not allow us to confidently predict the accuracy of their embedding in our setting. Still, we estimate that to achieve sufficient accuracy when comparing query records to large databases of records, we need at least a dimension of 30 for their evaluation data. As their data consists only of first and last name, we estimate we would need at least a dimension of 60 to embed the five string attributes of our records.
C.3. Synthetic Deduplication Dataset We base our dataset on the North Carolina Voter Registration database (NCVR) which contains all registered voters in the U.S. state of North Carolina [71]. Pre-Processing We pre-process the database as follows: We remove all records that miss a first name, last name, or year of birth. We extend the year of birth to a full date of birth by randomly sampling both day and month. For each record, we add the father’s first name and mother’s first and last name by randomly sampling a male and female first name and a last name from the database. Synthetic Duplicate Generation. We synthetically generate duplicates by applying perturbations to existing records. For each generated duplicate, we apply up to four perturbations to randomly chosen attributes. Each perturbation is chosen at random from an attribute-specific list. With a probability of 1/16 for each perturbation, a destructive modification is chosen (like deleting the value or replacing it with a random value). Otherwise, a non-destructive perturbation is applied, e.g., inserting, deleting, replacing, or swapping characters. For fixed-length fields, we do not apply lengthchanging perturbations. For the date of birth, we also include a perturbation that sets it to January 1st to emulate that exact dates of birth may not always be available in humanitarian contexts. When the gender field is selected for perturbation, its value is randomly replaced.
TABLE 8. OVERVIEW OF WEIGHTS USED FOR DEDUPLICATION WITH ATTRIBUTE - LEVEL SIMILARITY METRICS , AVERAGE FREQUENCIES fi , ERROR RATES ei , AND WEIGHTS wi . SIM≈ DENOTES FUZZY COMPARISON USING B LOOM F ILTERS , SIM= DENOTES COMPARISON BY EQUALITY.
Attribute first_name last_name gender dob_year dob_month dob_day first_n_mother last_n_mother first_n_father
Metric sim≈ sim≈ sim= sim= sim= sim= sim≈ sim≈ sim≈
fi
ei
wi
−5
0.302 0.302 0.154 0.135 0.197 0.204 0.303 0.303 0.304
9.89 10.6 0.526 4.46 2.27 3.17 9.90 10.6 9.44
3.55 × 10 1.77 × 10−5 0.5 0.01 0.0833 0.0333 3.48 × 10−5 1.77 × 10−5 5.53 × 10−5
C.4. EpiLink Parameter Choices To evaluate the EpiLink matching functionality [4], [83], we need to choose fields, weights, and attribute similarity metrics. We choose the same comparison mechanisms and parameters as Stammler et al. [83]: fields are converted into 2-grams and then inserted into Bloom Filters of length 500 bit using 15 hash functions. Additionally, we split the date of birth into its individual components. As suggested by Contiero et al. [24], we determine an attribute’s weight based on its average frequency of values fi and its error rate ei as: 1 − ei wi = log2 . fi We determine attribute frequencies and error rates based on the parameter selection dataset: We sample 218 original records and compute the average frequency of values for each attribute. To determine the error rates, we compare each of the sampled original records to its synthetically generated duplicate and for each attribute determine the error rate. A record-pairs has an error in an attribute if the attribute’s values are not exactly equal. We show the attributes for deduplication and their associated weights in Table 8.
C.5. Matching with Private Approximate Jaccard Adir et al. [3] present a different approach for matching that does not rely on SMC: Using Minhash [12], they transform each record to a number of fingerprints such that, for a pair of records with high Jaccard similarity, one or more fingerprints will be equal with high probability. This transformation can be used for private matching by running PSI on these fingerprints. Han et al. [43] extend this to angular similarity and provide a more detailed analysis of parameter choices. The main strength of this approach is that it overcomes the need for explicit pairwise matching as it allows fuzzily comparing sets of records using PSI in sub-quadratic run time.
b=30 b=50 b=100 Jaccard Our Embedding
0.9 0.8 0.00
0.05
0.10 0.15 0.20 False Positive Rate
Time [s]
Recall
1.0
0.25
Figure 13. ROC curve for matching with Private Approximate Jaccard [3] for different number of fingerprints b, exact Jaccard, and our embedding (l = 511) for nR = 217 .
Construction. Adir et al. [3] propose to generate b fingerprints for each record using the Minhash LSH scheme [12]. Each fingerprint consists of r Minhash values of the record. Specifically, we convert a record x into a set X by computing its q -grams or domain-separated q -grams as in Eq. (1). For permutations π0 , . . . , πb·r−1 , the fingerprints of X are defined as fi (X) = (mπi·r (X), . . . , mπi·r+r−1 (X)).
where mπ is a Minhash function. For sets X and Y , the probability that one of the fingerprints collides depends on their similarity: Pr[∃i < b : fi (X) = fi (Y )] = 1 − (1 − simJ (X, Y )r )b .
Han et al. [43] analyze how to choose parameters for this construction such that a collision likely occurs if the similarity is greater than a given threshold τ . Evaluation. As for our embedding, we use domainseparated q -grams (Eq. (1)) with q = 2. We compress the individual fingerprint vectors fi (x) into one value using a hash function. Han et al. [43] choose the number of fingerprints as b ∈ {30, 50, 100}. For each b, we evaluate a range of values for r and present the results as a ROC curve. Results. Fig. 13 compares the accuracy of this private approximation of the Jaccard similarity, the exact Jaccard similarity, and our embedding (Appendix C.1) when matching one record against a database of nR = 131 072 records. We observe that the private Jaccard approximation does not achieve an accuracy that is comparable to the Jaccard similarity or our embedding. To achieve our target FPR of less than 0.1 % (RQ.P1), we would need to accept a recall of only 86.5 % for b = 100 (and only 76.1 % for b = 30), while our embedding is able to achieve a significantly higher recall of 99.4 % (see Appendix C.1).
101 100 28 211 Dimension l
214
Figure 14. Run time of otFPSI for nQ = nR = 256 by dimension l (τ = 42, Gigabit, SoftSpoken OTe).
OT block. Thus, for completeness, we also evaluate otFPSI with SoftSpokenOT [79]. SilentOT and SoftSpokenOT provide a different tradeoff in terms of communication and computation cost: While SilentOT is significantly more communication-efficient, it requires more computation and different cryptographic hardness assumptions. In Fig. 14, we confirm the theoretical relationship between otFPSI’s runtime and the dimension l (i.e., O(l log l)). In Table 9, we present the overall performance of otFPSI using SoftSpokenOT. Table 10 presents the performance of the secret-shared variants otFPSI-ss and otFPSI-ssb. We observe similar trends as in the instantiation with SilentOT seen in §7. The major differences are slightly faster runtimes at the cost of larger communication. For otFPSIss, we observe significantly increased communication due to the large number of OTs performed by the protocol.
D.2. Comparison with Prior FPSI Protocols
D.1. Evaluation with SoftSpokenOT
D.2.1. FLPSI. The FLPSI protocol [88] approximates the Hamming distance using a sub-sampling approach: For a bit string q , it generates T sub-samples where each subsample consists of L bits of q at positions determined by fixed random masks. Two bit strings are considered to match if they have at least t sub-samples in common. In practice, the complexity of their protocol restricts the number of subsamples T as well as the threshold t. We evaluate the accuracy of this approach and find it is not sufficient for our application. For this, we use the same parameters as the authors (l = 256, T = 64, t = 2, τ = 25) to sample random pairs of bit strings and compare them using the sub-sampling approach. We observe that 0.0015 % of pairs are falsely classified as matching even though their Hamming distance is greater than τ . When comparing one bit string to a database of 100 000, we therefore expect that 1.5 of the individual comparisons are falsely positive. This effect leads to a substantial overall false-positive rate since almost every queried record will be considered a duplicate of one (or multiple) records in the database, violating RQ.P1. Due to this sub-sampling technique, FLPSI is unable to provide the necessary accuracy for humanitarian deduplication.
As discussed in §7, we used SilentOT as a building block in our construction. Yet, otFPSI can be instantiated with any
D.2.2. Fmap-FPSI. We now discuss Fmap-FPSI [35] in more detail. The Fmap primitive relies on the key assump-
Appendix D. Evaluation
TABLE 9. RUN TIME AND COMMUNICATION OF OT FPSI USING S OFT S POKEN OT FOR QUERIER SET SIZE nQ , RESPONDER SET SIZE nR , AND DIMENSION l ( THRESHOLD τ = ⌊l/16⌋ ). l = 127
l = 511
l = 8191
nQ
nR
Gigabit
Slow
Comm
Gigabit
Slow
Comm
Gigabit
Slow
Comm
64 256 1024 4096
64 256 1024 4096
0.032 s 0.258 s 3.84 s 61.0 s
0.744 s 1.43 s 8.72 s 123 s
0.802 MiB 11.8 MiB 186 MiB 2.89 GiB
0.077 s 0.969 s 15.1 s 240 s
0.927 s 2.96 s 30.6 s 477 s
3.08 MiB 46.0 MiB 724 MiB 11.3 GiB
1.24 s 24.5 s 418 s 6744 s
4.31 s 48.8 s 900 s 15 085 s
72.4 MiB 1.08 GiB 17.2 GiB 274 GiB
1 1 1 1
16 384 131 072 524 288 1 048 576
0.075 s 0.466 s 1.83 s 3.64 s
0.912 s 1.84 s 4.70 s 8.38 s
2.91 MiB 23.1 MiB 92.5 MiB 185 MiB
0.241 s 1.79 s 7.13 s 14.3 s
1.30 s 4.86 s 15.5 s 30.4 s
11.3 MiB 90.0 MiB 360 MiB 720 MiB
4.58 s 36.5 s 146 s 291 s
13.7 s 103 s 367 s 739 s
274 MiB 2.14 GiB 8.55 GiB 17.1 GiB
TABLE 10. RUN TIME AND COMMUNICATION OF PLAINTEXT OT FPSI AND SECRET- SHARED OT FPSI- SS AND OT FPSI- SSB WITH S OFT S POKEN OT FOR QUERIER SET SIZE nQ AND RESPONDER SET SIZE nR ( DIMENSION l = 511 , THRESHOLD τ = ⌊l/16⌋ = 31 ). otFPSI
otFPSI-ss
otFPSI-ssb
nQ
nR
Gigabit
Slow
Comm
Gigabit
Slow
Comm
Gigabit
Slow
Comm
64 256 1024 4096
64 256 1024 4096
0.077 s 0.969 s 15.1 s 240 s
0.927 s 2.96 s 30.6 s 477 s
3.08 MiB 46.0 MiB 724 MiB 11.3 GiB
0.240 s 3.38 s 51.0 s 807 s
1.67 s 13.6 s 198 s 3140 s
18.8 MiB 301 MiB 4.70 GiB 75.1 GiB
0.194 s 2.58 s 40.7 s 649 s
1.24 s 5.38 s 87.9 s 1470 s
7.90 MiB 120 MiB 1.85 GiB 29.5 GiB
1 1 1
16 384 131 072 524 288
0.241 s 1.79 s 7.13 s
1.30 s 4.86 s 15.5 s
11.3 MiB 90.0 MiB 360 MiB
0.897 s 6.73 s 26.8 s
4.11 s 26.0 s 100 s
75.1 MiB 601 MiB 2.35 GiB
tion that each element in the receiver’s set has τ + 1 unique components: i.e., for each element, there are τ + 1 dimensions where all other elements have a different value. This assumption is very restrictive as it: (i) constricts the threshold in relation to the dimension (e.g., their implementation requires l > 8(τ + 1)), and (ii) limits the maximum receiver set size. For example, for bit strings of length l = 512 and threshold τ = 128 and without pre-processing, the largest set fulfilling this assumption has cardinality 3. The authors suggest packing multiple bits into one dimension of a lower-dimensional integer vector. For our parameters, we can pack at most three bits into one component (otherwise, the dimension would be less than τ + 1). When packing two or three bits, the assumption cannot hold for any sets of meaningful size. To illustrate this, we sample 16 random bit strings of size l = 512 and measure the probability that another random bit string has τ + 1 = 129 unique dimensions with regard to all 16 vectors in the set. When packing three bits, this probability is 1.92 × 10−82 and 2.16 × 10−183 when packing 2 bits. This illustrates that, in our setting with a relatively high threshold τ , we cannot rely on the assumption Fmap-FPSI is based on. To show the efficiency of otFPSI, we still compare its performance to Fmap-FPSI. Fmap-FPSI consists of an offline phase that may be re-used as long as the receiver set does not change, and an online phase. We measure both online and offline phases to allow for a fair comparison. Table 11 compares both protocol at the evaluation parameters used by the authors: For set sizes 256 and 1024, otFPSI is faster than the online phase of Fmap-FPSI. For set size
Batching not applicable for nQ = 1
TABLE 11. RUN TIME OF F MAP -FPSI AND OT FPSI WITH S ILENT OT BY SET SIZE n = nQ = nR ( l = 128 , τ = 4 , 10 Gibit/s, 0.02 ms LATENCY ) Fmap-FPSI
otFPSI
n
Online
Total
Comm
Total
Comm
256 1024 4096
2.18 s 8.79 s 35.4 s
100 s 402 s 1620 s
91.9 MiB 368 MiB 1.44 GiB
0.301 s 4.54 s 72.1 s
9.22 MiB 145 MiB 2.27 MiB
4096, this is no longer the case. Yet, the offline phase of Fmap-FPSI is so expensive that we would need 26 protocol iterations with the same receiver set until Fmap-FPSI would be faster than otFPSI in total. As otFPSI scales quadratically in the set size it can be slower than Fmap-FPSI for large sets. However, FmapFPSI achieves this linear scaling by relying on a restrictive input assumption and by requiring an offline phase that is concretely expensive. otFPSI works on any input and our experiments show that it scales better to higher dimensions and thresholds.
D.3. Comparison to Funshade Funshade [47] privately computes distance metrics between two (integer) vectors and privately compare the distance to a threshold. The protocol uses two compute parties and two data holders (that may be different from the compute parties), which is a similar system model to secretshared FPSI in xDup. In the following, we illustrate the limitations of the Funshade protocol.
TABLE 12. C OMPARISON OF THE EVALUATION ENVIRONMENTS OF EXISTING FPSI PROTOCOLS Year FLPSI [88]
2021
DA-PSI [16]
Machine/CPU Type
Cores/Threads
RAM
Network Setting
Parallelism a
72 vCPUs
144 GB
Not relevant for comparison
2023
Azure F72s v2 (Intel Xeon Platinum 8168) 2 × AWS EC2 t2.xlargec
4 vCPUs
16 GB
Approx-PSI [19]
2024
Unspecified
8 vCPUs
8 GB
Fmap-FPSId[35] PE-FPSI [6]
2024 2025
Intel Xeon Gold 6330 AWS EC2 c7i.metal-48xl (Intel Sapphire Rapids 8488C [5])
Unspecified 192 vCPUs [5]
256 GB 384 GB [5]
Real network with 320480 Mbit/s and unspecified latency Unspecified LAN and 480 Mbit/s with unspecified latency 10 Gbit/s, 0.02 ms latency Unlimited
Ours.
2025
Google Cloud c4dstandard-8 (AMD EPYC Turin)
4 vCPUsf
30 GB
Gigabit (1 Gbit/s, 0.5 ms latency) and slow (250 Mbit/s, 20 ms latency)
Online: single-threaded,b offline: unspecified Unspecified Single-threaded Unspecifiede Unspecified
Single-threaded
a
We only reproduce their computation costs (excluding communication). For comparison, we only use their single-threaded results. The t2.xlarge instances are burstable, i.e. do not provide constant CPU perfornamce over time [5]. d We run their code in our environment and only provide their evaluation environment for reference. e The published source code is single-threaded. f Configured to one vCPU per core. b c
Funshade utilizes Π-sharing, a variant of arithmetic secret sharing that enables one online multiplication without online communication. This is achieved by pre-generating Beaver triplets offline and building the Π-shares based on the Beaver triplets. After computing secret-shared distances, Funshade performs a threshold comparison using Function Secret Sharing (FSS). Setup. The setup phase generates Beaver multiplication triplets and FSS keys. In our system model without additional trust assumptions, we can only perform both steps in SMC. However, the authors evaluate Funshade under the assumption that the setup is performed by a trusted third party (TTP). We expect that implementing a setup without a TTP using SMC would increase costs significantly. Cost. We cannot directly estimate the cost of Funshade for our setting since the authors use parameters tailored for a different distance metric in their evaluation. Further, we were unable to reproduce their results [47, Table 2] using their code. Thus, we linearly extrapolate the presented performance numbers to our parameters (for an online query with l = 511, n = 9, nR = 131072). We estimate that the setup phase using a trusted third party would take 28.5 s over a 250 Mibit/s connection. This ignores the online phase of the protocol and the cost of a secure setup, which we expect to be significantly more expensive. Our protocol otFPSI-ss can perform the same query over the same network in just 13.3 s. Multiple Comparisons. A core benefit of secret-shared FPSI in xDup is that a field team can generate secretshares of a registration once, and the compute nodes can then repeatedly use these shares without the field team’s involvement. For Funshade, it is unclear whether the Π-shares can be reused for multiple comparisons. The evaluation results [47, Table 4] suggest that shares are reused, while the authors
also state that “fresh randomness is generated for each 1:1 verification”. Fresh shares for each comparison would put a high load on the field teams (violate RQ.D3), while it is unclear whether share reuse would retain the security guarantees of the protocol.
D.4. Evaluation Environments The FPSI works discussed in Section 7 do not have a publicly available implementation with the exception of Fmap-FPSI. Thus, in our evaluation, we can only build on the evaluation results presented by the authors in their respective papers. Table 12 gives an overview of the evaluation environments used in prior work.
Appendix E. Meta-Review The following meta-review was prepared by the program committee for the 2026 IEEE Symposium on Security and Privacy (S&P) as part of the review process as detailed in the call for papers.
E.1. Summary This paper addresses the problem of deduplication across humanitarian organizations, where multiple entities need to detect whether the same individual is registered to receive aid from each of them, in order to avoid unnecessary or duplicate assistance. The authors propose a system called xDup that relies on a two-servers FPSI construction based on OT. The authors implement the core FPSI protocol to demonstrate the feasibility of xDup and evaluate its performance.
E.2. Scientific Contributions • •
3. Creates a New Tool to Enable Future Science. 6. Provides a Valuable Step Forward in an Established Field.
E.3. Reasons for Acceptance 1) The paper presents a useful tool that tries to addresses an important and concrete real-world problem in the humanitarian sector. By focusing on a realistic deployment scenario, it introduces meaningful practical constraints that guide the protocol design and help bridge a gap in the recent FPSI literature. 2) The work demonstrates that a well-designed combination of established building blocks (OT, FPSI secretsharing) can deliver an impactful and practical service. 3) The authors also implement and evaluate their scheme, and their benchmarks show that the proposed construction significantly outperforms existing approaches.
E.4. Noteworthy Concerns 1) The paper’s central protocol seems a straightforward generalization of the SHADE protocol for obliviously computing hamming distance from OT. Yet, there are some non-trivial observations and adaptions from that SHADE protocol to a FPSI protocol with secret shared inputs. 2) The threat model assumes honest registrations, which may be difficult to guarantee in practice. In real-world humanitarian settings, field teams may face significant challenges in verifying the accuracy of biographical data provided by registrants. If an individual manages to register multiple times under different identities, the protocol may fail to detect such duplication and thus may not fully enforce fairness in aid distribution.