The process of linking databases that contain sensitive information about individuals across organisations is an increasingly common requirement in the health and social science research domains, as well as with governments and businesses. The lack of unique entity identifiers means that linking often has to rely on personal details such as names and addresses. Data linkage protocols have been proposed to limit the leakage of sensitive personal information, while privacy-preserving record linkage (PPRL) techniques have been developed to conduct linkage on encoded data. While PPRL techniques are now being employed in real-world applications, the focus of PPRL research has been on the technical aspects of linking sensitive data, such as encoding methods and cryptanalysis attacks. Organisational and human challenges when employing such techniques in practice, however, have not been studied adequately. In this paper, we describe the end-to-end data linkage process and formalise two fundamental types of linkage protocols. We describe the types of parties that participate in such a protocol, and analyse what sensitive information each party can learn from the data it obtains legitimately within the protocol. We also discuss the possible motivations and objectives of an adversary who aims to learn sensitive information from the databases being linked, and show that current PPRL protocols still result in the unintentional leakage of sensitive information. We provide recommendations to help data custodians and other parties involved in data linkage projects to identify and prevent vulnerabilities and make their projects more secure.

Privacy-Preserving Record Linkage (PPRL) aims to identify records that refer to the same entity across databases held by different organisations without revealing sensitive information about the entities whose records are being linked. Research has shown that some popular PPRL techniques can be vulnerable to reidentification attacks. In response, the use of Differential Privacy (DP) has been investigated with the aim to provide formal privacy guarantees for PPRL. Multiple studies have explored the use of DP during the blocking stage, where similar records are grouped prior to comparison. Yet, since encodings of individual records must be shared for comparison and classification, the linkage process remains vulnerable to attacks despite being differentially private during the blocking stage, unless a computationally expensive secure multi-party protocol is used. Other studies have explored the use of DP during the encoding stage to guarantee that encoded records remain private even when exchanged between the parties involved in a PPRL protocol. While such approaches do employ established DP methods, we consider that their current application in the context of PPRL is nonsensical. The purpose of PPRL is to identify, with highest possible accuracy, specific records that refer to the same entity, while DP perturbs sensitive data to prevent possible reidentification of individuals within a data set. Therefore, this is a mismatch of paradigms. In its current use, DP for PPRL requires substantial perturbation to guarantee privacy, which in turn leads to a notable degradation of linkage quality. To support this argument, we survey and review the use of DP for PPRL, focusing on its effectiveness in protecting the real-world entities (generally people) whose records are being linked.

Privacy-Preserving Record Linkage (PPRL) aims to link records across multiple data sources without revealing any sensitive information about the entities whose records are being linked. However, recent studies have identified attacks that exploit multiple vulnerabilities in popular PPRL methods. To address such vulnerabilities and prevent possible reidentification, hardening techniques have been proposed to perturb patterns in encodings. Most such hardening techniques are either specific to bit array based encodings (such as Bloom filters), or they rely on randomness which can negatively affect linkage quality. Here we propose a novel hardening technique that addresses the frequency, similarity, and co-occurrence vulnerabilities, and is applicable on any PPRL method that uses character q-grams. Our technique identifies and hardens only those q-grams that are vulnerable, and modifies them using a non-random, context-aware approach that ensures these q-grams are not vulnerable after hardening. We evaluate our technique using real and synthetic data sets, and show that it substantially reduces the vulnerabilities of PPRL encoding methods and makes them more secure.

Record linkage is the process of matching records that refer to the same entity across two or more databases. In many application areas, ranging from healthcare to government services, the databases to be linked contain sensitive personal information, and hence, cannot be shared across organisations. Privacy-Preserving Record Linkage (PPRL) aims to overcome this challenge by facilitating the comparison of records that have been encoded or encrypted, thereby allowing linkage without the need of sharing any sensitive data. While various PPRL techniques have been developed, most of them do not properly address privacy concerns, such as the various vulnerabilities of encoded data with regard to cryptanalysis attacks. Existing PPRL methods, furthermore, do not provide conceptual analyses of how a user should set the various parameters required, possibly leading to sub-optimal results with regard to both linkage quality and privacy protection. Here we present a novel encoding method for PPRL that employs reference q-gram sets to generate bit arrays that represent sensitive values. Our method requires a single user parameter that determines a trade-off between linkage quality, scalability, and privacy. All other parameters are either data driven or have strong bounds based on the user-set parameter. Furthermore, our method addresses the length, frequency, and pattern-based PPRL vulnerabilities that are exploited by existing PPRL attacks. We conceptually analyse our method and experimentally evaluate it using multiple databases. Our results show that our method provides robust results for both high linkage quality and strong privacy protection.

Privacy-preserving record linkage (PPRL) facilitates the matching of records that correspond to the same real-world entities across different databases while preserving the privacy of the individuals in these databases. A Bloom filter (BF) is a space efficient probabilistic data structure that is becoming popular in PPRL as an efficient privacy technique to encode sensitive information in records while still enabling approximate similarity computations between attribute values. However, BF encoding is susceptible to privacy attacks which can re-identify the values that are being encoded. In this paper we propose two novel techniques that can be applied on BF encoding to improve privacy against attacks. Our techniques use neighbouring bits in a BF to generate new bit values. An empirical study on large real databases shows that our techniques provide high security against privacy attacks, and achieve better similarity computation accuracy and linkage quality compared to other privacy improvements that can be applied on BF encoding.

To facilitate advanced analytics, data science projects increasingly require records about individuals to be linked across databases. Generally no unique entity identifiers are available in the databases to be linked, and therefore quasi-identifiers such as names, addresses, and dates of birth are used to link records. The process of linking records without revealing any sensitive or confidential information about the entities represented by these records is known as privacy-preserving record linkage (PPRL). Various encoding and encryption based PPRL methods have been developed in the past two decades. Most existing PPRL methods calculate approximate similarities between records because errors and variations can occur in quasi-identifying attribute values. Even though being used in real-world linkage applications, certain PPRL methods, such as popular Bloom filter encoding, have shown to be vulnerable to cryptanalysis attacks. In this paper we present a novel attack on PPRL methods that exploits the approximate similarities calculated between encoded records. Our attack matches nodes in a similarity graph generated from an encoded database with a corresponding similarity graph generated from a plain-text database to re-identify sensitive values. Our attack is not limited to any specific PPRL method, and in an experimental evaluation we apply it on three PPRL encoding methods using three different databases. This evaluation shows that our attack can successfully re-identify sensitive values from these encodings with high accuracy where no previous attack on PPRL would have been successful.

Privacy-preserving record linkage (PPRL) is the process of identifying records that correspond to the same entities across several databases without revealing any sensitive information about these entities. One popular PPRL technique is Bloom filter (BF) encoding, with first applications of BF based PPRL now being employed in real-world linkage applications. Here we present a cryptanalysis attack that can re-identify attribute values encoded in BFs. Our method applies maximal frequent itemset mining on a BF database to first identify sets of frequently co-occurring bit positions that correspond to encoded frequent q-grams (character substrings extracted from plain-text values). Using a language model, we then identify additional q-grams by applying pattern mining on subsets of BFs that encode a previously identified frequent q-gram. Experiments on a real database show that our attack can successfully re-identify sensitive values even when each BF in a database is unique.

Being able to identify records that correspond to the same entity across diverse databases is an increasingly important step in many data analytics projects. Research into privacy-preserving record linkage (PPRL) aims to develop techniques that can link records across databases such that besides the record pairs classified as matches no sensitive information about the entities in these databases is revealed. A popular technique used in PPRL is to encode sensitive values into Bloom filters (bit vectors), which has the advantage of allowing approximate matching using character q-grams. PPRL based on Bloom filter encoding has been shown to be accurate and scalable to large databases, and is thus now being used in real-world PPRL systems in Australia, Canada, and the UK. However, recent studies have shown that Bloom filters used for PPRL are vulnerable to cryptanalysis attacks that can re-identify some of the sensitive values encoded in these Bloom filters. While previous such attack methods were slow and required knowledge of various encoding parameters, we present a novel efficient attack which exploits how attribute values are encoded into Bloom filters. Our attack method does not require knowledge of the encoding function or its parameter settings used. It is able to correctly re-identify with high precision q-grams that could not have been hashed to certain Bloom filter bit positions, and using these re-identified q-grams it can then re-identify attribute values with high precision. Our method is significantly faster than earlier PPRL cryptanalysis attacks, and in our experimental evaluation, it is able to successfully re-identify attribute values from large real-world databases in a few minutes.