  Quasi-identifier-based deidentification techniques (QI-deidentification) are
widely used in practice, including $k$-anonymity, $\ell$-diversity, and
$t$-closeness. We present three new attacks on QI-deidentification: two
theoretical attacks and one practical attack on a real dataset. In contrast to
prior work, our theoretical attacks work even if every attribute is a
quasi-identifier. Hence, they apply to $k$-anonymity, $\ell$-diversity,
$t$-closeness, and most other QI-deidentification techniques.
  First, we introduce a new class of privacy attacks called downcoding attacks,
and prove that every QI-deidentification scheme is vulnerable to downcoding
attacks if it is minimal and hierarchical. Second, we convert the downcoding
attacks into powerful predicate singling-out (PSO) attacks, which were recently
proposed as a way to demonstrate that a privacy mechanism fails to legally
anonymize under Europe's General Data Protection Regulation. Third, we use
LinkedIn.com to reidentify 3 students in a $k$-anonymized dataset published by
EdX (and show thousands are potentially vulnerable), undermining EdX's claimed
compliance with the Family Educational Rights and Privacy Act.
  The significance of this work is both scientific and political. Our
theoretical attacks demonstrate that QI-deidentification may offer no
protection even if every attribute is treated as a quasi-identifier. Our
practical attack demonstrates that even deidentification experts acting in
accordance with strict privacy regulations fail to prevent real-world
reidentification. Together, they rebut a foundational tenet of
QI-deidentification and challenge the actual arguments made to justify the
continued use of $k$-anonymity and other QI-deidentification techniques.
