| With the rapid development of information technology, massive data collection is relatively easier and cheaper than ever before. Thus, the efficient and safe exchange of information becomes the renewed focus of database management as a pervasive issue. The challenge we face today is to provide users with reliable and useful data while protecting the privacy of confidential information contained in the database.; Our research concentrates on statistical databases, which usually store a large number of data records and are open to the public where users are allowed to ask only limited types of queries, such as Sum, Count and Mean. Responses for those queries are aggregate statistics that intends to prevent disclosing the identity of a unique record in the database.; My dissertation aims to analyze these problems from a new perspective using Probably Approximately Correct (PAC) learning theory which attempts to discover the true function by learning from examples. Different from traditional methods from which database administrators apply security methods to protect the privacy of statistical databases, we regard the true database as the target concept that an adversary tries to discover using a limited number of queries, in the presence of some systematic perturbations of the true answer. We extend previous work and classify a new data perturbation method---the variable data perturbation which protects the database by adding random noises to the confidential field. This method uses a parametrically driven algorithm that can be viewed as generating random perturbations by some (unknown) discrete distribution with known parameters, such as the mean and standard deviation. The bounds we derive for this new method shows how much protection is necessary to prevent the adversary from discovering the database with high probability at small error. Put in PAC learning terms we derive bounds on the amount of error an adversary makes given a general perturbation scheme, number of queries and a confidence level. |
