A private entity matching approach for multiple databases

Abstract

Matching similar records from different databases to prevent duplication in a private manner has attracted plenty of attention, which is referred to as Private Entity Matching (PEM). In spite of various approaches having been proposed to solve this problem, private linking numerical data such as integer (e.g. age), floating point (e.g. body mass index) from multiple databases is an urgent gap, which is commonly required in health domain, statistical departments and more. Hence, this paper targets at solving the problem of linking numerical data from three or more sources in an efficient and secure way. Firstly, we introduce a novel homomorphic encryption method constrained similar modul, which provides strong privacy to encrypt numerical data in the range of real numbers. Then, to avoid frequent decryptions in the homomorphic encryption schema, we draw an inference about the encryption keys. Finally, an accelerated algorithm is proposed to reduce the complexity of multi-party numerical records matching. Our approach is considered absolute safety that no party learns any sensitive information of the others in the absence of collusion. Experiments on two real-world health information databases of patient records validate our approach with regards to the efficiency improvement and at the same time, at no the sacrifice of linkage quality.

Keywords

Entity matching privacy numerical records multiple databases

1 Introduction

In the era of big data, large amounts of data have been generated, collected and stored in several domains. Matching records related to the same entities [1] allows data from different databases to be integrated, which has drawn considerable attention in many areas, including healthcare, businesses, government agencies and research projects. However, in many cases, records have to be linked by private information, for example, in linking medical data of the same patients across different hospitals or in collecting the credit history of users from several sources. Due to privacy and confidentiality concerns often these organizations are not willing or allowed to reveal the sensitive or personal data to other database owners, or to any external party. Consequently, these data need be merged, using a private entity matching protocol.

Private Entity Matching (PEM) [2,3, 2,3] is to find records from two or more data sources that refer to the same or similar individuals, without revealing other information besides the matched records. It has been widely studied in many fields, for instance, an integration of medical information from different hospitals, which integrates similar medical records to reduce redundant data and generate a basic public medical library. The library containing a large number of medical records plays an important role in improving the quality of healthcare services. However, medical data [4,5, 4,5] is highly sensitive, including both medical and personal information. The privacy of sensitive data has to be considered.

There have been numerous works on PEM [6,7, 6,7], but some issues are still unsolved. One of the issues is that most of the approaches are limited to linking data from two sources [8,9, 8,9], however, linking data from more sources has become commonly required in real world. The other issue is that majority of the existing solutions can only handle records made up of strings and categorical values [10,11, 10,11], as to the numerical data, there are few approaches [12]. Actually, for many applications, the data used in entity matching includes numerical information, such as data in statistical department, homeland security, biomedical research and more. For example, Table 1 and Table 2 respectively represent the medical information of patients in database A and database B, Integrating similar medical information from different databases to reduce redundant data is necessary. As shown in database A and database B, patients A44884 and B11301 is similar. Thus, to utilize these data effectively, it is urgent to propose a method to match numerical data in privacy. Some existing methods simply treat numerical data as strings, which would induce the loss of precision. As an example, although 99 and 100 are close numerical values, the same values are found to be distant if they are cast as strings. Recently, an approach has been proposed for numerical data [12], which encodes the numerical data by Bloom Filter (BF). However, BF may be vulnerable to frequency based attacks [13] and has a certain rate of errors [14,15, 14,15], which leads to information leakage and false positives.

Table 1
Patients in database A

ID Body Mass Index Blood Pressure Age

A50088 32.62 69 19

A44884 24.08 66 34

A11542 29.28 80 31

ID	Body Mass Index	Blood Pressure	Age
A50088	32.62	69	19
A44884	24.08	66	34
A11542	29.28	80	31

Table 2

Patients in database B

ID	Body Mass Index	Blood Pressure	Age
B11301	24.28	66	34
B70542	27.21	72	28
B32100	30.36	80	40

To deal with the drawbacks above, we propose an approach specially designed for numerical records, which links numerical records from multiple sources in an efficient and secure way.

Contributions. The main contributions of this paper are summarized as follows.

We introduce a novel encryption method constrained similar modul to encrypt the numerical records in real numbers, which provides stronger security and reduces the encryption time. We also draw an inference about the encryption keys to avoid frequent decryptions in multi-party matching approach.

We propose an accelerated algorithm to reduce the complexity of calculating the similarity among multiple numerical records. We also prove that our accelerated algorithm does not compromise linkage quality. When the number of participants is large, the accelerated algorithm shows a good performance in efficiency.

We analyze our approach and conduct an empirical study on two large real-world medical information databases. Empirical study results manifest that our solution outperforms previous techniques in privacy, efficiency and at no sacrifice of linkage quality.

The remainder of this paper is organized as follows. In the following section, we mention some previous works related to ours. We introduce definitions and background in Section 3. We describe our approach in Section 4 and analyze our approach in Section 5. In Section 6, we report our empirical study. Finally we summarize our findings in Section 7.

2 Related work

Various techniques have been proposed to tackle the problem of PEM. However, most of them consider linking two databases only, and few approaches have been proposed for PEM on multiple databases. The first approach to PEM [16] linked multiple databases by comparing the hash encoded values from all data sources by using a third party. However, this approach only performs exact matching. A Secure Multi-party Computation (SMC)-based approach using an oblivious transfer protocol was proposed by O’Keefe et al. [17] for PEM on multiple databases. While provably secure, the approach can only perform exact matching of masked values. Kantarcioglu et al. [18] introduced a multi-party approach to perform secure equi-join on k-anonymous databases only for exact matching. Recently, a multi-party PEM approach for categorical values based on k-anonymity and game-theoretic concepts was proposed by Mohammed et al. [11]. Another efficient multi-party approach for categorical data was recently proposed by Karapiperis et al. [19] using a Count-Min sketch data structure. Sketches are used to summarize the local set of elements which provide a global synopsis using homomorphic operations, secure summation, and symmetric noise addition privacy techniques. However, these two approaches are limited to dealing with categorical data. Lai et al. [20] developed an efficient multi-party PEM approach using Bloom filters. However, the approach performs only exact matching. This approach has been adapted by Vatsalan and Christen for approximate matching in multi-party PEM. The approximate privacy-preserving comparison functions for calculating similarities of multiple records has only recently been considered by Vatsalan and Christen [21] using the Dice coefficient similarity. Then, Vatsalan and Christen proposed the use of Counting Bloom Filter (CBF), which is a variation of BF, to improve the approach in [22].

There have been a few approaches designed for strings and categorical data, but few work has so far focused on numerical data. Vatsalan and Christen proposed an efficient BF-based masking approach for numerical data [12] and developed a solution for the privacy-preserving similar patient matching problem. However, BF is vulnerable to frequency-based attacks and has a certain rate of errors, which induces information leak and false positives. As we described next, our approach is absolute safety without information leak, and improves the efficiency at no sacrifice of linkage quality.

3 Definitions and preliminaries

In this section, we define the problem and introduce the related technologies in this paper.

3.1 Problem formulation

Definition 1. (PEM) Assume P₁, P₂,..., P_p are p parties owning the datasets D₁, D₂,..., D_p respectively. They wish to identify the matched records among D₁, D₂,..., D_p according to a matching function in a privacy preserving manner, such that at the end of the process P₁, P₂,..., P_p will know only a set of matched records respectively and no information will be revealed about the non-matched records.

For example, there are two records r₁ and r₂ to be matched in the attribute of first name, the values of attribute first name are sara and sarah. Firstly, to protect the privacy of records, we encode two values by Bloom filter encode, BF(sara) = 10100011000100, BF(sarah) = 10100011100101. Then, we calculate the similarity of two encoded values, Dice_sim = 2 × 5/(7 + 5) = 0.83. By comparing with the threshold, we could decide wether two records in attribute first name is match or not.

Our PEM approach is for multi-party numerical records matching, which can combine with other PEM approaches to match the records made up of numerical, strings and categorical values. The definition of numerical record is as follows:

Definition 2. (Numerical Record) The values of all attributes in a record are numerical; or the values of partial attributes in a record are numerical, the numerical attributes can be selected as a numerical record.

3.2 Similar modul

Definition 3. (Similar Modul) Similar modul is a binary operator, which takes a real number modulo a positive integer. The rules can be described as follows [30] : $smod (m, p) = {\begin{matrix} \mod (m, p) m \geq 0 \\ - (\mod (| m |, p)) m < 0 \end{matrix}$ (1)

m is a real number; p is a positive integer.

Similar modul is one of homomorphic encryption schemes, which can perform the homomorphic operators addition, subtraction, multiplication and division in real number. More formally, let Enc_kpuband Dec_kpriv be the encryption and decryption functions with keys kpub and kpriv, m₁ and m₂ be plain texts, c(m₁) and c(m₂) be cipher texts such that c(m₁) = Enc_kpub(m₁), c(m₂) = Enc_kpub(m₂). Thus, homomorphic operations can be expressed by operator “±” as follows: ${Dec}_{kpri} (c (m_{1}) \pm c (m_{2})) = m_{1} \pm m_{2}$ (2)

3.3 Numerical similarity calculation

Numerical data is often encountered in PEM, such as age, year, price, or blood pressure. In this paper we use the absolute difference approach to calculate the similarity between the numerical values, the similarity between two numerical data n₁, n₂ is calculated as follows [12]: $sim (n_{1} n_{2}) = {\begin{matrix} 1.0 - | n_{1} - n_{2} / d_{\max} | \\ 1.0 - | n_{1} - n_{2} | \geq d_{\max} else \end{matrix}$ (3) where d_max is the maximum absolute difference between two numerical values that is to be tolerated. For example, assume the maximum absolute difference in two salary values is d_max = $500. If n₁ = $1800 and n₂ = $1700, then sim_{_numabs}($1800, $1700) = 1.0 - $100 / $500 = 1.0 - 0.2 = 0.8.

4 Proposed solution

In this part, we provide an overview of our solution, which is composed of three main phases: 1) Data Preparation, 2) Data Encryption and 3) Private Multi-Party Numerical Records Matching. We then describe each phase in detail through Section 4.1 to 4.3 and take an example to illustrate our solution in Section 4.4. The framework is presented in Figure 1.

Fig. 1

The framework of our solution.

4.1 Data preparation

In the data preparation phase, without loss of generality, the parties agree on the parameters and generate encryption keys to encrypt numerical data. The symbols used in our approach are shown in Table 3.

Table 3
Table of frequent symbols

Symbol Description

D_i databases for party i, 1≤i≤P

N size of the databases

P number of the participants

d number of the common attributes

n nth attribute, 1≤n≤d

θ _d threshold of the attribute d

h an integer

Symbol	Description
D_i	databases for party i, 1≤i≤P
N	size of the databases
P	number of the participants
d	number of the common attributes
n	nth attribute, 1≤n≤d
θ _d	threshold of the attribute d
h	an integer

Agree on the Parameters. We assume P (P ≥ 3) participants in our method P₁, P₂,..., P_P with their respective databases D₁, D₂,..., D_P to perform private entity matching on the common attributes {a₁, a₂,..., a_d}. Linkage Unit (LU) is used to decide whether the records among P parties are match.

Generate Encryption Keys. Before encrypting data, each party needs to receive encryption keys first. In our approach, P₁ generates encryption keys and sends them to the corresponding parties. Specifically, the encryption keys containing d sub-keys respectively encrypt the attributes a₁, a₂,..., a_d, which would reduce the possibility of inferring the plain texts.

4.2 Data encryption

To calculate the similarity among P records respectively from P parties, each party needs to encrypt its data with encryption keys first, then releases the encrypted data to LU to perform multi-party private entity matching.

In this phase, we introduce a lower cost homomorphic encryption scheme similar modul to encrypt numerical data in the range of real numbers. The process of encryption and decryption are described as follows:

Encryption. For a plaintext message m ∈ D_i, with keys (p, q, rand), the p and q are prime number, rand is a random integer. Z_p = {m| |m| ≤ p} is the space of plaintexts, Z_p_* _q = {m| |m| < p ∗ q} is the space of ciphertexts. The encryption of m is computed as follows[26]: $Enc (m) = smod {(m + rand * p), p * q}$ (4)Decryption. For a ciphertext c(m) with keyp. Decryption is computed as follows [24]: $Dec (c (m)) = smod (c (m), p)$ (5)

Specifically, as discussed by Domingo-Ferrer and Herrer-Joancomart in [25], the homomorphic encryption scheme similar modul has two important properties, which provides strong privacy guarantees.

Theorem 1. Because the rand is a random integer, there will be Enc₁(m) ≠ Enc₂(m) as to the same m, however Dec(c₁(m)) = Dec(c₂(m)).

Theorem 2. The similar modul has been proved to be secure. If an attacker only knows the ciphertexts, without knowing p, q and rand, it can hardly infer the plaintexts.

Encrypting the Records. In our solution, each party respectively encrypts records with its own keys as shown in Algorithm 1. For each record, we encrypt its attributes by different sub-keys to improve the security of our approach. More formally, the encryption of the ith record can be described as C_in = Enc(r_i(a_n)) = {(r_i(a_n) + rand_in ∗ p_in), q_in ∗ p_in}, 1 ≤ n ≤ d and C_i = {C_i₁, C_i₂, C_in,..., C_id}.

4.3 Private numerical records matching

After encrypting its own data, each party sends the cipher texts C₁, C₂,..., C_P to LU to determine whether (r₁, r₂,..., r_P) is match or not. Figure 2 shows the whole process of matching multi-party numerical records in privacy, from which we know that our approach is absolutely safe without any information leakage.

Fig. 2

The process of private multi-party numerical records matching.

As to the multi-party private matching, we regard P records as a match if any two records are matched, which incurs high computation costs. Hence, in this section, we propose an accelerated algorithm for private multi-party numerical records matching approach, which can compute the similarity among P records by the cipher texts efficiently. The main idea is to obtain the minimum and the maximum values in each attribute, then we only perform similarity calculation on them instead of any two values, we can directly determine whether P records is match or not. Our accelerated algorithm is proposed based on the following proposition:

Proposition 1. Assuming that if the similarity between the minimum and the maximum values in certain attribute is above the threshold, then the similarity between any two values in this attribute is above the threshold.

Proof. If sim(a_nmin, a_nmax) > θ _n , we can infer sim(a, b) > θ _n , a_nmin ≤ a, b ≤ a_nmax.

If a >b, sim(a, b) = 1 - (a - b)/d_max = 1 - ((a/b) - 1)/d_max; (proposed in Eq. (4))

When a = a_nmax, b = a_nmin, sim(a, b) get minimum value which is equal with sim (a_nmin, a_nmax);

Thus, sim(a, b) > θ _n ;

Evidenced by the same token, when a <b or a = b, sim(a, b) > θ _n .

Thus, we prove the Proposition 1.

As the proof shows, the Proposition 1 is correct. Hence, we can conclude that the approach introducing the accelerated algorithm has the same linkage quality as the naive approach in which any two encrypted records compare.

Algorithm 1 Encrypting the Records

Require:

r_i: A record from party i, 1 ≤ i ≤ P;

r_i(a_n): The nth attribute in record r_i, 1 ≤ n ≤ d;

h: A positive integer;

Ensure:

C_i: The encryption of r_i;

for each r_i( a_n) do

Generatekey() = {p_in, q_in, rand_in};

p_in = p_1n, q_in = q_1n, rand_1n +h q_1n;

C_in = Enc(r_i(a_n)) = {(r_i(a_n) + rand_in ∗ p_in), q_in ∗ p_in};

end for

return C_i = {C_i1, C_i2,..., C_id};

Then, our Decision Rules (DR) can be described as follows: $DR = {\begin{matrix} sim (a_{nmin}, a_{nmax}) \geq θ_{n}, 1 \leq n \leq d, match \\ otherwise, - match \end{matrix}$ (6)

a_nmin: The minimum value of the attribute a_n; a_nmax: The maximum value of the attribute a_n.

Only when sim(a_nmin, a_nmax) in all attributes are above the threshold, we regard (r₁, r₂,..., r_P) as a match. Otherwise, (r₁, r₂,..., r_P) is non-match. Based on the DR, the similarity calculations can be terminated early, if the similarity of P records in one attribute has been calculated below the threshold.

By this token, the most important step is to obtain the minimum and the maximum values in each attribute. However the data which LU receives is encrypted. Thus, if our approach satisfies that if m₁ > m₂, thenc(m₁) > c(m₂), we can only perform on the cipher texts without frequent decryptions. To satisfy this condition, we assume: x₁, x₂ are the plain texts and the encryption of x₁, x₂ are E(x₁) = smod{(x₁ + rand₁ ∗ p), p ∗ q}, E(x₂) = smod{(x₂ + rand₂ ∗ p), p ∗ q} (as calculated in Eq. (5)). Then we infer that what relation between the rand₁ and rand₂, it satisfies: when x₁ ≥ x₂ ⇔ E(x₁) ≥ E(x₂).

(1) x₁ ≥ x₂ ⇒ E(x₁) ≥ E(x₂);

x₁ - x₂ ≥ (rand₂ - rand₁) ∗ p + (n₁ - n₂) ∗ p ∗ q, if x₁ ≥ x₂, (rand₂ - rand₁) ∗ p + (n₁ -n₂) ∗ p ∗ q ≥ 0.

Thus, when rand₂ ≥ rand₁ + (n₂ - n₁) ∗ q, it satisfies: x₁ ≥ x₂ ⇒ E(x₁) ≥ E(x₂).

(2) E(x₁) ≥ E(x₂) ⇒ x₁ ≥ x₂;

x₁ + rand₁ ∗ p - n₁ ∗ p ∗ q ≥ x₂ + rand₂ ∗ p - n₂ ∗ p ∗ q, rand₂ - rand₁ ≤ (x₁ - x₂)/p + (n₂ - n₁) ∗ q.

When x₁ - x₂ = 0,

(x₁ - x₂)/p + (n₂ - n₁) ∗ q get minimum value, rand₂ - rand₁ ≤ (n₂ - n₁) ∗ q,

Thus, when rand₂ ≤ rand₁ + (n₂ - n₁) ∗ q, it satisfies: E(x₁) ≥ E(x₂) ⇒ x₁ ≥ x₂.

Above all, when rand₂ = rand₁ + (n₂ - n₁) ∗ q, it satisfies: x₁ ≥ x₂ ⇔ E(x₁) ≥ E(x₂).

Thus, we conclude the Corollary 1 as follows:

Corollary 1. When rand₂ = rand₁ + (n₂ - n₁) ∗ q = rand₁ + h ∗ q (h is an integer), the cipher texts retain the inequality relation in the plain texts.

Definition 4. (Constrained Similar Modul) In the homomorphic encryption scheme similar modul, if the encryption keys for the P parties in attribute a_n, rand_in ( 1 ≤ i ≤ P, 1 ≤ n ≤ d) satisfy rand_in = rand_1n + h ∗ q_1n (rand_1n is a random integer), we name it as constrained similar modul.

Algorithm 2 Private Matching Numeric Records for Multiple Databases

Require:

(C₁, C₂,..., C_p): The encryption records from P parties;

Ensure:

The P encryption records (C₁, C₂,..., C_p) are match or non-match;

flag = true;

n = 1; i = 2; j = 3;

for n ≤ d do

min = C_1n > C_2n ? C_2n: C_1n;

max = C_1n ≤ C_2n ? C_2n: C_1n;

for i ≤ P and j ≤ P do

tempmax = C_in ≥ C_jn ? C_in: C_jn;

tempmin = C_in < C_jn ? C_in: C_jn;

if tempmax > max then

max = tempmax;

end if

if tempmin < min then

min = tempmin;

end if

i += 2; j +=2;

end for

C_a = Enc(max) - Enc(min)

if sim( min, max) = 1 - Dec(C_a)/d_max < θ_n then

flag = false;

end if

n ++;

end for

return flag;

The encryption scheme in our approach is constrained similar modul, in which the cipher texts retain the inequality relation in the plain texts. Therefore, as shown in Algorithm 1, our approach generates encryption keys rand_i = rand₁ + h ∗ q. Remarkably, the constrained similar modul still has the two theorems described in Section 4.2 to guarantee the privacy of our approach.

The process of getting the maximum and the minimum values in each attribute has been given in Algorithm 2. Specially, to reduce complexity, our approach divides the encrypted numerical records into pairs, and performs the comparison in each pair. Then we select the larger one in each pair to compare to get the maximum value, and the same way to get the minimum value, which takes less time than other comparison methods. After obtaining the maximum and the minimum values in each attribute, our approach performs the homomorphic subtraction on them, C_a = Enc(a_nmax) - Enc(a_nmin), 1 ≤ n ≤ d. Then, we pass the C_a to P₁ to decrypt and calculate the similarity by the Eq. (4). At last, we judge the relation between sim(a_nmin, a_nmax) = 1 - Dec(C_a)/d_max and θ _n . If the sim(a_nmin, a_nmax) in all attributes are above the threshold, we regard (r₁, r₂,..., r_P) as a match. In the whole process of private entity matching, our approach only performs on the cipher texts without frequent decryptions, which reduces the time cost.

4.4 An illustration of our approach

In this part, we take an example to illustrate our approach with the process of encrypting data and private matching multi-party numerical records.

Table 4 presents the four records selected from patient database which are used to perform private numerical records matching. In Table 5, we calculate the similarity among the records in [P96, P80, P26] and [P96, P26, P37] in each attribute and determine whether the records are match or not. As to the records in [P96, P80, P26] in attribute Blood pressure, firstly, we generate encryption keys and the parameters [p = 181, q = 71, rand₁ = 23, rand₂ = 94, rand₃ = 236, d₁ = 10, θ ₁ = 0.95]. Then, we encrypt data with keys. C₁ = Enc(69) = smod = 4232; C₂ = Enc(66) = smod[(66 + 94 * 181), 181 * 71] = 4229; C₃ = Enc(69) = smod[(69 + 236 * 181), 181 * 71] = 4232. C_min = 4229, C_max = 4232, C_sub = C_max - C_min = 3. Sim(P96, P80, P26) = 1 - Dec(C_sub)/10 = 0.7 in attribute Blood pressure. The same way to calculate the similarity of other attributes as shown in Table 5. At last, we can decide [P96, P80, P26] is non-match and [P96, P26, P37] is match. In the whole example, there is no frequent decryptions and comparisons, and the accelerated algorithm reduces the complexity at no sacrifice of linkage quality.

Table 4
Patient database D

Patient ID Blood Pressure 2-Hours Erum Insulin Diabetes Pedigree Age

P96 69 0 0.351 31

P80 66 543 0.158 53

P26 69 0 0.347 31

P37 69 0 0.357 31

Patient ID	Blood Pressure	2-Hours Erum Insulin	Diabetes Pedigree	Age
P96	69	0	0.351	31
P80	66	543	0.158	53
P26	69	0	0.347	31
P37	69	0	0.357	31

Table 5

Similarity calculation

Patient ID	Blood Pressure	2-Hours Erum Insulin	Diabetes Pedigree	Age	Matching Result
P96 P80 P26	0.7	0	0.62	0.74	0
P96 P26 P37	1	1	0.98	1	1

5 Analysis of the approach

We now analyze our approach in terms of privacy, complexity and linkage quality.

Privacy: We assume that all parties will follow the protocol honestly, but they may try to infer private information based on the messages they receive during the process without collusion [26]. The semi-honest model without collusion is a common assumption for multi-party approaches. Next we summarize the information that our approach discloses to each of the participants.

P₁: P₁ receives the encrypted results of secure subtraction from LU. After decrypting the encrypted results with private key, the real results only show the final results without revealing the specific information.

P_i (2 ≤ i ≤ P): Each party does not receive any messages regarding other participants. Thus, without collusion each part cannot infer any information.

LU: This party receives the encrypted data from P_i (1 ≤ i ≤ P). However, only knows the encrypted data without decryption keys, LU can hardly infer the plain texts (The security is guaranteed by two properties in Section 4.2).

Complexity: We assume P parties in the approach, each having a database of n records. In step 1 of our approach, the agreement of parameters has a constant communication complexity. In the step of blocking, with the simplified assumption, all blocks are of equal size n/b. The encryption of records is O(n) at each party. All combinations of P parties is O(b(n/b) ^P ). For each combination, the process of obtaining the minimum and the maximum values in each attributes is O(3/2P). Then, for each attribute we perform the similarity calculation on the minimum and the maximum values. For d attributes, the similarity calculation is O(d). Thus, the complexity of our approach is O(b(n/b) ^P )(O(3/2Pd) + O(d)) + O(nP). Comparing with the naive approach which performs decryption and similarity calculation on any two encrypted records, the complexity of naive approach is O(b(n/b) ^P )(O((P(P - 1))/2) O(d)) + O(nP). Through the above analysis, we draw the conclusion that our approach has advantages in efficiency with the increasing participates P.

Linkage quality: Our approach encrypts numerical data (integer or float) by constrained similar modul. The constrained similar modul is a homomorphic encryption scheme which can perform the homomorphic operators addition, subtraction, multiplication and division. As the numerical similarity calculation shown in Eq. (4), sim(a_nmin, a_nmax) = 1 - Dec(c(a_nmax) - c(a_nmin)/d_max. The equation indicates that our approach only performs the similarity calculation on the encrypted numerical data and the result is equivalent with the performance on the original data. Thus, we can conclude that the encryption scheme in our approach has no effect on the linkage quality. We also design an accelerated algorithm to reduce computation, the proof has been given in Section 4.3 that our approach has the same linkage quality with the naive approach in which any two encrypted records compare. Thus, no matter the encryption scheme or the accelerated algorithm has no effect on the linkage quality. However, as to the approach in [17], which encode the numerical data by BF. The quality of BF-based masking depends on the BF parameters [33]. For a given BF length l, and the number of elements q to be inserted into the BF, the optimal number of hash functions k, that minimizes the false positive rate f is calculated as k = l/q · ln(2), leading to a false positive rate of f = (1/2^ln (2))^l/q.

6 Experiment

To perform the experimental analysis, two real-world medical health information databases are used for this experimental study, which include Diabetes UCI database [28] and Medical Quality Improvement Consortium (MQIC) database [12]. We evaluate our approach in terms of complexity and linkage quality. All tests are conducted on a computer server with a 64-bit, 8.0G of RAM Intel Core (3.30 GHz) CPU.

6.1 Database information

The Pima Indians Diabetes database contains 768 patient records, which is downloaded from http://archive.ics.uci.edu/ml/databases/Pima+Indians+Diabetes. Each patient is represented by a 8 dimensional vector.

The Medical Quality Improvement Consortium (MQIC) database contains a random sample of approximately 6 million patient records, which is downloaded from https://github.com/Mathuv/PPSPM. Each patient is represented by a 7 dimensional vector.

These two databases contain only categorical and numerical attributes. The blocking keys B and the matching attributes A are shown in Table 6. We group the records which have the same values in attributes B as a block and perform our approach on the matching attributes A of the records that are within the same block.

Table 6
A summary of databases

Database |D| B A

Diabetes 768 Diabetes, Age Diastolic blood pressure,

Diabetes pedigree function

MQIC 6,000,000 Gender, Diabetes, Age, Body mass index

Hypertension,Stroke, Smokingr

Database	\|D\|	B	A
Diabetes	768	Diabetes, Age	Diastolic blood pressure,
			Diabetes pedigree function
MQIC	6,000,000	Gender, Diabetes,	Age, Body mass index
		Hypertension,Stroke, Smokingr

6.2 Evaluation metrics

We use the following measures to evaluate the performance of our private multi-party numerical records matching technique in terms of complexity and linkage quality. Complexity is evaluated by the total runtime required for our approach. We utilize Precision, Recall and F-measure to evaluate the linkage quality. Based on the number of True Positives (TP), True Negatives (TN), False Positives (FP) and False Negatives (FN), Precision, Recall,and F-measure can be calculated as follows[29]:

Precision: The ratio of a correct match TP to all declared duplicates. It is calculated as: $Precision = \frac{TP}{TP + FP}$ (7) Recall: The ratio of a correct match TP to all true duplicates. It is calculated as: $Recall = \frac{TP}{TP + FN}$ (8) F-measure: This measure, also known as f-score or f₁-score, calculates the harmonic mean between precision and recall. It is calculated as: $F - measure = 2 \times (\frac{prec \times rec}{prec + rec})$ (9)

6.3 Experiment design

Complexity: We evaluate the complexity of our approach on the large database MQIC. We respectively extract 5000, 10,000, 50,000, 100,000, 500,000, 1000,000 records from MQIC for 3, 5, 7, and 9 parties, with 50% of records occurring in all parties (i.e. 50% of records are true matches). Then we measure the runtime with increasing database sizes and the number of parties.

Linkage quality: We evaluate the linkage quality of our approach on databases Pima Indians Diabetes and MQIC. And we measure the Precision, Recall and F-measure with different database sizes, the number of parties and thresholds. We compare our approach with previous approaches which are described as follows:

BF approach: The numerical records are encrypted by BF [14].

Naive approach: Any two encrypted records in theP records are compared to calculate the similarity.

Original approach: We perform our approach on the plain texts without encryption.

We set the parameters in our approach as the range of threshold is [0.85, 1], d_max = 5 for Age, d_max = 1 for Body mass index, d_max = 10 for Diastolic blood pressure, and d_max = 1 for Diabetes pedigree function. The parameters in BF approach are set following the work in [14].

6.4 Performance evaluation

Complexity: In our first set of experiments, we evaluate the scalability with the variation of database sizes in four approaches on database MQIC. From Figure 3 we can see that our approach takes less time than BF approach, which indicates the improvement of our approach in efficiency. Our approach also saves much time than the naive approach (The complexity has been analyzed in Section 4), which indicates that our accelerated algorithm has a good performance. We also can see the runtime of our approach almost equals with the runtime of original approach, which confirms the fact that the encryption by constrained similar modul costs a little time. The blocking keys B and the matching attributes A have been shown in Table 6, if we change the matching attribute Age to blocking key, the runtime drops heavily as shown in Figure 4. Thus, based on a good blocking, our approach has an excellent performance in efficiency.

Fig. 3

Runtime with different database sizes.

Fig. 4

Runtime (Blocking with age) with different database sizes.

Next, we evaluate scalability with different numbers of parties in four approaches for Database size = 5,000. As shown in Figure 5, with the participants increasing, our approach shows a greater advantage in efficiency, which owes to our accelerated algorithm.

Fig. 5

Runtime with different number of parties.

Linkage Quality: In Figure 6 and Figure 7, we evaluate the linkage quality with the variation of database sizes on the MQIC database in four approaches. As Figure 6 shows, our approach has the same linkage quality with naive approach and original approach (linkage quality has been analyzed in Section 5), which validates the accelerated algorithm and the encryption do not loss of linkage quality. Thus, we merge three lines into one in the following experimental figures. The linkage quality of BF approach is lower than our approach, the reason is that the encryption scheme in our approach has no information loss but the BF approach has. As shown in Figure 7, the linkage quality decreases with the increasing database sizes, this is because more records induce more false positives. Figure 8 shows the linkage quality with different number of parties. The linkage quality of our approach is better than BF approach with increasing parties. Figure 9 and Figure 10 show the linkage quality with the variation of thresholds on the MQIC database and Diabetes database. We can see the linkage quality on Diabetes database is better than which on MQIC database, this is due to the database quality. The matching attributes in Diabetes database can represent certain entity better than which in MQIC database.

Fig. 6

F-measure with different database sizes.

Fig. 7

Linkage quality with different database sizes.

Fig. 8

Linkage quality with different number of parties.

Fig. 9

Linkage quality with different threshold in MQIC.

Fig. 10

Linkage quality with different threshold in Diabetes.

Above all, we can conclude that our approach performs better than previous approaches in efficiency and privacy and at the same time, at no sacrifice of linkage quality.

7 Conclusion

In this paper, we study the problem of linking numerical records from three or more sources in privacy, which is commonly required in health domain, statistical departments, homeland security and more. We encrypt numerical data by a constrained similar modul to provide stronger privacy. The constrained similar modul takes a little encryption time and has no effect on the linkage quality, which is better than the previous privacy technique BF. Then, we draw an inference about the encryption keys. Based on these encryption keys, our approach can only perform on the cipher texts without frequent decryptions, which reduces the time cost. Next, we derive an accelerated algorithm in private multi-party PEM matching, which avoids any two records calculating the similarity and reduces the complexity without loss of linkage quality. Especially, when the number of participants is large, our approach shows a good performance in efficiency. Finally, as experiments show, our approach exhibits high performance both in efficiency and privacy and at the same time, at no sacrifice of linkage quality.

Footnotes

Acknowledgments

This work is supported by the National Key R&D Program of China (2018YFB1003404) and the National Natural Science Foundation of China (61672142, 61602103, 61472070).

References

Christen

, Data Matching: Concepts and Techniques for Record Linkage, Entity Resolution, and Duplicate Detection. Data-Centric Systems and Applications, Springer, (2012).

Clifton

, Kantarcioglu

, Doan

, Schadow

, Vaidya Elmagarmid

, Suciu

, Privacy-preserving data integration and sharing, In Proceedings of the 9th ACM SIGMOD Workshop on Research Issues in Data Mining and Knowledge Discovery, (2004), 19–26.

Vatsalan

, Christen

, Verykios

V.S.

, Privacy-Preserving Record Linkage, Encyclopedia of Big Data Technologies, (2019).

Franke

, Gladbach

, Sehili

, Rohde

and Rahm

, ScaDS research on scalable privacy-preserving record linkage, Datenbank-Spektrum 19 (2019), 31–40.

Laud

and Pankova

, Privacy-preserving record linkage in large databases using secure multiparty computation, In Proceedings of the 6th iDASH Privacy and Security Workshop, (2018), 84.

Vatsalan

, Christen

and Verykios

V.S.

, A taxonomy of privacy-preserving record linkage techniques, Information Systems Journal 38 (2013), 946–969.

Vatsalan

, Sehili

, Christen

and Rahm

, Privacy-Preserving Record Linkage for Big Data: Current Approaches and Research Challenges, Handbook of Big Data Technologies, (2017).

Verykios

V.S.

, Karakasidis

and Mitrogiannis

, Privacy preserving record linkage approaches, International Journal of Data Mining, Modelling and Management 1 (2009), 206–221.

and Atallah

, Protocols for secure remote database access with approximate matching, In Processings of E-Commerce Security and Privacy, (2001), 87–111.

10.

Trepetin

, Privacy-preserving string comparisons in record linkage systems: a review, Information Security Journal 17 (2008), 253–266.

11.

Mohammed

, Fung

and Debbabi

, Anonymity meets game theory: secure data integration with malicious participants, In VLDB Journal 20 (2011), 567–588.

12.

Vatsalan

and Christen

, Privacy-preserving matching of similar patients, Journal of Biomedical Informatics 59 (2016), 285–298.

13.

Vidanage

, Ranbaduge

, Christen

and Schnell

, Effient pattern mining based cryptanalysis for privacy-preserving record linkage, IEEE 35th International Conference on Data Engineering, (2019).

14.

Durham

, Xue

, Kantarcioglu

and Malin

, Quantifying the correctness, computational complexity, and security of privacy-preserving string comparators for record linkage, Information Fusion 13 (2012), 245–259.

15.

Kuzu

, Kantarcioglu

, Durha

and Malin

, A constraint satisfaction cryptanalysis of Bloom filters in private record linkage, In: Proceedings of the 11th International Conference on Privacy Enhancing Technologies, (2011), 226–245.

16.

Quantin

, Bouzelat

and Allaert

, How to ensure data security of an epidemiological follow-up: quality assessment of an anonymous record linkage procedure, Journal of Medical Informatics 49 (1998), 117–122.

17.

O’Keefe

, Yung

, Gu

and Baxter

, Privacy-preserving data linkage protocols, In: Processings of ACM Workshop on Privacy in the Electronic Society, (2004), 94–102.

18.

Kantarcioglu

, Jiang

and Malin

, A privacy-preserving framework for integrating person-specific databases, In PSD, (2008).

19.

Karapiperis

, Vatsalan

, Verykios

V.S.

and Christen

, Large scale multi-party counting set intersection using a space efficient global synopsis, In: Processings of 20th International Conference on Database Systems for Advanced Applications, (2015), 329–345.

20.

Lai

, Yiu

, Chow

, Chong

and Hui

, An Efficient Bloom filter based Solution for Multi-party Private Matching, In SAM, (2006).

21.

Vatsalan

and Christen

, Scalable privacy-preserving record linkage for multiple databases, In: Proceedings of the 23th ACM International Conference on Information and Knowledge Management, (2014), 1795–1798.

22.

Vatsalan

and Christen

, Scalable privacy-preserving linking of multiple databases using counting Bloom filters, In: Proceedings of IEEE 16th International Conference on Data Mining Workshops, (2017).

23.

Durham

, A Framework for Accurate, Efficient Private Record Linkage, Ph.D. Thesis, Vanderbilt University, (2012).

24.

Xiang

G.L.

and Chen

X.M.

, Homomorapic Encryption Scheme in the Range of the Real, Journal of Computer Engineering Application 20 (2005).

25.

Domingo-Ferrer

and Herrera-Joancomarti

, A new privacy homomorphism and applications, Information Processing Letters 60 (1996), 277–282.

26.

Kuzu

and Inan

, Efficient privacy-aware record integration, In: Proceedings of the 16th In-ternational Conference on Extending Database Technology, (2013), 167–178.

27.

Schnell

, Bachteler

and Reiher

, Privacy Preserving record linkage using Bloom filters, BMC Medical Information and Decision Making 9 (2009), 41.

28.

Wang

, Adaptive semi-supervised recursive tree partitioning: The ART towards large scale patient indexing in personalized healthcare, Journal of Biomedical Informatics 55 (2015), 41–54.

29.

Elmagarmid

A.K.

, Ipeirotis

P.G.

and Verykios

V.S.

, Duplicate record detection: a survey, IEEE Transactions on Knowledge and Data Engineering 19 (2007), 1–16.

A private entity matching approach for multiple databases

Abstract

Keywords

1 Introduction

Table 1 Patients in database A ID Body Mass Index Blood Pressure Age A50088 32.62 69 19 A44884 24.08 66 34 A11542 29.28 80 31

3 Definitions and preliminaries

3.1 Problem formulation

3.2 Similar modul

Table 3 Table of frequent symbols Symbol Description D i databases for party i, 1≤i≤P N size of the databases P number of the participants d number of the common attributes n nth attribute, 1≤n≤d θ d threshold of the attribute d h an integer

Table 4 Patient database D Patient ID Blood Pressure 2-Hours Erum Insulin Diabetes Pedigree Age P96 69 0 0.351 31 P80 66 543 0.158 53 P26 69 0 0.347 31 P37 69 0 0.357 31

6 Experiment

6.1 Database information

Table 6 A summary of databases Database |D| B A Diabetes 768 Diabetes, Age Diastolic blood pressure, Diabetes pedigree function MQIC 6,000,000 Gender, Diabetes, Age, Body mass index Hypertension,Stroke, Smokingr

6.4 Performance evaluation

Footnotes

Acknowledgments

References

Table 1
Patients in database A

ID Body Mass Index Blood Pressure Age

A50088 32.62 69 19

A44884 24.08 66 34

A11542 29.28 80 31

Table 3
Table of frequent symbols

Symbol Description

D_i databases for party i, 1≤i≤P

N size of the databases

P number of the participants

d number of the common attributes

n nth attribute, 1≤n≤d

θ _d threshold of the attribute d

h an integer

Table 4
Patient database D

Patient ID Blood Pressure 2-Hours Erum Insulin Diabetes Pedigree Age

P96 69 0 0.351 31

P80 66 543 0.158 53

P26 69 0 0.347 31

P37 69 0 0.357 31

Table 6
A summary of databases

Database |D| B A

Diabetes 768 Diabetes, Age Diastolic blood pressure,

Diabetes pedigree function

MQIC 6,000,000 Gender, Diabetes, Age, Body mass index

Hypertension,Stroke, Smokingr