TL;DR
This paper presents a scathing technical critique of the European Commission’s (EC) proposed anonymization measures for Google Search data under the Digital Markets Act (DMA). By conducting a re-identification exercise on real-world datasets, the authors demonstrate that the EC’s heuristic-based approach fails to prevent record linkage and identity disclosure, effectively leaving users "anonymous in name only."
What Problem Does This Paper Address?
Under Article 6(11) of the DMA, "gatekeepers" like Alphabet (Google) are required to share search, click, and view data with competing search engines to level the playing field. However, this data must be anonymized to protect user privacy under the GDPR.
The EC recently proposed a specific methodology for this anonymization, involving Named Entity Recognition (NER) to strip identifiers, frequency-based "allow lists," and length-based query suppression. The authors argue that these measures are fundamentally flawed because they rely on unjustified heuristics rather than formal privacy guarantees (like $k$-anonymity or differential privacy). The core challenge is whether these measures actually meet the legal standard of anonymization—where a data subject is "no longer identifiable"—or if they merely provide a false sense of security.
Methods
The authors performed a critical review and an empirical "re-identification exercise." Their approach involved:
- Technical Analysis: Deconstructing the EC’s proposed thresholds (e.g., the 50-user entity threshold and the 95th-percentile length cap) to show how they fail to account for the joint uniqueness of attributes.
- Attack Pattern Design: Developing four reproducible and automatable attack patterns:
- Self-queries: Searching for patterns like "my name is [Name]" which often escape NER if the name is malformed or contains common words.
- Email/Identifier Leakage: Using regular expressions to find malformed email addresses or phone numbers that bypassed standard detectors.
- Geospatial Linkage: Exploiting Irish "Eircodes" (postal codes) to identify private residences and link multiple queries to a single household.
- Metadata Linkage: Using rare combinations of language and date (e.g., Icelandic queries in Ireland) to cluster records belonging to a single individual.
- Automation with LLMs: Using the Google Gemini API to rank and filter unique queries to identify those most likely to contain high-certainty identifying information.
Datasets
The study utilized six-month samples of real Google Search data (March to August 2026) provided by Alphabet, which had been processed according to the EC’s proposed technical measures.
- Ireland Dataset: 4.87 million search records.
- Spain Dataset: 34.62 million search records.
- Allow Lists: The authors also had access to the monthly updated "allow lists" used by the EC's methodology to validate their findings.
Key Insights and Ideas
- The Curse of Joint Uniqueness: The EC evaluates query components in isolation. The authors show that while individual words might be common, their combination with metadata (location, device, day-level timestamp) makes 44% of search records unique.
- NER is Not a Silver Bullet: Named Entity Recognizers are imperfect. The authors found that simple variations in spacing or capitalization allowed sensitive identifiers like Eircodes and phone numbers to pass through the filters.
- The "AI Mode" Conflict: The EC requires the inclusion of "AI mode" queries (conversational prompts). These are naturally longer and more descriptive, making them highly disclosive. The EC's arbitrary length-based threshold will either suppress these useful queries (destroying utility) or fail to protect them if the threshold is raised.
- Allow List Manipulation: The authors describe a "targeted attack" where an adversary could use as few as 13 phone numbers to create enough fake accounts to force a specific rare identifier (like a target's passport number) onto the "allow list," ensuring it isn't suppressed in future data releases.
- Legal Inadequacy: The authors argue that the EC’s reliance on contractual safeguards (prohibiting recipients from re-identifying) admits that the technical measures are insufficient. Under GDPR, if the data can be re-identified with "means reasonably likely to be used," it is not anonymous.
Key Results
- Successful Re-identification: In a sample of 100 "self-search" queries in Spain, the authors achieved a 10% success rate in unequivocally re-identifying private individuals using only public sources like LinkedIn and Facebook.
- Sensitive Data Exposure: The "anonymized" data contained queries revealing special category data under GDPR, including mental health conditions, sentimental life details, and requests to help forge documents (diplomas/medical leaves).
- Linkage Success: By filtering for minority languages (Icelandic), the authors linked ~50 unique queries to a single traveler in Ireland, building a detailed profile of their interests, health concerns, and movements.
- Failure of EDPB Criteria: The paper concludes that the EC measures fail all three European Data Protection Board criteria for anonymization: No Isolation (44% of records are unique), No Linkage (records were easily linked via Eircodes and language), and No Inference (sensitive attributes were easily inferred).
Limitations and Future Work
The authors acknowledge that their manual verification was limited to small subsets (e.g., the top 100 ranked records for certain patterns). They suggest that a motivated adversary with more resources or access to non-public databases (like property registries) could achieve much higher re-identification rates.
Future work could involve exploring how formal privacy models, such as $k$-anonymity via microaggregation or Differential Privacy, could be applied to search data to provide the "privacy-first" approach that the EC currently lacks.
Summary updated