Team for Research in
Ubiquitous Secure Technology

Citation
Ashwin Machanavajjhala, Daniel Kifer, Johannes Gehrke, Muthuramakrishnan Venkitasubramaniam. "l-Diversity: Privacy beyound k-Anonymity". Cornell University, pp. 52, March 2007.

Abstract
Publishing data about individuals without revealing sensitive information about them is an important problem. In recent years, a new definition of privacy called k-anonymity has gained popularity. In a k-anonymized dataset, each record is indistinguishable from at least k −1 other records with respect to certain identifying attributes. In this article, we show using two simple attacks that a k-anonymized dataset has some subtle but severe privacy problems. First, an attacker can discover the values of sensitive attributes when there is little diversity in those sensitive attributes. This is a known problem. Second, attackers often have background knowledge, and we show that k-anonymity does not guarantee privacy against attackers using background knowledge. We give a detailed analysis of these two attacks, and we propose a novel and powerful privacy criterion called -diversity that can defend against such attacks. In addition to building a formal foundation for -diversity,we show in an experimental evaluation that -diversity is practical and can be implemented efficiently.

Electronic downloads

• L%20Diversity%20Privacy.pdf · application/pdf · 819 kbytes

• HTML

  Ashwin Machanavajjhala, Daniel Kifer, Johannes Gehrke,
  Muthuramakrishnan Venkitasubramaniam. <a
  href="http://www.truststc.org/pubs/465.html"
  >l-Diversity: Privacy beyound k-Anonymity</a>,
  <i>Cornell University</i>, pp. 52, March 2007.

• Plain text

  Ashwin Machanavajjhala, Daniel Kifer, Johannes Gehrke,
  Muthuramakrishnan Venkitasubramaniam. "l-Diversity:
  Privacy beyound k-Anonymity". <i>Cornell
  University</i>, pp. 52, March 2007.

• BibTeX

  @article{MachanavajjhalaKiferGehrkeVenkitasubramaniam07_LDiversityPrivacyBeyoundKAnonymity,
      author = {Ashwin Machanavajjhala and Daniel Kifer and
                Johannes Gehrke and Muthuramakrishnan
                Venkitasubramaniam},
      title = {l-Diversity: Privacy beyound k-Anonymity},
      journal = {Cornell University},
      pages = {52},
      month = {March},
      year = {2007},
      abstract = {Publishing data about individuals without
                revealing sensitive information about them is an
                important problem. In recent years, a new
                definition of privacy called k-anonymity has
                gained popularity. In a k-anonymized dataset, each
                record is indistinguishable from at least k −1
                other records with respect to certain identifying
                attributes. In this article, we show using two
                simple attacks that a k-anonymized dataset has
                some subtle but severe privacy problems. First, an
                attacker can discover the values of sensitive
                attributes when there is little diversity in those
                sensitive attributes. This is a known problem.
                Second, attackers often have background knowledge,
                and we show that k-anonymity does not guarantee
                privacy against attackers using background
                knowledge. We give a detailed analysis of these
                two attacks, and we propose a novel and powerful
                privacy criterion called -diversity that can
                defend against such attacks. In addition to
                building a formal foundation for -diversity,we
                show in an experimental evaluation that
                -diversity is practical and can be implemented
                efficiently.},
      URL = {http://www.truststc.org/pubs/465.html}
  }
  

Posted by Johannes Gehrke on 26 Aug 2008.
Groups: trust
For additional information, see the Publications FAQ or contact webmaster at www truststc org.