Abstract
The Australian Bureau of Statistics (ABS) is tasked with integrating large-scale datasets, such as the 2016 Census, with various administrative records while upholding a public commitment to privacy. A key component of this strategy involves the destruction of plaintext names and the use of "irreversible" cryptographic hashes. This paper provides a cryptographic evaluation of various name-encoding methods for Privacy-Preserving Record Linkage (PPRL). We demonstrate that simple cryptographic hashing is insufficient for protecting low-entropy data like names and recommend the use of HMAC-based identifiers derived from attribute subsets as a robust, high-performance alternative.
The Problem: The Hashing Fallacy
In the context of data linkage, names are considered "low entropy" data. In Australia, there are fewer than 400,000 common surnames, a pool small enough to be vulnerable to brute-force dictionary attacks. Furthermore, deterministic encoding preserves the underlying frequency distribution of the data. If "Smith" is the most common surname in a dataset, the most common hash will inevitably represent "Smith," allowing for straightforward frequency analysis attacks.
The challenge for the ABS is to find an encoding method that supports "fuzzy matching"—accounting for typographical errors and variations—without leaving the data vulnerable to re-identification in the event of a data breach.
Methodological Evaluation
The authors analyzed five primary options for secure data linkage:
- Public-key Encryption: Encrypting names so only the authorized "Linker" can access them. While simple, this method relies entirely on the security of the private key.
- Lossy Encoding: Mapping multiple names to a single "bucket" (e.g., using only initials). While highly irreversible, this method significantly degrades linking accuracy.
- HMAC-based Linkage Identifiers (The Recommended Path): Utilizing a secret key to generate multiple hashes based on different combinations of attributes (e.g.,
HMAC(First Name + DoB + Postcode)). This approach "smooths" the data distribution, making frequency attacks significantly more difficult. - Individual IDs: Assigning a unique, encrypted identifier to every individual prior to the linkage process.
- Homomorphic Encryption and Secure Multi-Party Computation (SMC): Performing mathematical operations on encrypted data without decryption. While this is the "gold standard" for privacy, it remains computationally intensive.
Notably, the paper critiques Bloom Filters, a common technique in PPRL literature, arguing that they are frequently implemented insecurely and remain highly susceptible to frequency analysis.
Experimental Design and Synthetic Data
To test these methods without compromising sensitive Census data, the authors developed a Synthetic Data Generator tailored to the Australian population. The dataset included:
- MBS Demographics: 29 million records incorporating Year of Birth (YOB) and Gender.
- Surnames: A list of 384,370 Australian last names with realistic frequency distributions.
- First Names: The top 100 names for boys and girls in NSW from 1952–2015.
- Geography: 2011 Census "mesh block" data for fine-grained location uniqueness.
- Distortions: Manual introduction of "noise," such as typos, gender swaps, and transposed names, to test the robustness of fuzzy matching algorithms.
Key Insights and Results
The empirical testing focused on Option 3 (HMAC on attribute subsets), yielding several critical insights:
- Privacy through Uniqueness: Counter-intuitively, including more identifying information (like birth year or mesh block) in a hash can increase privacy. By making the hash input more unique, the frequency distribution is flattened, neutralizing frequency attacks. Most attribute combinations tested were 99.99% unique.
- High Accuracy: Using a "voting" method across multiple attribute-subset hashes, the researchers achieved near 100% precision and recall, even in the presence of data distortions.
- Superior Performance: On a standard multi-core desktop, the system linked 2.9 million records in under 15 minutes. Traditional cross-comparison methods would have required over six days to complete the same task.
Limitations and Future Directions
While HMAC-based identifiers offer a pragmatic solution, the study identifies several limitations. All feasible methods currently require a "Trusted Linker"—a central entity or machine that holds the secret keys. This remains a single point of failure. Additionally, the success of attribute-subset hashing depends on the consistency and formatting of attributes across disparate datasets.
While Homomorphic Encryption and SMC represent the future of privacy-preserving linkage, they are currently too computationally expensive for the ABS's immediate requirement to process tens of millions of records. For now, HMAC-based identifiers derived from attribute subsets provide the most viable balance of privacy, accuracy, and operational efficiency.
Summary updated