Locality-Sensitive Hashing Does Not Guarantee Privacy! Attacks on Google's FLoC and the MinHash Hierarchy System
Authors: Florian Turati (ETH Zurich), Karel Kubicek (ETH Zurich), Carlos Cotrini (ETH Zurich), David Basin (ETH Zurich)
Volume: 2023
Issue: 4
Pages: 117–131
DOI: https://doi.org/10.56553/popets-2023-0101
Abstract: Recently proposed systems aim at achieving privacy using locality-sensitive hashing. We show how these approaches fail by presenting attacks against two such systems: Google's FLoC proposal for privacy-preserving targeted advertising and the MinHash Hierarchy, a system for processing location trajectories in a privacy-preserving way. Our attacks refute the pre-image resistance, anonymity, and privacy guarantees claimed for these systems. In the case of FLoC, we show how to deanonymize users using Sybil attacks and to reconstruct 10% or more of the browsing history for 30% of its users using Generative Adversarial Networks. We achieve this only analyzing the hashes used by FLoC. For MinHash, we precisely identify the location trajectory of a subset of individuals and, on average, we can limit users' trajectory to just 10% of the possible geographic area, again using just the hashes. In addition, we refute their differential privacy claims.
Keywords: LSH, FLoC, MinHash, SimHash, Privacy
Copyright in PoPETs articles are held by their authors. This article is published under a Creative Commons Attribution 4.0 license.
