Team for Research in
Ubiquitous Secure Technology

Citation
Shubha U. Nabar, Bhaskara Marthi, Krishnaram Kenthapadi, Nina Mishra, Rajeev Motwani. "Towards Robustness in Query Auditing". Proceedings of the 32nd International Conference on Very Large Data Bases (VLDB), September, 2006.

Abstract
We consider the online query auditing problem for statistical databases. Given a stream of aggregate queries posed over sensitive data, when should queries be denied in order to protect the privacy of individuals? We construct efficient auditors for max queries and bags of max and min queries in both the partial and full disclosure settings. Our algorithm for the partial disclosure setting involves a novel application of probabilistic inference techniques that may be of independent interest. We also study for the first time, a particular dimension of the utility of an auditing scheme and obtain initial results for the utility of sum auditing when guarding against full disclosure. The result is positive for large databases, indicating that answers to queries will not be riddled with denials.

Electronic downloads

• robustnessQueryAuditing.pdf · application/pdf · 251 kbytes

• HTML

  Shubha U. Nabar, Bhaskara Marthi, Krishnaram Kenthapadi,
  Nina Mishra, Rajeev Motwani. <a
  href="http://www.truststc.org/pubs/105.html"
  >Towards Robustness in Query Auditing</a>,
  Proceedings of the 32nd International Conference on Very
  Large Data Bases (VLDB), September, 2006.

• Plain text

  Shubha U. Nabar, Bhaskara Marthi, Krishnaram Kenthapadi,
  Nina Mishra, Rajeev Motwani. "Towards Robustness in
  Query Auditing". Proceedings of the 32nd International
  Conference on Very Large Data Bases (VLDB), September, 2006.

• BibTeX

  @inproceedings{NabarMarthiKenthapadiMishraMotwani06_TowardsRobustnessInQueryAuditing,
      author = {Shubha U. Nabar, Bhaskara Marthi, Krishnaram
                Kenthapadi, Nina Mishra, Rajeev Motwani},
      title = {Towards Robustness in Query Auditing},
      booktitle = {Proceedings of the 32nd International Conference
                on Very Large Data Bases (VLDB)},
      month = {September},
      year = {2006},
      abstract = {We consider the online query auditing problem for
                statistical databases. Given a stream of aggregate
                queries posed over sensitive data, when should
                queries be denied in order to protect the privacy
                of individuals? We construct efficient auditors
                for max queries and bags of max and min queries in
                both the partial and full disclosure settings. Our
                algorithm for the partial disclosure setting
                involves a novel application of probabilistic
                inference techniques that may be of independent
                interest. We also study for the first time, a
                particular dimension of the utility of an auditing
                scheme and obtain initial results for the utility
                of sum auditing when guarding against full
                disclosure. The result is positive for large
                databases, indicating that answers to queries will
                not be riddled with denials.},
      URL = {http://www.truststc.org/pubs/105.html}
  }
  

Posted by Krishnaram Kenthapadi on 8 Jul 2006.
For additional information, see the Publications FAQ or contact webmaster at www truststc org.