Vincent Toubiana of Alcatel-Lucent Bell Labs and Helen Nissenbaum of New York University have published an article, “An Analysis of Google Logs Retention Policies,” in the Journal of Privacy and Confidentiality (2011): Vol. 3: Iss. 1, Article 2. Here’s the Abstract:
To preserve search log data utility, Google groups search queries in log bundles by deleting the last octet of logged IP address. Because these bundles still contain identifying information, part of these search logs can be de-anonymized [Jones et al., 2008]. Without an external audit of these search logs, it is currently impossible to evaluate their robustness against de-anonymizing attacks. In this paper, we leverage log retention policy ambiguities to show that quasi-identifiers could be stored in sanitized search query logs and could help to de-anonymize user searches. This paper refers to Google Search and Google Suggest log retention policies and shows that even with the highest degree of anonymization that Google offers, one could separate user queries with a high granularity. Because Google Suggest is queried every time a user types a character in the Google Chrome navigation box, the privacy of Chrome users could be compromised with respect to their browsing histories. Such ambiguities within log retention policies are critical and should be addressed, as anonymized logs could be shared with third parties without prior user consent.
You can download the article from CMU.