Team for Research in
Ubiquitous Secure Technology

l-Diversity: Privacy beyound k-Anonymity
Ashwin Machanavajjhala, Daniel Kifer, Johannes Gehrke, Muthuramakrishnan Venkitasubramaniam

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

Citation formats  
  • 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.

Notice: This material is presented to ensure timely dissemination of scholarly and technical work. Copyright and all rights therein are retained by authors or by other copyright holders. All persons copying this information are expected to adhere to the terms and constraints invoked by each author's copyright.