  Simply restricting the computation to non-sensitive part of the data may lead
to inferences on sensitive data through data dependencies. Inference control
from data dependencies has been studied in the prior work. However, existing
solutions either detect and deny queries which may lead to leakage -- resulting
in poor utility, or only protects against exact reconstruction of the sensitive
data -- resulting in poor security. In this paper, we present a novel security
model called full deniability. Under this stronger security model, any
information inferred about sensitive data from non-sensitive data is considered
as a leakage. We describe algorithms for efficiently implementing full
deniability on a given database instance with a set of data dependencies and
sensitive cells. Using experiments on two different datasets, we demonstrate
that our approach protects against realistic adversaries while hiding only
minimal number of additional non-sensitive cells and scales well with database
size and sensitive data.
