Team for Research in
Ubiquitous Secure Technology

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%20Case%20Background.pdf · application/pdf · 203 kbytes

• 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.
Groups: trust
For additional information, see the Publications FAQ or contact webmaster at www truststc org.