Inference-Proof Database Instances for Controlled Query Evaluation

Controlled Query Evaluation (CQE) defines a logical framework to protect confidential information in a database. By representing a user's a priori knowledge appropriately, a CQE system not only controls access to certain database entries but also accounts for information inferred by the user.

This talk covers a novel constituent of CQE: it presents an algorithm devised to compute an inference-proof instance out of an unprotected input instance, a security policy and the representation of a user's knowledge.

The inference-proof instance formally guarantees confidentiality of the security policy entries and hence all user queries can truthfully be answered by the database. It is owed to this fact that query evaluation on the inference-proof instance does not incur any performance degradation.

Due to undecidability of the general first-order case, appropriate fragments of first-order logic for the security policy and the user knowledge representation are analyzed. The due proofs of refutation soundness engage a version of Herbrand's theorem with semantic trees