How Anonymous are Search Engine Queries? Quantifying the Risk to Privacy in Search Engine Query Logs and Protecting Exposure of Personally Identifiable Information in Them

Search query logs are invaluable for scientific research, particularly in the medical domain, yet they pose significant privacy risks through the potential exposure of Personally Identifiable Information (PII). This work addresses the dual challenge of quantifying PII vulnerability and evaluating effective anonymization strategies to prevent these vulnerabilities. We collected search query logs and PII information of 11 attributes from 19 consenting participants. Human analysts and an offline Large Language Model (LLM) attempted to identify the PII from the query logs. Our findings show that some PII values are easily identified (e.g., age group, which was identified in 67% of cases) but others, such as participant name, are much more difficult, though the risk is non-negligible (8%). Notably, human analysts exhibit significant inconsistency in the PII they were able to infer. The LLM reached identification results that were statistically indistinguishable from those of human analysts, and both were statistically significant better than classic Named-Entity Recognition methods. We tested the ability to hinder identification of PII through two techniques: Sanitization (data removal) and Obfuscation (noise addition). While the former did not provide statistically significant reductions in identification of PII, the latter did. Specifically, the Dissimilar Addition method, where queries from a user with dissimilar PII values were injected, achieved a statistically significant reduction in identification accuracy (absolute reduction of 18%) while requiring significantly fewer data modifications than the best sanitization techniques. These findings indicate that effectively anonymizing query logs requires masking the signal rather than simple data suppression. Our work shows that query logs reveal some PII values, but that these can be masked to a certain extent using appropriate techniques. This opens the way to protecting privacy in query logs with minimal effect on the utility of the logs and, more broadly, to the development and testing of new deidentification methods.