An epistemic framework for privacy protection in database linking

In this paper, we present an epistemic framework for privacy protection in the database linking context, whereby the user’s knowledge and the individuals’ confidential information are represented by propositional sentences. In the framework, the concept of safety is rigorously defined, and an effective approach for testing the safety of released data is provided. It is shown that some generalization operations can be applied to original data to make it less specific so that the release of generalized data does not violate privacy. Two kinds of generalization operation are considered: attribute-oriented generalization (AOG) and cell-oriented generalization (COG). AOG is more restrictive, but a bottom-up search algorithm can be used to find the maximally informative AOG that satisfies the safety requirement. We investigate the properties of AOG that can be used to improve the search efficiency. COG, on the other hand, is more flexible. However, it necessitates searching through the whole space, so its computational complexity is much higher. Although graph theory can be used to simplify the search procedure, heuristic methods are needed to improve its efficiency. Easy extensibility is one of the main advantages of our framework. It is shown that the framework can be extended to accommodate probabilistic inference attacks and alternative protection techniques.