  In this paper, we define noiseless privacy, as a non-stochastic rival to
differential privacy, requiring that the outputs of a mechanism (i.e., function
composition of a privacy-preserving mapping and a query) can attain only a few
values while varying the data of an individual (the logarithm of the number of
the distinct values is bounded by the privacy budget). Therefore, the output of
the mechanism is not fully informative of the data of the individuals in the
dataset. We prove several guarantees for noiselessly-private mechanisms. The
information content of the output about the data of an individual, even if an
adversary knows all the other entries of the private dataset, is bounded by the
privacy budget. The zero-error capacity of memory-less channels using
noiselessly private mechanisms for transmission is upper bounded by the privacy
budget. The performance of a non-stochastic hypothesis-testing adversary is
bounded again by the privacy budget. Finally, assuming that an adversary has
access to a stochastic prior on the dataset, we prove that the estimation error
of the adversary for individual entries of the dataset is lower bounded by a
decreasing function of the privacy budget. In this case, we also show that the
maximal information leakage is bounded by the privacy budget. In addition to
privacy guarantees, we prove that noiselessly-private mechanisms admit
composition theorem and post-processing does not weaken their privacy
guarantees. We prove that quantization operators can ensure noiseless privacy
if the number of quantization levels is appropriately selected based on the
sensitivity of the query and the privacy budget. Finally, we illustrate the
privacy merits of noiseless privacy using multiple datasets in energy and
transport.
