Privacy-Preserving Screening for Record Linkage

Privacy-Preserving Screening for Record Linkage Chenyu Huang∗† , Fan Zhang∗† , Huangxun Chen‡ , Yongjun Zhao§ , Huaming Rao∗ , Peng Chen∗ , Danqing Huang∗ ∗ Tencent Inc, ‡ Hong Kong University of Science and Technology (GZ), § Independent Researcher † Co-primary Authors

arXiv:2605.26882v1 [cs.CR] 26 May 2026

{chenyuhuang, zxfanzhang}@tencent.com, [email protected], [email protected], {huamingrao, pengchen, daisyqhuang}@tencent.com

Abstract—In an era dominated by big data and machine learning, establishing valuable data collaboration has never been more critical. However, such collaborations must operate under regulatory and legal constraints. Two-party Privacy-Preserving Record Linkage (PPRL) emerges to assess the potential collaboration value and also ensure the privacy and security of the involved data. Nevertheless, the substantial computational and communication overheads associated with PPRL hinder its practical adoption in data markets with numerous potential collaborators. Therefore, we present the Screening-then-Linkage framework, which incorporates a lightweight Screening phase prior to the resource-intensive PPRL phase, i.e., PPRS, to mitigate the scalability issue of PPRL. We propose a circuit-PSIbased system, named Appraisal to realize a secure, effective, and efficient PPRS. To reconcile the approximate matching and/or schema-aware setting required in PPRS with the limitations of the circuit-PSI supporting only symmetric functions, we propose a more communication-efficient secure permutation, i.e., Oblivious Attribute/Feature Alignment protocol tailored for PPRS. This protocol supports a broader range of comparison functions and significantly improves efficiency, i.e., reducing communication costs by a factor of 14 compared to the conventional protocol. Our rigorous analysis and comprehensive empirical evaluations demonstrate the security, effectiveness, and efficiency of Appraisal. Appraisal can accommodate up to 850× more records than the SOTA PPRS system, SFour, within the same constraints. Moreover, it is 165× faster than SOTA PPRL, indicating the Screening-then-Linkage framework substantially decreases the computation time required to identify the most valuable collaborators from a large pool of candidates. Index Terms—Multiparty Computation, Privacy-preserving Record Linkage, Secure Permutation, Private Set Intersection.

I. I NTRODUCTION Empowered by the progress of machine learning techniques, organizations endeavor to acquire more valuable data to enhance their analytical and predictive models [1]–[4] in sectors like finance [5], healthcare [6], [7] etc. These trends stimulate the growth of data federation markets, where data owners can discover potential collaborators or engage in data trading. An indispensable operation in data markets is to assess the collaboration value across multiple datasets or parties. • Example of Advertisement: Amazon Publisher Service [8] provides a platform that enables advertisers and publishers to access comprehensive data from both sides which helps them optimize advertising planning and investment. Advertisers need to select the most suitable publisher for an advertiser, Fan Zhang and Peng Chen are corresponding authors.

i.e., one that maximizes profit, and vice versa. By calculating the match rate (collaboration value), the percentage of common customers, via record linkage service [9], both parties can make more informed decisions, thereby enhancing the effectiveness of their advertising campaigns. • Example of Healthcare: Datavant [10], the leading health data marketplace, has records from over 70K hospitals and clinics. Its platform facilitates hospitals in finding appropriate datasets via its record linkage service [11]. A particularly challenging area is rare diseases, where it’s difficult to find patients. Pharmaceutical companies invest significant time linking their patients with rare diseases to various datasets [12], [13]. Unfortunately, their efforts often yield no results due to the small number of patients. Therefore, they are eager to find an efficient way to determine whether the datasets contain the patients they are interested in. In general, the collaboration value may vary on a case-bycase basis and is highly related to the statistics of the linked records, such as the quantity/ratio of linked/unlinked data. Meanwhile, to foster a prosperous data market under the data regulations and privacy laws, such as General Data Protection Regulation and China’s Personal Information Protection Law, we need a secure, effective, and efficient way to estimate the collaboration value for multiple involved parties, i.e., plaintextbased record linkage is not allowed. Specifically, it must ensure that no information is disclosed except for the estimation result (security); it should provide accurate estimation (effectiveness); and it should run efficiently to swiftly identify the most valuable dataset among massive candidates (efficiency). Numerous two-party Privacy-Preserving Record Linkage (PPRL) methods [14]–[19] have been proposed. Among these, Multi-party Computation (MPC)-based PPRL [14], [15], [18], [20] ensure security while maintaining high accuracy of linkage. However, they suffer from high computational costs. For example, the performance of SFour [18] is bottlenecked by cryptographic sorting and comparison; Wei et al. [20] involves O(n log n) secure comparisons. As a result, the best solution can only link 40K records per hour [20]. The efficiency issue becomes even more severe when dealing with a large number of potential candidates in the market. Instead of further optimizing the efficiency of PPRL itself, we observe that PPRL may be an overkill in the collaborative candidate search phase. Before pinpointing each linked record, an involved party might be more interested in the aggregated statistics of the linked records (collaboration value), such as

Fig. 1: Screening-then-Linkage Framework. the number of linked records with each potential candidate: if the number is too small, it is a waste of time to compute the exact linking record pairs. With this observation, we propose a new framework for data collaboration called Screening-thenLinkage (Fig. 1), and develop a lightweight Privacy-Preserving Record Screening (PPRS) system, Appraisal. Our main idea is to employ a lightweight protocol to securely, effectively, and efficiently estimate the aggregated statistics of linked records with all potential candidates, so as to select the most suitable targets as the input to the subsequent PPRL procedure. Notice that the relaxed goal of PPRS allows us to achieve efficiency and effectiveness simultaneously, in contrast to using PPRL directly. Instead of naively comparing all parties between databases, most PPRL works rely on blocking strategy that assigns records to different bins, and only compares the subset of the pairs in the corresponding bins. In PPRL, opting for a smaller bin size tends to compromise effectiveness in favor of efficiency, given the task’s fine-grained nature and sensitivity to the bin size. Empirically, bin size is set that in most works that requires at least O(n log n) costly secure comparisons [20], [21]. For PPRS, we can reduce the record screening problem to the set intersection problem: considering a record with multiple attributes, linking a record is determined by whether most of its attribute values have appeared in the opposite databases, which only involves O(n) secure comparisons, which is more lightweight than PPRL. Set intersection does not involve bins as in PPRL and is therefore unaffected by the impact of bin size. However, realizing a secure protocol based on the idea is not trivial. The most relevant technique is private set intersection (PSI), a protocol that can reveal the intersection result without leaking the elements outside the intersection. Adir et al. [19] implements the PSI-based PPRL, which takes all the attributes from one record as input, and two parties can determine whether the record is linked or not. However, it can only support schema-agnostic settings with exact matching, which restricts the usage scope. A straightforward solution is to input all the attribute values to PSI separately to support schema-aware setting, or input the signature bins derived from Locality Sensitive Hashing (LSH) to support approx-

imate matching [19]. However, both parties will know the intersected attribute value distribution even the records are not linked, which violates the privacy requirements of PPRL. To preserve the privacy of all the attributes, we choose circuitPSI protocol [22]–[24], which is an advanced variant of PSI to enable secure computation over the intersection. Unlike PSI, circuit-PSI outputs the boolean shares of the intersection result, preserving the privacy of the attribute value. However, it restricts that only symmetric functions can be applied to the intersection items, namely the output is not related to the order of elements in the intersection. Therefore, it cannot naturally support two basic asymmetric permutation functions: (i) replicating elements and (ii) reordering elements. But these functions are essential to support approximate matching, schema-aware setting, and complex scoring functions for collaboration value in PPRS system. To address this, we propose an Oblivious Feature Alignment (OFA) protocol to support these by enabling oblivious data permutation that builds upon secure permutation techniques [25]. Moreover, we incorporate various optimizations in OFA to make it practical in PPRS, which greatly improves efficiency. Our contributions can be summarized as follows: • We identify the discrepancy between the needs of the data market and the capabilities of existing PPRL methods and thus introduce the Screening-then-Linkage framework and the PPRS system, Appraisal, specifically to address the issue. • Appraisal incorporates the circuit-PSI and a computationally efficient OFA protocol, ensuring comprehensive support for various operations vital to PPRS, including both exact and approximate matching of attributes. • We validate the security, effectiveness, and efficiency of Appraisal through rigorous analysis and extensive evaluation. Our system is 165× faster than state-of-the-art (SOTA) PPRL [20] on million-level records, and can accommodate up to 850 times more records within the same time frame than the SOTA PPRS system, SFour [18]. II. P ROBLEM D EFINITION A. Notations For a finite set S, s ← S denotes choosing a uniformly random element from S and |S| denotes the number of elements in S. We use bold lowercase for vectors (e.g., a) and uppercase for matrices (e.g., M). a[i] (resp. M[i]) denotes the i-th entry (row), and M[i, j] is the value at the row i, column j. B. System Model We define a party denoted as P0 that seeks to identify data providers of superior quality among N other parties (P1 , P2 , ..., PN ) in the data market. Each party possesses a database denoted as Vi from domain V, comprising a collection of ni records from domain R. These parties agree on a matching function m : R × R → {0, 1}. The goal of the PPRS is to get f({v|v ∈ V0 , v ′ ∈ Vi , m(v, v ′ ) = 1}) between P0 and Pi where f(·) is a secure score function on P0 ’s linked records {v}. Without loss of generality, we assume

n0 = n1 = ... = n, nevertheless, our solution accommodates scenarios where each party holds a varying number of records. Two modes are supported [26]: (i) Schema-aware knows the schema information and focuses on the most relevant attributes. Without loss of generality, we assume all parties have the same attributes here. (ii) Schema-agnostic does not take any schema information into account and instead uses the whole attribute values as matching input. Two matching types are supported [27]: (i) Exact matching determines the match of attribute value iff they are exactly the same, unless the value is missing; (ii) Approximate matching estimates a matching probability given two attribute values, thus can tolerate the typos and different syntax representations. C. PPRL’s Trade-off b/w Efficiency and Effectiveness/Security PPRL aims at finding the exact link between the records, e.g., all linked pair (v 0 , v 1 ) where v 0 ∈ V0 , v 1 ∈ V1 between the P0 and P1 . However, the huge time cost hinders them far from practical, i.e., SOTA [20] takes hours to link 40K records from two parties. The workflow contains two stages: (i) Blocking: both parties assign the records to multiple bins via blocking. (ii) Matching: execute the attribute-level matching between the pairwise bins. The number of secure comparisons within each bin is O((n/ℓ)2 ) where ℓ is the number of bins, resulting in O(n2 /ℓ) comparisons of the whole protocol. With larger ℓ, the number of secure comparisons will decrease a lot. However, this may cause a high false negative rate due to the probability of candidate pairs of record, one from P0 and the other from P1 , assigning to the corresponding bin decrease. To balance the effectiveness and efficiency, ℓ is set to O(n log n) empirically [20], [21], resulting a time complexity O(n log n) of the whole protocol. This is only an ideal situation without considering the security. The number of records within the bin is sensitive information, which can leak the data distribution, for example, the block bin based on “gender” attribute can leak gender ratio. Thus, padding around η dummy elements in each bin is required to preserve the privacy of bin size. The SOTA [20] achieves η = n/2ℓ. Therefore, there are at least ℓ(n/ℓ + η)2 ≈ 2n log n secure comparisons. Consider a data federation market with a party, P0 and 10 candidates, each has 1M records. It takes around one month (10×70 hours per PPRL) for P0 to identify the most valuable partners. We observe that it is not necessary to find the exact linkage between P0 ’s database and all candidates. Instead, we can first quickly estimate the collaboration value, e.g., number of linked records, so that we can greatly shrink the candidates’ size. Then, P0 only needs to execute PPRL with high-valued candidates, thereby reducing computing costs. D. Rationale of Screening-then-Linkage Framework To overcome the above issue, we develop a Screening-thenLinkage framework (Algorithm 1): (i) P0 initiates the PPRS protocol with other parties and obtains the collaboration value c (Line 2–3); (ii) c is compared against a predefined threshold, and those that exceed the threshold are added to set U (Line

Algorithm 1 Screening-then-Linkage Framework Input: Data Vi of party Pi (i ∈ [0, N ]); Output: Set of linked records Ṽ 1: U = ∅ 2: for i = 1 to N do 3: P0 recoveries c from the output of PPRS(V0 , Vi ) 4: if c > threshold then 5: U = U ∪ {i} 6: for i ∈ U do 7: Ṽi = PPRL(V0 , Vi ) 8: return Ṽ ← {Ṽi |i ∈ U } 4–5); (iii) P0 gets the exact linkage by executing PPRL with the parties in U (Line 6–7). The proposed framework offers several advantages. First, executing the lightweight PPRS protocol to get the collaboration value before pinpointing exact linked records reduces the overall execution time. Secondly, PPRS ensures that no information other than the final collaboration value is leaked to P0 , thereby protecting the data privacy of the involved parties. Additionally, if we allow the disclosure of whether the records of P0 are linked, the subsequent PPRL can operate on these linked records instead of all the records. E. Screening for Record Linkage To implement a lightweight screening, reducing the number of comparisons is in urgent need. Thus, our core idea is to reduce the screening problem to the set intersection problem, which can be efficiently solved with only n secure comparisons, such as merge sort. Considering the most simple case the exact matching in a schema-agnostic setting. This process can be straightforwardly executed by merging all values from different attributes into a single, extended string. Then, it is reduced to the set intersection problem: finding the records in common from two sets V0 and V1 1) Extend to Approximate Matching: There are two main types of approximate matching: (i) fuzzy matching for string attributes, and (ii) distance matching for numeric attributes. Specifically, we employ locality-sensitive hashing (LSH) [28], a highly effective approach. It identifies the nearest neighbor in high-dimensional space and outputs identical hash values for similar inputs. We adopt MinHash LSH for string fuzzy matching and cross-polytope LSH [29] for numeric distance matching for their efficiency and effectiveness. Without loss of generality, let’s consider MinHash LSH as an example. It approximates the Jaccard coefficient between sets derived from candidate record pairs. A string is divided into a set, E, of all overlapping substrings of length q (q-grams). Then B · R different MinHash functions are adopted, each will be applied to E and output hash value mine∈E hk (e) where hk (·) is the k-th hash function. The B ·R values are grouped into B bands of R hash values, and the concatenation of the R hash values is the band’s signature. A candidate attribute pair is considered a match if at least one of the band signatures matches. Crosspolytope LSH functions similarly for numeric values, which also hashes attribute values into B bands. To incorporate LSH

with the set intersection, each attribute will be expanded to B band signatures via MinHash. An attribute is considered to be matched if one of the B signatures, for example, j-th signature, exists in the other party’s set of j-th signatures. 2) Extend to Schema-aware: In this mode, the parties will align the schema between them. The straightforward approach is to run a set intersection at the attribute level, i.e., the value of the j-th attributes is matched iff it exists in the other party’s set of j-th attributes. Then a record is considered to be linked if most of its attribute values is matched (or via a score function). However, this may not be suitable for attributes with low discriminative power, i.e., those having limited attribute space. Take the “gender” attribute as an example: the values “male” and “female” are common across both V0 and V1 , potentially leading to a high false positive rate for screening. To mitigate this, we can derive new attributes, e.g. “name gender”, by concatenating low and high discriminative attributes. This strategy can also be used when some attributes are not available in other parties, i.e., the unavailable attribute can be concatenated as one derived attribute. Now, the linkage criteria of records is determined from these derived attributes. The specific scheme for deriving new attributes can be established through empirical testing. To prove the effectiveness of this idea, we conduct the evaluation in Section VI-C with 8 (4 pairs) datasets. The balanced accuracy rate is all larger than 90%, which is competitive. III. P RELIMINARIES A. Threat Model We consider a static, semi-honest probabilistic polynomial time (PPT) adversary [18]–[20], which follows the protocol without deviation but tries to learn more beyond the outputs. Formally, let Π be a two-party protocol computing a deterministic functionality F : {0, 1}∗ × {0, 1}∗ 7→ {0, 1}∗ × {0, 1}∗ , The output of F is a pair, F0 (x0 , x1 ) to P0 and F1 (x0 , x1 ) to P1 . For i ∈ {0, 1}, the view of Pi during an execution of Π on (x0 , x1 ) is denoted by ViΠ (x0 , x1 ). Definition III.1. For a function F , Π privately computes F if there are PPT algorithms S0 and S1 such that Si (x0 , F1 (x0 , x1 )) ≈c ViΠ (x0 , x1 ) ∀x0 , x1 ∈ {0, 1}∗ , i ∈ {0, 1}, where ≈c denotes computational indistinguishability. We prove the security of our protocols in the hybrid model with composition theorem as follows. Theorem III.1 (Composition [30]). Let F1 , . . . , Fm be ideal 2-party functionalities, and let Π be a 2-party protocol in the computational (F1 , . . . , Fm )-hybrid model, where at most one ideal evaluation call occurs per round. Let f1 , f2 , . . . , fm be the 2-party protocols that evaluate Fi in the computational setting. For any PPT passive real-world adversary A and any PPT environment machine Z, there exists a PPT passive adversary S in the (F1 , . . . , Fm )-hybrid model such that F1 ,F2 ,...,Fm SimΠ,S,Z ≈c ExecΠ (f1 ,f2 ,...,fm ) ,A,Z .

B. Cryptographic Building Blocks 1) Obilivous Transfer (OT): 1-out-of-n OT [31] is a secure two-party computation protocol between a sender inputting n messages and a receiver inputting a selection index i ∈ [0, n − 1]. The receiver only gets the i-th message while the sender is oblivious to which message the receiver gets. We denote its ideal functionality as FOT . 2) Secret Sharing Schemes: (2,2)-arithmetic additive secret sharing [32]. For an l-bit A A value x, it is represented as x = ⟨x⟩A 0 + ⟨x⟩1 , where ⟨x⟩b ∈ Z2l is held by Pb for b ∈ {0, 1}. For floating-point numbers x e ∈ R, they are lifted using a specified precision f to encode them as fixed-point numbers x = ⌈e x2f ⌉ ∈ [−2l−1 , 2l−1 ]. This scheme supports the following operations: • Addition. ⟨z⟩A = ⟨x⟩A +⟨y⟩A is run by either parity locally. • Multiplication. ⟨z⟩A = FMUL (⟨x⟩A , ⟨y⟩A ), which can be computed using Beaver’s triples [33]. 2-out-of-2 XOR-based boolean sharing [32]. A boolean B B value x can be represented as x = ⟨x⟩B 0 ⊕⟨x⟩1 , where ⟨x⟩b ∈ Z2 is held by party Pb for b ∈ {0, 1}. The boolean sharing scheme supports the following operations: • XOR. ⟨z⟩B = ⟨x⟩B ⊕ ⟨y⟩B is run by either parity locally. • NOT. ⟨y⟩B = ¬⟨x⟩B is only run by one parity locally. • AND. ⟨z⟩B = FAND (⟨x⟩B , ⟨y⟩B ) is achieved by a secure 2PC protocol using pre-computed boolean triples. [32] • OR: ⟨z⟩B = FOR (⟨x⟩B , ⟨y⟩B ) is achieved by x ∨ y = x ∧ y ⊕ (¬x ⊕ ¬y) using FAND . • Multiplexer. ⟨z⟩A = FMUX (⟨x⟩A , ⟨y⟩B ). If y is true then z = x else z = 0. It can be realized via two calls to FOT . [34] • Boolean share to arithmetic share. ⟨y⟩A = FB2A (⟨x⟩B ). It can implemented via one call to FOT [34]. • Most significant bit. ⟨y⟩B = FMSB (⟨x⟩A ). If x ≤ 0 then y is true/1 else y is false/0. This can be realized via FOT [34]. 3) Circuit-PSI: Private Set Intersection (PSI) allows two parties to securely compute the intersection X ∩ Y of their respective sets X and Y while keeping items non-intersection items private. Circuit-PSI [22]–[24], the functionality of which denotes as FCPSI , takes a step further by allowing computations on the intersection, denoted as f (X ∩Y ), without leaking any other information. Specifically, both parties use the same set of hash functions {h1 , h2 , ..., ha }, and the receiver maps X to a table containing (1 + ϵ)|X| (ϵ > 0, used for avoiding collisions) bins using Cuckoo hashing, while the sender maps Y using simple hashing. For Cuckoo hashing insertion, the receiver first checks whether ∃i ∈ [1, a] that the bin hi (x) is empty, where x ∈ X. If so, it stores x in one of the empty bins; otherwise, it randomly evicts the current item in bin hi (x) and then recursively tries to insert the evicted item. The final evicted item is placed in a stash if this process does not terminate after a certain number of trials. If ϵ and a are chosen properly, the stash can be removed [22]–[24]. For Simple hashing insertion, the sender hashes y ∈ Y to bins by all hi ; each bin may have multiple items. Both parties pad their tables with “fake entries” to the maximum bin size. There is exactly one bin to which both parties map each common item. PSI is then converted to private set membership

testing: Whether the item that the receiver places in a bin is among the items that are placed in this bin by the sender. Oblivious programmable pseudorandom function is employed to obtain the final intersection result in the form of boolean shares, which involves O(1) secure comparisons. Therefore, there are O(n) secure comparisons in circuit-PSI. The subsequent operations are applied to the output shares, the size is equal to the bin size, i.e., related to the record size of the receiver. Thus, the record size of the sender does not affect the description of the subsequent protocols, which indicates that the assumption of n0 = n1 = ... = n is reasonable. Although circuit-PSI enables secure computation of the function f over the intersection, it only supports symmetric functions that are oblivious to the order of the elements in the intersected set. 4) Secure Permutation: The secure permutation protocol enables two parties, P0 and P1 , to permute the input shares, ⟨x⟩, based on a permutation π defined by one of the parties. The output remains shared as ⟨y⟩. Two techniques can instantiate it: Homomorphic Encryption (HE) [35], [36] and Oblivious Switching Network (OSN) [25], [35] . HE-based approaches have a O(n) complexity but require costly asymmetric encryption. While OSN relies on efficient symmetric key operations and OT, but has a O(n log n) complexity. Motivated by the efficiency advantages it offers over the HEbased approaches, as reported in [25], we adopt the OSNbased Oblivious Extended Permutation (OEP) [25] as our baseline approach. The OEP is capable of handling the secure permutation problem with an extended permutation π, which allows for the replication or omission of elements. Formally, given N, M ∈ N+, N ≤ M , the permutation π is considered an extended permutation if, for every y ∈ [1, N ], there exists exactly one x ∈ [1, M ] such that π(x) = y. IV. P RIVACY- PRESERVING R ECORD S CREENING For simplicity, P0 and P1 are the two participants. A. Overview of Appraisal To realize the idea from Section II-E in a privacy-preserving manner, we proposed MPC-based PPRS, Appraisal. Fig 2 gives an example to illustrate the process: • Feature Engineering Module: Each party Pi locally preprocesses its dataset Vi to V̄i . To support schema-aware setting, derived attributes are generated empirically (Section. II-E2). To support the approximate match, one attribute is expanded to B band signatures via LSH (Section. IV-E2). For simplicity, we assume both V̄0 , V̄1 contains n records and m derived attributes (or Bm band signatures). • Circuit-PSI Module: It takes the derived attributes and identifies the matched ones (in the intersection) in a privacypreserving manner. The result is in boolean secret shares to ensure no information leakage of Vi . • Oblivious Feature Alignment (OFA): Similar to the plaintext idea in Section II-E, one instance of circuit-PSI will be invoked for each derived attribute. Due to the hashing operation in circuit-PSI, the attribute of the same records will be out-of-order. The OFA protocol addresses this issue

by employing the secure permutation technique with several optimizations. It ensures the elements corresponding to the same record are properly aligned for subsequent computations. • Score Function Module: It determines whether the record is linked or not obliviously, ultimately deriving the final collaboration value between two parties’ datasets. B. Circuit-PSI Module In a naı̈ve exact matching and schema-agnostic setting, PSI could easily handle. However, PSI can support neither approximate matching nor schema-aware setting without information leakage. Appraisal runs multiple circuit-PSI instances, each for one attribute (to support schema-aware) or one band (to support LSH bin for the approximate matching), and the privacy of the intermediate result can be preserved. Specifically, two parties proceed to carry out m (Bm for approximate matching) separate instances of the circuit-PSI protocol, with each instance aligning with a specific derived attribute (e.g., j-th attribute) from V̄0 and V̄1 . In an individual circuit-PSI instance, P0 (resp. P1 ) acts as the sender (resp. receiver), and inputs j-th attribute value V̄0 (resp. V̄1 ) of all records. It generates boolean shares ⟨qj ⟩B l for Pl , which indicates the presence of j-th derived attribute within the intersection set. Both the Cuckoo hash and simple hash can be conceptualized as permutation functions, denoted as π C and π S , respectively. It causes two problems: (i) misalignment of intersection results across attributes: the order of the ⟨qj ⟩B is determined by the Cuckoo hash, which is different for different attributes; (ii) the result of the duplicate item is missing: the hash operation maps duplicate attribute values to the same hash bin. Therefore, to align ⟨qj ⟩B of all the attributes, we need to −1 apply the extended permutation, πjC : [0, (1+ϵ)n) → [0, n), on ⟨qj ⟩B obliviously. The problem is not trivial due to the simple hash maps multiple records residing within the same bin, i.e., the order of records after circuit-PSI is not disclosed to P1 . A straightforward solution is to let P0 send the permutation π C to P1 . Nevertheless, this raises concerns regarding the potential information leakage related to V̄0 , as in Figure 3. By analyzing π C , P1 can infer the likelihood of a record matching. For example, if the attribute values of a record aligned together post-alignment, the probability of a match, Pr(Match), could be substantially elevated. C. Oblivious Feature Alignment (OFA) Protocol We abstract the above issue as a secure permutation prob−1 lem: P0 inputs the extended permutation πjC and the ⟨qj ⟩B 0 , while P1 inputs ⟨qj ⟩B 1 . The protocol provides each party the boolean shares post-permutation, denoted as ⟨q̄j ⟩B = πjc −1 (⟨qj ⟩B ). To solve this, we propose the Oblivious Feature Alignment (OFA) protocol, which tailors the OEP protocol [25] to meet our requirements. 1) OEP [25]: OEP is constructed via 2 basic protocols Oblivious Replication Network (ORN) and Oblivious Permutation Network (OPN). The former can obliviously replicate the adjacent elements within a vector, while the latter can obliviously reorder the elements of a vector by giving a

Fig. 2: An example of Appraisal. The records marked in orange right after the feature engineering module are linked. TABLE I: Output yi , yj with different selection bit b in replication 1-switch and permutation 1-swtich. The value marked in red can be removed in OFA for optimization.

Fig. 3: An example of the information leakage if P0 transmits the permutation π c to P1 . The bin value with the same color is from the same record.

Fig. 4: The structure of 1-switch. ri , rj , rk , rl are the random wire labels generated by the receiver, b is the selection bit from the sender, xi and xj are receiver’s input, yi and yj are the blinded output to the sender. bijection mapping (i.e., one-one and onto). Both OPN and ORN are built on the 1-switch, which replicates/permutes the adjacent input value for both parties based on a selection bit, as Fig. 4 shows. The difference is the input-output table (shown in I) and network topology of these 1-switches. OPN is implemented via a topology of Beneš Network containing n log n−n+1 permutation switch, while ORN is implemented by sequentially connecting n − 1 replication switch. For a given 1-switch, P1 assigns random blinded values ri , rj (resp. rk , rl ) to the input (resp. output) wires, and inputs xi and xj . They get the output shares of yi and yj , determined by the P0 ’s selection bit b. All the selection bits are derived from the extended permutation π : [1, N ] → [1, M ] via depthfirst search (DFS). A 1-switch is realized by one call of FOT . Let’s take replication 1-switch with b = 1, meaning to copy the value of yj from yi , as an example: First, P1 blinds its input A ⟨xi ⟩A 0 = xi ⊕ ri and ⟨xj ⟩0 = xj ⊕ rj , and sends them to P0 . Next, P1 creates table T as Table I shows. Then both parties

Switch Type

b

yi

yj

T[b, i]

T[b, j]

Permutation 1-switch

0 1

xi ⊕ rk xj ⊕ rk

xj ⊕ rl xi ⊕ rl

ri ⊕ r k rj ⊕ rk

rj ⊕ r l ri ⊕ rl

Replication 1-switch

0 1

xi ⊕ rk xi ⊕ rk

xj ⊕ rl xi ⊕ rl

ri ⊕ r k ri ⊕ r k

rj ⊕ r l ri ⊕ rl

invoke FOT , where P0 inputs b and P1 inputs T. Finally, P0 retrieves T[b] from FOT , and outputs yi = ⟨xi ⟩A 0 ⊕ T[b, i] = xi ⊕rk and yj = ⟨xi ⟩A ⊕T[b, j] = x ⊕r . Both are the shares i l 0 of replication value xi because P1 holds the other share rl and rk . This can be easily extended to the case where both parties input the shares: P1 replaces xi ,xj with its input shares, P0 XOR the result yl , yk with its reordered (permuted/replicated) input shares according to its b. Built on OPN and ORN, OEP (and the improved OFA) has three following phases, which take N real inputs with M − N dummy inputs as Fig. 5 shows: • Dummy-value Placement Phase (OPN): For each real input that is mapped to e different output positions according to π, it outputs real value followed by e − 1 dummy values, which serve as a placeholder for replication in the subsequent phase. • Replication Phase (ORN): Taking the output from the previous phase as input, it directly outputs the real input and replaces the dummy input with the real input that precedes it. • Permutation Phase (OPN). The output from the previous phase is taken and permuted to the final location under the guidance of π, which is in the same order as the P0 ’s records. 2) Optimizations in OFA: OEP supports the general extended permutation, we take a further step and tailor it for the −1 permutation of Cuckoo hash (πjC ) with three optimizations (shown in Fig. 5), which significantly improve the efficiency. • Optimization 1 - Dummy-value Placement Phase: The input of secure permutation containing ϵn redundant bins for privacy (see Section III-B3), e′ dummy inputs, and n − e′ real inputs. Thus, during deriving the selection bits from the permutation −1 πjC in DFS, we add a constraint that orders the ϵn redundant bins at the end of the output values. Both parties can now easily drop the last ϵn output values, reducing the 1-switch used for the subsequent two phases, ultimately decreasing the number of FOT from 2(1 + ϵ)n log((1 + ϵ)n) − (1 + ϵ)n + 1

Fig. 5: The workflow of Oblivious Feature Alignment (OFA) protocol. “*” represents a random fake entry, the attribute value marked in orange is the repeated input. P0 (resp. P1 ) inputs the value x0 (resp. x1 ) to circuit-PSI and gets the boolean shares result ⟨q⟩B indicates the intersection result, i.e., x0 ∩ x1 . The dummy placement phase reorders the dummy values “*” (resp. “VI, AL”) to the second bin right after the bin with “VI”, which will be used in replication later. It also permutes all other redundant bins to the bottom, which will be then dropped by both parties. The replication phase copies the boolean shares of dummy inputs from the boolean share represented “VI”. Finally, the permutation phase permutes all the bins to the order of P0 ’s records before input to circuit-PSI. The bins (i.e., boolean shares) with blue color are the input and output of each phase. The bins of the attribute values, State, are only for illustration and are not used in the actual protocol. to (1 + ϵ)n log((1 + ϵ)n) + n log n − (1 + ϵ)n + 1. • Optimization 2 - Replication Phase: We found that in replication 1-switch, the top output (yi ) is always equal to the top input (xi ) in Fig. 4, regardless of the selection bit. Therefore, P1 only needs to generate and send a partial table T[b, j] to FOT , omitting T[b, i] (marked in red in Table I) related to the top output wire (rk ). P1 can directly blind input xi with top output label rk instead of ri , i.e., yi′ = xi ⊕rk , and P0 can output yi = yi′ . Therefore, we halve the communication and computation cost in replication 1-switch. • Optimization 3 - Shares Type: OEP is designed for arithmetic shares, which typically requires a larger bits (e.g., 128 bits) in the circuit. By observing ⟨qj ⟩B are boolean shares, we replace all the random arithmetic numbers r (16 bytes) used in the 1-switch with random boolean values (one byte). Since these random values is used in FOT and T, we achieve a substantial 16× reduction in the communication cost. 3) Communication-efficient OFA: With the integration of the three aforementioned optimizations, we present our highly efficient OFA protocol. The workflow is shown in Fig. 5, and the functionality and detailed protocol are shown in Fig. 6 D. Score Function Module After executing OFA, all intersection results, ⟨q̄⟩B , across various attributes are aligned to match the original order of records in V0 . Then, Appraisal can determine whether each record is linked via a score function, and calculate the value of the collaboration between the two parties. 1) Scoring Function for Records: Appraisal accommodates various polynomial score functions, providing flexibility

in determining how records are linked. Below are two exemplary scoring models supported by Appraisal: • Simple linear model. In this model, a record is linked iff all its attributes are matched. The matching result for the ith record can V be determined using FAND across all attribute ⟨d⟩B [i] = j ⟨q̄j ⟩B [i], where j iterates over all attributes. • General linear/logistic regression model. A linear/logistic regression is applied to score the records. It assigns different attributes different weights, i.e., the more selective an attribute is, the more it contributes to the matching decision. A record is determined to be linked by comparing the score with a predetermined threshold t. The threshold and the weights can be decided by an offline machine learning algorithm trained on public/private data. The specific workflow shows as follows. (i) Weight Sharing: P0 generates the arithmetic shares of the weights, and sends one share to P1 ; (ii) Score Calculation: Both the score for the i-th record as ⟨s⟩A [i] = P parties compute e A B n A B j (FMUX (⟨wj ⟩ , ⟨q̄j ⟩ [i]) + FMUX (⟨wj ⟩ , ¬⟨q̄j ⟩ [i])), e where wj denotes the weight of the j-th attribute when it is matched, and wjn for unmatched; (iii) Decision Making: The linkage decision for the i-th record is determined by comparing the score with the threshold, ⟨d⟩B [i] = FMSB (⟨s⟩A [i]−⟨t⟩A ). The former model offers a faster method, while the latter is more fine-grained to consider varying importances of different attributes. Both models are executed securely through MPC. 2) Score Function for Collaboration Value: The collaboration value c is a statistical aggregated value over the results of linked records. Finding an appropriate scoring function is an open question and depends on the specific applications. This is orthogonal to Appraisal, which focuses on providing

Functionality FOFA

Functionality FAppraisal

P0 ’s Input: Boolean shares ⟨q⟩B 0 of size (1 + ϵ)n, the extended permutation mapping π : [0, (1+ϵ)n) → [0, n) P1 ’s Input: Boolean shares ⟨q⟩B 1 of size (1 + ϵ)n Output: Pl (l = 0/1) learns ⟨q̄⟩B l of size n, s.t. q̄ = π(q).

P0 ’s Input: Database V0 with n records. P1 ’s Input: Database V1 with n records. Public Input: B, R in LSH, threshold t in score function for records. Output: Pl (l = 0/1) gets the collaboration value ⟨c⟩B l .

Protocol ΠOFA ▷ P0 derives the selection bits b of π and learns a random encoding of the whole network with b. 1: Pl : constructs the network of three phases via 1-switch. 2: P0 : derives b of these switches via DFS. 3: for network of dummy-value placement phase (OPN), replication phase (ORN), permutation phase (OPN) do 4: for each wire i of the network do 5: P1 : generates a random bit ri ←$ {0, 1}. 6: for each switch i of the network do 7: P1 : creates and sends table T as Table I to FOT . 8: P0 : sends b[i] to FOT and gets T[b[i]]. ▷ P1 blinds its input shares

9: P1 : sends yi′ = ⟨q⟩B 1 [i] ⊕ ri to P0 for all input wire wi .

▷ P0 evaluates the random encoding of the whole network on P1 ’s blinded inputs. 10: P0 : yi = yi′ ⊕ ⟨qi ⟩B 0 = q[i] ⊕ ri for all input wire wi . 11: In topological order, for each switch with selection bit b, input wires wi , wj and output wires wk , wl , P0 does: 12: if switch is a replication switch then 13: if b = 0 then yk = yi , yl = yj ⊕ T[b, j] 14: else yk = yi , yl = yi ⊕ T[b, j] 15: if switch is a permutation switch then 16: if b = 0 then yk = yi ⊕ T[b, i], yl = yj ⊕ T[b, j] 17: else yk = yj ⊕ T[b, j], yl = yi ⊕ T[b, i] ▷ P0 unblinds and retrieves the output 18: P0 : blinds yk with its output shares for each output switch h(0 ≤ h < n/2) with output wires wk , wl : B B ⟨q̄⟩B 0 [2h] = yk ⊕ π(⟨q⟩0 )[2h], ⟨q̄⟩0 [2h + 1] = yl ⊕ B π(⟨q⟩0 )[2h + 1]. 19: P1 : outputs the randoms rk , rl of output wires wk , wl in the network of permutation phase, ⟨q̄⟩B 1 [2h] = rk , ⟨q̄⟩B 1 [2h + 1] = rl for the h-th output switch. Fig. 6: Ideal functionality and protocol of OFA a flexible framework to support different scoring functions. For simplicity, we adopt cardinality counting for scoring P collaboration value, i.e., ⟨c⟩A = i FB2A (⟨d⟩B [i]). E. Practical Consideration 1) Handling Missing Value: In many applications, data is incomplete, i.e., some attribute values are missing. However, the output of circuit-PSI is restricted to only two cases: match or unmatch. This causes the attribute with the missing value to eventually be deemed a match, resulting in an elevated false positive rate. Note that the receiver (P0 ) in circuit-PSI is aware of which values are missing, as it inserts the data using

Protocol ΠAppraisal ▷ Feature Engineering Module 1: Pl locally preprocess Vl to generate V̄l , which contains

n records and Bm derived attributes. Specifically, it can derive new attributes via concatenate attributes to support schema-aware (Section. II-E2), or can apply LSH to expand an attribute to multiple band signatures for approximate matching (Section. IV-E2). ▷ Circuit-PSI 2: for each derived attribute j in V̄l do 3: P0 takes role of receiver, P1 takes role of sender, invokes FCPSI , Pl gets the Boolean shares indicates the presence of the attribute value in the intersection b 1 ⟨qj ⟩B l = FCPSI ({V̄ [:, j]}, {V̄ [:, j]}), P0 also gets C the mapping of Cuckoo hash πj . ▷ Oblivious Feature Alignment 4: for each derived attribute j in V̄l do 5: Both parties jointly invoke FOFA and Pl gets

the aligned attribute intersection result ⟨q̄j ⟩B l = C −1 FOFA ({⟨q⟩B }, {⟨q⟩B 0 , πj 1 })

▷ Score Function Module

6: for each record i do 7: Pl calculates the decision of linkage ⟨d⟩B l [i] accord-

ing to Section IV-D1 via FMUX P, FMSB , FAND B i FB2A (⟨d⟩l )[i]

8: Pl gets collaboration value ⟨c⟩A l =

Fig. 7: Ideal functionality and protocol of Appraisal Cuckoo hashing and has access to π C . It can adjust the score of the records having the missing attribute value. Taking the linear/logistic model as an example, we denote the weight for missing values as wjm for attribute j. After both parties have computed ⟨s⟩A , if attribute value V̄[i, j] of record i is absent, A m P0 can adjust the score via ⟨s⟩A 0 [i] = ⟨s⟩0 [i] + wj . 2) Supporting Approximate Matching: Section II-E introduces to support the approximate matching via LSH. To incorporate it in Appraisal, we modify the following: (i) P0 and P1 synchronize parameters B, R; (ii) They extract q-grams for each attribute values; (iii) Each party creates a new V̄ by expanding one attribute to B band signatures (detailed in Section II-E), increasing the number of derived attributes from m to Bm; (iv) Both parties invoke the circuit-PSI per attribute, i.e., Bm instances of circuit-PSI are executed in total; (v) OFA is used to align the intersection result of all derived attributes. (vi) In the score function module, the original j-th attribute (in V) of record i is linked iff one of its BWderived attributes (j+1)B−1 (band signatures) is matched ⟨q̄′j ⟩B [i] = k=j·B ⟨q̄k ⟩[i],

which can be securely realized via FOR . And the decision d of the record is linked is calculated by ⟨q̄′j ⟩B . F. Putting All Things Together By assembling all the modules, we get Appraisal, the ideal functionality and the protocol is shown in Fig. 7. V. A NALYSIS

Proof sketch. ΠAppraisal consists of mB FCPSI , mB FOFA , Score Function including FMUX , FMSB , FAND , and FB2A . All of these functionalities are secure 2PC FOT hybrid protocols in the semi-honest model. Thus, we can construct a simulator for Appraisal using the simulators of FCPSI , FOFA , FMUX , FMSB , FAND and FB2A , which are similar to the proof of Theorem V.1 and conclude that Appraisal is also secure given Theorem III.1.

A. Security Analysis In this section, we provide sketches of proof that OFA and Appraisal are secure according to Definition III.1. Theorem V.1. ΠOFA is a secure protocol under FOT -hybrid. Proof. Case 1: P0 is corrupted. The simulator S constructs the network of three phases via 1-switch and interacts with P0 as follows. Step 1. S assigns random bits for each wire in the network of the dummy-value placement phase and constructs the table T of each permutation switch. Then, S works as sender in FOT . When P0 sends selection bit b to FOT , S sends T to FOT . Step 2. S assigns random bits for each wire in the network of the replication phase and constructs the table T of each replication switch. Then, S works as sender in FOT . When P0 sends selection bit b to FOT , S sends T to FOT . Step 3. S assigns random bits of each wire in the network of the permutation phase and constructs the table T of each permutation switch. Then, S works as sender in FOT . When P0 sends selection bit b to FOT , S sends T to FOT . Step 4. S XOR the input vector ⟨q⟩B 1 with random bits in Step 1 and sends to P0 , and outputs the random bits of output wires in the permutation phase (OPN). To prove that this simulation is indistinguishable from the real protocol, we consider the following hybrid worlds. Hybrid0 The same as the real protocol. Hybrid1 Each permutation switch in dummy-value placement phase (Line 4– 8, ΠOFA ) is replaced by FOT Hybrid2 Each replication switch in replication phase (Line 4– 8, ΠOFA ) is replaced by FOT Hybrid3 Each permutation switch in permutation phase (Line 4– 8, ΠOFA ) is replaced by FOT . Hybrid4 The execution of S in step 4 is identical to Line 9– 19 in ΠOFA . Note that Hybrid1 , Hybrid2 and Hybrid3 is computationally indistinguishable from real protocol as FOT is secure. Therefore, the simulation (Hybrid4 ) is computationally indistinguishable from the view of real protocol (Hybrid0 ). Case 2: P1 is corrupted. The simulator S constructs the network of three phases via 1-switch and derives b of these switches via DFS. Then, the interaction between S and P1 is similar to the situation when P0 is corrupted, except S works as receiver in FOT . To sum up, in both cases, The FOT -hybrid OFA protocol is secure in the semi-honest model. Theorem V.2. The FOT -hybrid ΠAppraisal is secure.

B. Performance Analysis 1) Appraisal: The analysis of time and communication complexity is as follows: • Feature Engineering. It runs locally without any communication. The time complexity is O(nm) for exact matching and O(Bnm) for approximate matching. • Circuit-PSI. The time and communication complexity of the protocol is O(n). For the schema-aware and approximate matching setting, it is O(nmB). • OFA. The time and communication complexity per derived attribute (and/or band signature) is O(n log n) . • Score Function. The time and communication complexity per derived attribute (and/or band signature) is O(n). In total, the time and communication complexity of Appraisal is O(mn log n), or it is O(Bmn log n) for approximate matching. Moreover, only circuit-PSI involves secure comparison, which is O(Bmn). 2) Screening-then-Linkage: The time for the pure PPRL scheme is N · tPPRL where tPPRL is the time for executing the PPRL. The time for Screening-then-Linkage is N ·tPPRS + αN · tPPRL where tPPRS is the time for executing the PPRS and α is the ratio of the parties with high collaboration value. VI. E VALUATION In this section, we first outline the implementation. Then, we present the evaluation setup, and show the effectiveness and efficiency of Appraisal and Screening-then-Linkage framework. A. Implementation We conducted data extraction, cleaning, and ground truth determination using Python 3 and implemented Appraisal system in C++ using the following libraries: the Feature Engineering and Score Function modules were based on Cryptflow2 [34], while the FOT was sourced from Cheetah [37]. The Circuit-PSI module was adapted from [23]. For the OFA protocol, we modified the OSN code from [38] and [39]. We set the computational security parameter to λ = 128 and the statistical security parameter to σ = 40 For the stashless circuit-PSI, the smaller ϵ, the possibility of collisions will increase; the larger ϵ, the cost of both Circuit-PSI and OFA will increase. We use ϵ = 0.27 and a = 3 [24] to achieve the balance between security and performance. B. Evaluation Setup We conducted our evaluations on two instances, which play the roles of P0 and P1 respectively. Both instances are equipped with 10 cores of 2.5GHz Intel Xeon Platinum 8255C

TABLE II: The description of the evaluation datasets. Dataset

# of records

iDash500K iDash1M DBLP/ACM BNB/TPL

500K/500K 1,000K/1,000K 2,616/2,294 3,565K/1,443K

Duplication (%) for both data 10%/10% 10%/10% 85%/95% 17.5%/39.5%

Matching Mode Exact Exact Approximate Mixed

CPU and 128GB of memory. To ensure fairness, we matched the number of cores utilized in both instances to the number of threads used in Appraisal, choosing between 1 or 4 threads. Our evaluation covers two network conditions: (i) Local Area Network (LAN): bandwidth of 1Gbps and an approximate latency (ping time) of 2ms; (ii) Wide Area Network (WAN): we use the tc command to artificially constrain the bandwidth to 100Mbps and set the ping time to 100ms. C. Evaluation on Appraisal 1) Datasets: The evaluation datasets are shown in Table II. • iDash500K/1M [40]: iDash, a competition dedicated to addressing privacy and security challenges in genome data analysis, introduced a task in 2022 to tackle secure record linkage for electronic health records. Each record encompassed 9 attributes: Social Security Number (SSN), gender, first name, last name, birth date, phone number, address, state, and email. The SSN served as a deterministic key, whereas the other attributes played a supplementary role in record matching due to the potential missing in the SSN. All attributes were hashed using SHA-256, therefore, exact matching was required for comparison. iDash supplied two datasets, each consisting of two subsets, A and B, with each subset containing 500K records. We merged the two 500K datasets to create a larger dataset of 1M records in each subset. In evaluation, we adopt a logistic model in the Score Function module and evaluate the effectiveness (accuracy) with 5-fold cross validation. When evaluating the efficiency (runtime), we use all records. • DBLP/ACM [41]: This dataset, sourced from DBLP and ACM, contains bibliographic data with 2,615 and 2,293 records, respectively [42]. It includes 4 attributes: title, authors, venue, and year. Variations in text sequencing and abbreviations may occur within a single record across the two datasets, necessitating the use of approximate matching. In evaluation, we adopt the simple linear model in Score Function module. We set B = 25, 18 for schema-aware and schema-agnostic modes, respectively, in approximate matching, implying that the number of attributes expands to 50 and 18. • BNB/TPL: The British National Bibliography (BNB) [43], includes a catalog of books published in the UK or the Republic of Ireland, and the Toronto Public Library (TPL) [44], a collection of published books in the Toronto Public Library, serve as the datasets for this study. We have extracted three fields—ISBN, author, and title—from each dataset, eliminating any record missing all three. To establish the ground truth, we follow the methodology outlined in SFour [18]. ISBN can serve as a deterministic key, however, it is frequently missing. For records without ISBNs, we adopt the Levenshtein distance for the author and title fields, setting a similarity threshold of 80%. As a result, around 17.5% of BNB records and 39.5% of

Fig. 8: Accuracy across various datasets, with P0 utilizing one set of data from a given pair. TABLE III: Runtime of Appraisal with 1/4 threads in seconds. dataset iDash500K iDash1M DBLP ACM BNB TPL

Schema-aware LAN WAN 610/155 675/248 1274/386 1331/492 21/8 217/66 21/7 213/62 5032/1710 5402/2025 20165/9328 21317/9934

Schema-agnostic LAN WAN / / / / 8/3 85/27 8/3 83/26 2664/846 2861/990 10558/4559 11281/4855

TPL records are being linked. Notably, around 57.1% of these linked pairs can be matched through exact matching based on ISBN, consistent with findings in [18]. Our evaluation employs mixed matching modes: exact matching for the ISBN, and fuzzy matching for the author and title fields. In evaluation, we adopt the simple linear model in Score Function module. We set B = 8 for both schema-aware and schema-agnostic modes, extending the number of attributes to 17 and 9, respectively. 2) Evaluation Metrics: To conduct a detailed analysis of Appraisal, we temporarily shift our system’s objective to identifying whether a record is linked, rather than determining the collaboration value. This can be achieved by recovering ⟨d⟩B within the Score Function module. For effectiveness evaluation, we use metrics: Balanced Accuracy (BAC) = 0.5× P TN TP TP ( T PT+F N + T N +F P ); Precision = T P +F P ; Recall = T P +F N where T P , T N , F P , and F N stand for true positives, true negatives, false positives, and false negatives, respectively. In terms of efficiency, we measure its runtime, including both online and offline phases, under LAN and WAN. 3) Results: Presented in Fig. 8, the results are based on the dataset used by P0 and alternating between the two datasets in a pair. This demonstrates that Appraisal can achieve high accuracy when configured with appropriate parameters. The runtimes of Appraisal with single-threaded and fourthreaded configurations are displayed in Table III. These results confirm Appraisal’s capability to efficiently process records at the scale of millions. Additionally, as the record count increases, the relative time difference between LAN and WAN scenarios decreases, indicating that the communication cost is no longer the primary bottleneck in the OFA protocol. 4) Compare to Related Works: In this section, we limit the number of threads to one and set the network condition to

TABLE IV: Estimated runtime (in hours) of PPRL and PPRS. Dataset Ours [45] [20] [21](ϵ = 0.1) [21](ϵ = 0.4) [21](ϵ = 1.6)

iDash500K 0.2 4166.7 33.8 1456.8 154.6 36.0

iDash1M 0.4 16666.7 71.1 3943.7 323.6 75.6

DBLP/ACM 0.002/0.002 0.1 0.5 559.3 39.2 3.6

BNB/TPL 0.7 / 2.9 34707.0 481.3 436879.4 31034.8 3021.3

TABLE V: The maximum α that Screening-the-Linkage framework has an advantage over the pure PPRL framework. Dataset [45] [20] [21](ϵ = 0.1) [21](ϵ = 0.4) [21](ϵ = 1.6)

iDash500K 1.0 0.995 1.0 0.999 0.995

iDash1M 1.0 0.995 1.0 0.999 0.995

DBLP/ACM 0.980/0.980 0.995/0.995 1.0/1.0 1.0/1.0 0.999/0.999

BNB/TPL 1.0/1.0 0.998/0.994 1.0/1.0 1.0/1.0 1.0/0.999

LAN for a fair comparison because some selected works either do not support multi-threading or have not implemented the network communication module in their open-source codes. Thus, we estimate their performance based on both their codes (if they exist) and the results reported in their papers. We identify that SFour [18] is PPRS due to it outputs whether the record is linked instead of the linked pair. Compared to it, Appraisal demonstrates superior performance in terms of both effectiveness and efficiency. While SFour achieves slightly less than 90% accuracy on the BNB/TPL dataset, Appraisal consistently maintains an accuracy rate exceeding 95% across various settings. Furthermore, SFour takes approximately 385 minutes (77 minutes online and 308 minutes offline) to process 4096 records in a LAN environment. In contrast, Appraisal can efficiently handle up to 3.5 million records, as shown with the TPL dataset, in roughly 336 minutes under the same network conditions. We also compare with the SOTAs on PPRL, BF-based (Bloom filter) PPRL [45] and MPC-based PPRL [20], [21]. • BF-based PPRL: It comprises three components: diffusion, encoding, and linking. The diffusion and encoding processes are performed once per dataset, while the linking process is executed for every pair of records, resulting in time complexity of O(n2 ). According to the reported results and our measurements using the available source code [46], linking two records is the most consuming part, which takes around 6 × 10−5 ms. • MPC-based PPRL: This approach involves blocking records into bins using LSH, adding dummy elements in bins for privacy, and finally comparing the records in the respective bins from both parties. The difference lies: (i) He et al. leverages differential privacy padding, while Wei et al. [20] padding in a strategy of frequency smoothing; (ii) He et al. adopts one-to-one secure comparison protocol while Wei et al. adopts private join protocol (many-to-many secure comparison protocol). Nevertheless, the cost is primarily determined by the number of secure pairwise comparisons. Our implementation of the comparison protocol takes around 0.13ms per comparison. Based on the analysis in [20], the expected number of comparisons is approximately Bℓ(n/ℓ + η)2 for both works (definitions are in Section II-C). η is different for two works, it is related to the different privacy parameter ϵ in He et al.,

TABLE VI: Communication cost (MB) of OEP, OEP with optimization 1, OEP with optimization 1+2 and OFA # of records OEP OEP+Opt 1 OEP+Opt 1+2 OFA

100 0.3 0.3 0.3 0.2

1K 1.1 1.0 1.0 0.3

10K 11.6 10.3 10.0 0.9

100K 136.8 121.4 118.4 8.4

500K 799.7 695.2 680.0 46.7

1M 1676.9 1459.7 1429.1 97.8

while is n/2ℓ in Wei et al.. The specific parameters and settings are detailed in the original text. For the iDash500K, iDash1M, DBLP/ACM, and BNB/TPL datasets, we tailored the parameters, B = 32, to ensure the accuracy rate of their approaches is greater than 90%. For iDash datasets, we estimate the runtime of all works under the schema-aware setting, and for other datasets, we adopt the schema-agnostic setting. The results are presented in Table IV. In the largest dataset BNB/TPL, the performance of Appraisal is exceptionally notable. Compared to the BF-based and MPC-based PPRL, Appraisal achieves a speedup factor of at least 11968× and 165×, respectively. These comparisons underscore the significant efficiency gains made possible by Appraisal, particularly when handling extensive datasets. D. Evaluation on Screening-then-Linkage In this section, we compare the Screening-then-Linkage framework with the framework solely based on PPRL. We also use the same datasets, parameters, and environment for both PPRL and Appraisal as Section VI-C4. In our setup, P0 utilizes one dataset from a pair, while P1 , ..., PN employs the other dataset in that pair. We introduce α, representing the proportion of parties possessing a high collaboration value (c > threshold). To demonstrate the efficiency advantages of the Screening-then-Linkage framework over pure PPRL framework, we compute the ratio of runtime between them, denoted as γ. Specifically, the runtime of the Screening-thenLinkage framework is T1 = N · tPPRS + α · N · tPPRL . Correspondingly, the running time of the pure PPRL framework is T2 = N · tPPRL . Thus, γ = T1 /T2 = tPPRS /tPPRL + α. We determine the maximum value of α for which the Screening-then-Linkage has an advantage over the pure PPRL framework by solving γ ≥ 1. The results, shown in Table V, indicate that the maximum α is larger than 0.98 in all cases. This suggests that when nearly all parties are highvalue participants for P0 , pure PPRL is more advantageous; otherwise Screening-then-Linkage is better. E. Component Evaluation: OFA protocol We evaluate the performance of the most critical module: OFA and compare it to the OEP with 2 instances, P0 and P1 . A variety of datasets are synthesized, each containing a single attribute of random boolean shares. The number of records in these datasets varies from 100 to 1M. Additionally, we generate random extended permutation π for P0 . Figure 9 presents the runtime results for OEP, optimizations and the OFA protocols. In a LAN setting, the OFA protocol demonstrates a slight performance advantage over the OEP. However, the distinction becomes more pronounced in a WAN

(a) LAN, 1 thread

(b) LAN, 4 threads

(c) WAN, 1 thread

(d) WAN, 4 threads

Fig. 9: Running time (in seconds) of OEP, optimization 1, optimization 1+2, and OFA with 1 or 4 threads.

environment, where the OFA significantly outperforms the OEP. This improvement in performance is attributed to the reduced communication cost associated with the OFA, as detailed in Table VI. The efficiency gains become increasingly evident as the dataset size expands. For a dataset comprising 1M records, the runtime of OFA is 4× faster than that of the OEP with 4 threads, the communication cost of the OFA is a mere 6% of the OEP’s, highlighting the substantial efficiency improvements achieved by the OFA protocol. Moreover, optimization 1 and 2 under LAN contribute almost equally as they do under WAN, and optimization 3 contributes more under WAN. It indicates that optimization 3 reduces the communication cost significantly, and the other two optimizations reduce both communication and computation costs. VII. R ELATED W ORK There are considerable works dedicated to achieving PPRL. All-Pairwise Comparisons [21] is a straightforward and accurate approach. It involves secure comparison between each pair of records in the Cartesian product of the two databases. However, due to its quadratic time complexity, it becomes inefficient for large-scale datasets. As a result, researchers have introduced various solutions to strike a balance between security, effectiveness, and efficiency. These approaches involve three primary techniques, including Differential Privacy (DP), Bloom Filter (BF), and Multi-party Computation (MPC). MPC-based approaches, while provably secure and accurate, are generally inefficient. Some works [14], [15] rely on computationally inefficient homomorphic encryption, while others [47] are based on communicationally inefficient garbled circuits. Among them, the PSI-based approach [19] achieves the best efficiency and can support more than 1M records. However, it can only handle the exact match in schemaagnositc scenario. Adir et al. [19] tries to solve the approximate match by directly running PSI on the elements extracted from LSH on each record. However, this leaks the frequency of each q-gram, and can inadvertently leak information about the attributes of the records. Moreover, it cannot support the schema-aware mode. In our work, we prevent such information leakage through the use of circuit-PSI. Wei et al. [20] leverages LSH for blocking and private join protocol for matching. It achieves the best performance in the MPC-based approach but still needs 1 hour for 40K records. DP-based works [48]–[50]

could improve efficiency. However, He et al. [21] demonstrate that these approaches may leak aggregate properties of the input datasets to both parties and propose a more secure solution based on the combination of DP and MPC. Rao et al. [51] achieves the best performance in the DP setting but relies on a trusted third party. BF-based works [52], [53] are often efficient. However, they are vulnerable to various attacks [54]– [57]. Moreover, the solutions [58]–[60] lack formal security analysis. A recent work [45] enhances the security of BF by adding a diffusion layer, providing a rigorous security analysis. But the complexity is O(n2 ) which is hard to scale. For further details, we direct readers to refer [17], [61], [62]. Some recent works are highly relevant to PPRS. SFour et al. [18] proposes using MPC-based sorting with sliding window comparison to enable the output of which records are linked. However, the cryptographic primitives used are time-consuming, resulting in the entire system taking more than 1 hour for only 4096 records. Along a similar line of work, we systematically define the PPRS framework. Unlike their approaches, our solution achieves O(n log n) complexity based on optimized lightweight cryptographic building blocks, thereby supporting million-level records. VIII. C ONCLUSION In this work, we point out the need for efficient collaboration value identification in the data federation market and introduce the Screening-then-Linkage framework to address this. The superior performance of Appraisal depends on circuit-PSI and our proposed OFA protocol. With a thorough security analysis, Appraisal is demonstrated to leak no information beyond the data collaboration value. Our evaluations show that Appraisal only needs about 20 minutes for a 1M dataset, which is 165× faster than the SOTA PPRL. In our future work, we aim to address more practical considerations related to the deployment in data markets, including: supporting more advanced approximate matching methods with circuit-PSI instead of expanding the records; implementing more efficient PPRS based on other privacy-preserving techniques such as DP and BF; analyzing the appropriate setting of parameters to avoid rare cases where the attribute of P0 is linked, but the linked attributes of P1 are from different records, leading to the failure of record screening; integrating data pricing methods with our Screening-then-Linkage framework and etc.

R EFERENCES [1] A. Asudeh and F. Nargesian, “Towards distribution-aware query answering in data markets,” Proceedings of the VLDB Endowment, vol. 15, no. 11, pp. 3137–3144, 2022. [2] P. Wang, Y. He, R. Shea, J. Wang, and E. Wu, “Deeper: A data enrichment system powered by deep web,” in Proceedings of the 2018 International Conference on Management of Data, 2018, pp. 1801–1804. [3] S. Hardy, W. Henecka, H. Ivey-Law, R. Nock, G. Patrini, G. Smith, and B. Thorne, “Private federated learning on vertically partitioned data via entity resolution and additively homomorphic encryption,” arXiv preprint arXiv:1711.10677, 2017. [4] R. Nock, S. Hardy, W. Henecka, H. Ivey-Law, J. Nabaglo, G. Patrini, G. Smith, and B. Thorne, “The impact of record linkage on learning from feature partitioned data,” in International Conference on Machine Learning. PMLR, 2021, pp. 8216–8226. [5] Fincom, “Fincom, modernizing banking technologies - real time aml sanctions screening & entity resolution,” 2016, available at: https://fincom.co (2025). [6] C. E. Kuehni, C. S. Rueegg, G. Michel, C. E. Rebholz, M.-P. F. Strippoli, F. K. Niggli, M. Egger, N. X. von der Weid, and S. P. O. G. (SPOG), “Cohort profile: the swiss childhood cancer survivor study,” International journal of epidemiology, vol. 41, no. 6, pp. 1553–1564, 2012. [7] Datavant, “Datavant match: High accuracy, fit-for-purpose record linkage for any research need,” 2023, available at: https://datavant.com/resources/product-sheet/matching-patient-recordswith-datavant (2025). [8] Amazon, “Amazon publisher service,” 2024, available at: https://aps.amazon.com/aps/index.html (2025). [9] Amazon, “Unlock data insights across multi-party datasets using aws entity resolution on aws clean rooms without sharing underlying data,” 2024, available at: https://aws.amazon.com/blogs/industries/unlockdata-insights-across-multi-party-datasets-using-aws-entity-resolutionon-aws-clean-rooms-without-sharing-underlying-data (2025). [10] Datavant, “Datavant - a data platform company for healthcare,” 2025, available at: https://www.datavant.com (2025). [11] Datavant, “Datavant connect: Linkage solutions,” 2025, available at: https://www.datavant.com/products/connect-linkage (2025). [12] Datavant, “Datavant - data and analytics thought leader: Paul petraro, boehringer ingelheim,” 2022, available at: https://www.datavant.com/real-world-data-rwd/data-analytics-thoughtleader-series-paul-petraro-boehringer-ingelheim (2025). [13] N. Wu, D. Vatsalan, M. A. Kâafar, and S. K. Ramesh, “Privacypreserving record linkage for cardinality counting,” in Proceedings of the 2023 ACM Asia Conference on Computer and Communications Security, ASIA CCS 2023, Melbourne, VIC, Australia, July 10-14, 2023. ACM, 2023, pp. 53–64. [14] K.-S. Wong and M. H. Kim, “Privacy-preserving similarity coefficients for binary data,” Computers & Mathematics with Applications, vol. 65, no. 9, pp. 1280–1290, 2013. [15] A. Essex, “Secure approximate string matching for privacy-preserving record linkage,” IEEE transactions on information forensics and security, vol. 14, no. 10, pp. 2623–2632, 2019. [16] C. Phua, K. Smith-Miles, V. Lee, and R. Gayler, “Resilient identity crime detection,” IEEE transactions on knowledge and data engineering, vol. 24, no. 3, pp. 533–546, 2010. [17] A. Gkoulalas-Divanis, D. Vatsalan, D. Karapiperis, and M. Kantarcioglu, “Modern privacy-preserving record linkage techniques: An overview,” IEEE Transactions on Information Forensics and Security, vol. 16, pp. 4966–4987, 2021. [18] B. Khurram and F. Kerschbaum, “Sfour: a protocol for cryptographically secure record linkage at scale,” in 2020 IEEE 36th International Conference on Data Engineering (ICDE). IEEE, 2020, pp. 277–288. [19] 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 Applied Cryptography and Network Security Workshops: ACNS 2022 Satellite Workshops, AIBlock, AIHWS, AIoTS, CIMSS, Cloud S&P, SCI, SecMT, SiMLA, Rome, Italy, June 20– 23, 2022, Proceedings. Springer, 2022, pp. 398–424. [20] R. Wei and F. Kerschbaum, “Cryptographically secure private record linkage using locality-sensitive hashing,” Proceedings of the VLDB Endowment, vol. 17, no. 2, pp. 79–91, 2023.

[21] X. He, A. Machanavajjhala, C. Flynn, and D. Srivastava, “Composing differential privacy and secure computation: A case study on scaling private record linkage,” in Proceedings of the 2017 ACM SIGSAC conference on computer and communications security, 2017, pp. 1389– 1406. [22] B. Pinkas, T. Schneider, O. Tkachenko, and A. Yanai, “Efficient circuitbased psi with linear communication,” in Advances in Cryptology– EUROCRYPT 2019: 38th Annual International Conference on the Theory and Applications of Cryptographic Techniques, Darmstadt, Germany, May 19–23, 2019, Proceedings, Part III 38. Springer, 2019, pp. 122–153. [23] N. Chandran, D. Gupta, and A. Shah, “Circuit-psi with linear complexity via relaxed batch opprf,” Proceedings on Privacy Enhancing Technologies, no. 1, pp. 353–372, 2022. [24] P. Rindal and P. Schoppmann, “Vole-psi: fast oprf and circuit-psi from vector-ole,” in Advances in Cryptology–EUROCRYPT 2021: 40th Annual International Conference on the Theory and Applications of Cryptographic Techniques, Zagreb, Croatia, October 17–21, 2021, Proceedings, Part II. Springer, 2021, pp. 901–930. [25] P. Mohassel and S. Sadeghian, “How to hide circuits in mpc an efficient framework for private function evaluation,” in Advances in Cryptology– EUROCRYPT 2013: 32nd Annual International Conference on the Theory and Applications of Cryptographic Techniques, Athens, Greece, May 26-30, 2013. Proceedings 32. Springer, 2013, pp. 557–574. [26] G. Papadakis, V. Efthymiou, E. Thanos, O. Hassanzadeh, and P. Christen, “An analysis of one-to-one matching algorithms for entity resolution,” The VLDB Journal, vol. 32, no. 6, pp. 1369–1400, 2023. [27] G. Papadakis, M. Fisichella, F. Schoger, G. Mandilaras, N. Augsten, and W. Nejdl, “Benchmarking filtering techniques for entity resolution,” in 2023 IEEE 39th International Conference on Data Engineering (ICDE). IEEE, 2023. [28] P. Indyk and R. Motwani, “Approximate nearest neighbors: towards removing the curse of dimensionality,” in Proceedings of the thirtieth annual ACM symposium on Theory of computing, 1998, pp. 604–613. [29] A. Andoni, P. Indyk, T. Laarhoven, I. Razenshteyn, and L. Schmidt, “Practical and optimal lsh for angular distance,” Advances in neural information processing systems, vol. 28, 2015. [30] O. Goldreich, The Foundations of Cryptography - Volume 2: Basic Applications. Cambridge University Press, 2004. [31] M. RABIN, “How to exchange secrets by oblivious transfer,” Tech. Memo TR-81, Aiken Computation Laboratory, Harvard University, 1981. [32] D. Demmler, T. Schneider, and M. Zohner, “Aby-a framework for efficient mixed-protocol secure two-party computation.” in NDSS, 2015. [33] D. Beaver, “Efficient multiparty protocols using circuit randomization,” in Advances in Cryptology—CRYPTO’91: Proceedings 11. Springer, 1992, pp. 420–432. [34] D. Rathee, M. Rathee, N. Kumar, N. Chandran, D. Gupta, A. Rastogi, and R. Sharma, “Cryptflow2: Practical 2-party secure inference,” in Proceedings of the 2020 ACM SIGSAC Conference on Computer and Communications Security, 2020, pp. 325–342. [35] M. Chase, E. Ghosh, and O. Poburinnaya, “Secret-shared shuffle,” in Advances in Cryptology–ASIACRYPT 2020: 26th International Conference on the Theory and Application of Cryptology and Information Security, Daejeon, South Korea, December 7–11, 2020, Proceedings, Part III 26. Springer, 2020, pp. 342–372. [36] W. Fang, D. Zhao, J. Tan, C. Chen, C. Yu, L. Wang, L. Wang, J. Zhou, and B. Zhang, “Large-scale secure xgb for vertical federated learning,” in Proceedings of the 30th ACM International Conference on Information & Knowledge Management, 2021, pp. 443–452. [37] Z. Huang, W.-j. Lu, C. Hong, and J. Ding, “Cheetah: Lean and fast secure {two-party} deep neural network inference,” in 31st USENIX Security Symposium (USENIX Security 22), 2022, pp. 809–826. [38] Y. Jia, S.-F. Sun, H.-S. Zhou, J. Du, and D. Gu, “Shuffle-based private set union: Faster and more secure,” in 31st USENIX Security Symposium (USENIX Security 22), 2022, pp. 2947–2964. [39] G. Garimella, P. Mohassel, M. Rosulek, S. Sadeghian, and J. Singh, “Private set operations from oblivious switching,” in IACR International Conference on Public-Key Cryptography. Springer, 2021, pp. 591–617. [40] iDash, “iDASH Privacy & Security Workshop. Secure genome analysis competition,” 2022, available at: http://www.humangenomeprivacy.org/2022/ (2025). [41] H. Köpcke, A. Thor, and E. Rahm, “Evaluation of entity resolution approaches on real-world match problems,” Proceedings of the VLDB Endowment, vol. 3, no. 1-2, pp. 484–493, 2010.

[42] G. Papadakis, M. Fisichella, F. Schoger, G. Mandilaras, N. Augsten, and W. Nejdl, “Github - gpapadis/continuousfilteringbenchmark: Continuous benchmark of filtering methods for entity resolution,” 2022, available at:https://github.com/gpapadis/ContinuousFilteringBenchmark/ (2025). [43] The British Library, “British national bibliography,” 2023, available at: https://www.bl.uk/collection-metadata/metadata-services (2025). [44] The Toronto Public Library, “The toronto public library open dataset,” 2023, available at: http://www.torontopubliclibrary.ca/opendata/ (2025). [45] F. Armknecht, Y. Heng, and R. Schnell, “Strengthening privacypreserving record linkage using diffusion,” Proceedings on Privacy Enhancing Technologies, vol. 2, pp. 298–311, 2023. [46] “Github youzheheng/2022 popets: Strengthening privacypreserving record linkage using diffusion,” 2022, available at: https://github.com/youzheheng/2022 PoPETS (2025). [47] 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, vol. 22, no. 2, pp. 32–41, 2018. [48] A. Inan, M. Kantarcioglu, G. Ghinita, and E. Bertino, “Private record matching using differential privacy,” in Proceedings of the 13th International Conference on Extending Database Technology, 2010, pp. 123– 134. [49] J. Cao, F.-Y. Rao, E. Bertino, and M. Kantarcioglu, “A hybrid private record linkage scheme: Separating differentially private synopses from matching records,” in 2015 IEEE 31st International Conference on Data Engineering. IEEE, 2015, pp. 1011–1022. [50] M. Kuzu, M. Kantarcioglu, A. Inan, E. Bertino, E. Durham, and B. Malin, “Efficient privacy-aware record integration,” in Proceedings of the 16th International Conference on Extending Database Technology, 2013, pp. 167–178. [51] F.-Y. Rao, J. Cao, E. Bertino, and M. Kantarcioglu, “Hybrid private record linkage: Separating differentially private synopses from matching records,” ACM Transactions on Privacy and Security (TOPS), vol. 22, no. 3, pp. 1–36, 2019. [52] R. Schnell, T. Bachteler, and J. Reiher, “Privacy-preserving record linkage using bloom filters,” BMC medical informatics and decision making, vol. 9, no. 1, pp. 1–11, 2009. [53] J. H. Boyd, S. M. Randall, and A. M. Ferrante, “Application of privacypreserving techniques in operational record linkage centres,” Medical data privacy handbook, pp. 267–287, 2015. [54] M. Kuzu, M. Kantarcioglu, E. Durham, and B. Malin, “A constraint satisfaction cryptanalysis of bloom filters in private record linkage,” in Privacy Enhancing Technologies: 11th International Symposium, PETS 2011, Waterloo, ON, Canada, July 27-29, 2011. Proceedings 11. Springer, 2011, pp. 226–245. [55] F. Niedermeyer, S. Steinmetzer, M. Kroll, and R. Schnell, “Cryptanalysis of basic bloom filters used for privacy preserving record linkage,” German Record Linkage Center, Working Paper Series, No. WP-GRLC2014-04, 2014. [56] A. Vidanage, T. Ranbaduge, P. Christen, and R. Schnell, “Efficient pattern mining based cryptanalysis for privacy-preserving record linkage,” in 2019 IEEE 35th International Conference on Data Engineering (ICDE). IEEE, 2019, pp. 1698–1701. [57] A. Vidanage, P. Christen, T. Ranbaduge, and R. Schnell, “A graph matching attack on privacy-preserving record linkage,” in Proceedings of the 29th ACM International Conference on Information & Knowledge Management, 2020, pp. 1485–1494. [58] P. Christen, T. Ranbaduge, and R. Schnell, “Linking sensitive data,” Methods and techniques for practical privacy-preserving information sharing. Cham: Springer, 2020. [59] T. Ranbaduge and R. Schnell, “Securing bloom filters for privacypreserving record linkage,” in Proceedings of the 29th ACM International Conference on Information & Knowledge Management, 2020, pp. 2185–2188. [60] M. Franke, Z. Sehili, F. Rohde, and E. Rahm, “Evaluation of hardening techniques for privacy-preserving record linkage.” in EDBT, 2021, pp. 289–300. [61] D. Vatsalan, P. Christen, and V. S. Verykios, “A taxonomy of privacypreserving record linkage techniques,” Information Systems, vol. 38, no. 6, pp. 946–969, 2013. [62] D. Vatsalan, Z. Sehili, P. Christen, and E. Rahm, “Privacy-preserving record linkage for big data: Current approaches and research challenges,” Handbook of big data technologies, pp. 851–895, 2017.