TL;DR
This paper reveals critical privacy vulnerabilities in the UK Office for National Statistics' (ONS) "Beyond 2011" privacy-preserving record linkage (PPRL) approach. The authors demonstrate that combining pseudonymisation with similarity tables, as proposed by ONS, is not secure and can be exploited to recover sensitive personal data, even within a controlled environment.
What Problem Does This Paper Address?
The paper addresses the challenge of preserving individual privacy while enabling record linkage, a crucial task for statistical analysis and public services. Specifically, it scrutinizes the ONS's "Beyond 2011" initiative, which aimed to link datasets using pseudonymisation and similarity tables. The core problem is to determine if this proposed method genuinely protects data privacy against sophisticated attacks, especially when deployed outside of highly controlled environments. The authors question the ONS's claims of security and investigate whether their approach is robust enough to prevent re-identification of individuals.
Methods
The authors' methodology involves a critical analysis of the ONS's published "Beyond 2011" reports, focusing on the cryptographic assumptions and techniques employed. They dissect the use of cryptographic hash functions and HMACs (Hash-based Message Authentication Codes), highlighting incorrect assumptions about their one-way properties and the critical role of key entropy. A significant portion of their analysis involves simulating attacks on the proposed similarity table approach. This includes:
- Frequency Attacks: Exploiting the non-uniform distribution of common names (e.g., "Smith") to infer identities from HMACs.
- Similarity Leakage: Demonstrating how plaintext similarity scores in the tables can be used as an index to recover names, even without knowing the HMAC keys.
- Graph Isomorphism: Modeling the similarity table as a graph where nodes are HMAC'd names and edges represent similarity scores. They then explore subgraph isomorphism techniques to match known (potentially partial) name graphs to the larger similarity table graph, thereby recovering plaintext names.
Datasets
The paper does not introduce new datasets but uses publicly available information for its analysis and simulations. Specifically, it mentions using:
- A list of Australian last names (approximately 351,070 names) to calculate similarity tables and test the graph isomorphism attack.
- The ONS's own similarity tables (as described in their reports) are the primary target of the analysis.
Key Insights and Ideas
- HMACs are not a silver bullet: The paper emphasizes that HMACs, while offering some protection against dictionary attacks compared to simple hashes, are highly dependent on the secrecy and entropy of the key. Predictable keys render HMACs almost as vulnerable as hashes.
- Similarity tables are a major privacy leak: The core finding is that providing plaintext similarity scores alongside HMAC'd names creates a direct pathway for re-identification. This is because these scores can be recalculated and used to index into the HMACs.
- Frequency attacks are potent: Common names, when HMAC'd, can be identified through frequency analysis, especially when combined with similarity scores.
- Graph isomorphism offers a powerful attack vector: By treating the similarity table as a graph, attackers can use subgraph isomorphism to match known name structures to the table, enabling large-scale recovery of names. This attack is effective even with partial knowledge of the similarity table.
- Cryptographic terminology matters: The authors highlight how misusing terms like "hash function" and "one-way function" leads to flawed security analyses and overconfident claims about data protection.
Key Results
- The authors demonstrate that over 56% of similarity score sets in a sample Australian name list were unique, allowing for direct recovery of corresponding names.
- When combining frequency attacks with similarity tables, they show how a single common name (like "Smith") can lead to the recovery of many related names.
- Through their graph isomorphism simulation, they found that even with only 40% of the similarity table known, they could recover 69% of names. With 90% knowledge, recovery reached 91%.
- The paper concludes that the ONS's approach is susceptible to practical attacks and that its security is primarily derived from the strict controls of the Statistical Research Environment (SRE), not the cryptographic methods themselves.
Limitations and Future Work
- Limited access to ONS data: The analysis is based solely on the ONS's published reports and methods, not on direct access to their data or the SRE. This means the findings are theoretical but based on the described implementation.
- Simplistic attack implementation: The authors acknowledge that their subgraph matching algorithm is "simplistic and far from exhaustive" and heavily optimized for performance. They suggest several avenues for improvement:
- Probabilistic matching: Incorporating probabilities to estimate matches more accurately.
- Deeper evaluation: Exploring connections beyond a depth of one in the similarity graph.
- Evaluating incoming links: Considering incoming edges in addition to outgoing ones for labeling nodes.
- Future work recommendations: The authors recommend reviewing procedural protections around the SRE, correcting incorrect statements about HMAC key entropy, updating terminology for clarity, and crucially, not using the similarity table technique outside of an SRE.
Summary updated