  In this paper, we study the problem of privacy-preserving data sharing,
wherein only a subset of the records in a database are sensitive, possibly
based on predefined privacy policies. Existing solutions, viz, differential
privacy (DP), are over-pessimistic and treat all information as sensitive.
Alternatively, techniques, like access control and personalized differential
privacy, reveal all non-sensitive records truthfully, and they indirectly leak
information about sensitive records through exclusion attacks.
  Motivated by the limitations of prior work, we introduce the notion of
one-sided differential privacy (OSDP). We formalize the exclusion attack and we
show how OSDP protects against it. OSDP offers differential privacy like
guarantees, but only to the sensitive records. OSDP allows the truthful release
of a subset of the non-sensitive records. The sample can be used to support
applications that must output true data, and is well suited for publishing
complex types of data, e.g. trajectories. Though some non-sensitive records are
suppressed to avoid exclusion attacks, our experiments show that the
suppression results in a small loss in utility in most cases. Additionally, we
present a recipe for turning DP mechanisms for answering counting queries into
OSDP techniques for the same task. Our OSDP algorithms leverage the presence of
non-sensitive records and are able to offer up to a 25x improvement in accuracy
over state-of-the-art DP-solutions.
