Citation
David Martin, Daniel Kifer, Ashwin Machanavajjhala, Johannes Gehrke, Joseph Y. Halpern. "Worst-Case Backgrond Knowledge for Privacy-Preserving Data Publishing". International Conference on Data Engineering 2007: 126-135, Cornell University Comuputer Science Department, Cornell, USA, 10, February, 2007.

Abstract
Recent work has shown the necessity of considering an attacker’s background knowledge when reasoning about privacy in data publishing. However, in practice, the data publisher does not know what background knowledge the attacker possesses. Thus, it is important to consider the worst-case. In this paper, we initiate a formal study of worst-case background knowledge. We propose a language that can express any background knowledge about the data. We provide a polynomial time algorithm to measure the amount of disclosure of sensitive information in the worst case, given that the attacker has at most k pieces of information in this language. We also provide a method to efficiently sanitize the data so that the amount of disclosure in the worst case is less than a specified threshold.

Electronic downloads

• Worse Case Background.pdf · application/pdf · 203 kbytes

Citation formats

• HTML

  David Martin, Daniel Kifer, Ashwin Machanavajjhala, Johannes
  Gehrke, Joseph Y. Halpern. <a
  href="http://www.truststc.org/pubs/464.html">Worst-Case
  Backgrond Knowledge for Privacy-Preserving Data
  Publishing</a>, International Conference on Data
  Engineering 2007: 126-135, Cornell University Comuputer
  Science Department, Cornell, USA, 10, February, 2007.

• Plain text

  David Martin, Daniel Kifer, Ashwin Machanavajjhala, Johannes
  Gehrke, Joseph Y. Halpern. "Worst-Case Backgrond Knowledge
  for Privacy-Preserving Data Publishing". International
  Conference on Data Engineering 2007: 126-135, Cornell
  University Comuputer Science Department, Cornell, USA, 10,
  February, 2007.

• BibTeX

  @inproceedings{MartinKiferMachanavajjhalaGehrkeHalpern07_WorstCaseBackgrondKnowledgeForPrivacyPreservingData,
      author = {David Martin and Daniel Kifer and Ashwin
                Machanavajjhala and Johannes Gehrke and Joseph Y.
                Halpern},
      title = {Worst-Case Backgrond Knowledge for
                Privacy-Preserving Data Publishing},
      booktitle = {International Conference on Data Engineering 2007:
                126-135},
      organization = {Cornell University Comuputer Science Department,
                Cornell, USA},
      pages = {10},
      month = {February},
      year = {2007},
      abstract = {Recent work has shown the necessity of considering
                an attacker’s background knowledge when
                reasoning about privacy in data publishing.
                However, in practice, the data publisher does not
                know what background knowledge the attacker
                possesses. Thus, it is important to consider the
                worst-case. In this paper, we initiate a formal
                study of worst-case background knowledge. We
                propose a language that can express any background
                knowledge about the data. We provide a polynomial
                time algorithm to measure the amount of disclosure
                of sensitive information in the worst case, given
                that the attacker has at most k pieces of
                information in this language. We also provide a
                method to efficiently sanitize the data so that
                the amount of disclosure in the worst case is less
                than a specified threshold.},
      URL = {http://www.truststc.org/pubs/464.html}
  }
  

Posted by Johannes Gehrke on 26 Aug 2008.
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.