Secure XML Publishing without Information Leakage in the Presence of Data Inference (Full Version

Recent applications are seeing an increasing need that publishing XML documents should meet precise security requirements. In this pa-per, we consider data-publishing applications where the publisher species what information is sensitive and should be protected. We show that if a partial document is published care-lessly, users can use common knowledge (e.g., \all patients in the same ward have the same disease") to infer more data, which can cause leakage of sensitive information. The goal is to protect such information in the presence of data inference with common knowledge. We consider common knowledge represented as semantic XML constraints. We formulate the process how users can infer data using three types of common XML constraints. In-terestingly, no matter what sequences users follow to infer data, there is a unique, max-imal document that contains all possible in-ferred documents. We develop algorithms for nding a partial document of a given XML document without causing information leak-age, while allowing publishing as much data as possible. Our experiments on real data sets show that eect of inference on data security, and how the proposed techniques can prevent such leakage from happening. Work partially done during a visit to UC Irvine and par-tially supported by NSF China No. 60173051