Query Auditing Against Partial Disclosure

Date

2009-09-16T18:16:56Z

Authors

Journal Title

Journal ISSN

Volume Title

Publisher

Computer Science & Engineering

Abstract

Many government agencies, businesses, and nonprofit organizations need to collect, analyze, and report data about individuals in order to support their short-term and long-term planning activities. Statistical Databases therefore contain confidential information such as income, credit ratings, type of disease, or test scores of individuals. Such data are typically stored online and analyzed using sophisticated database management systems (DBMS) and software packages. On one hand, such database systems are expected to satisfy user requests of aggregate statistics related to non-confidential and confidential attributes. On the other hand, the system should be secure enough to guard against a user's ability to infer any confidential information related to a specific individual represented in the database. A major privacy threat is the adversarial inference of individual (private) tuples from aggregate query answers. Most existing work focuses on the exact disclosure problem, which is inadequate in practice. We propose a novel auditing algorithm for defending against partial disclosure. We introduce ENTROPY-AUDITING, an efficient query-auditing algorithm for partial disclosure that supports a mixture of common aggregate functions. In particular, we classify aggregate functions into two categories: MIN-like (e.g., MIN and MAX) and SUM-like (e.g., SUM and MEDIAN), and support a combination of them. Our proposed scheme utilizes an exact-auditing algorithm as a primitive function, and supports a combination of queries with various aggregate functions (e.g., SUM, MIN, MAX). We also present a detailed experimental evaluation of our PARTIAL-AUDITING approach.

Description

Keywords

Citation