Quantitative Information Flow and Applications to Differential Privacy

Mário S. Alvim, Miguel E. Andrés, Konstantinos Chatzikokolakis, Catuscia Palamidessi

Abstract

Secure information flow is the problem of ensuring that the information made publicly available by a computational system does not leak information that should be kept secret. Since it is practically impossible to avoid leakage entirely, in recent years there has been a growing interest in considering the quantitative aspects of information flow, in order to measure and compare the amount of leakage. Information theory is widely regarded as a natural framework to provide firm foundations to quantitive information flow. In this notes we review the two main information-theoretic approaches that have been investigated: the one based on Shannon entropy, and the one based on Rényi min-entropy. Furthermore, we discuss some applications in the area of privacy. In particular, we consider statistical databases and the recently-proposed notion of differential privacy. Using the information-theoretic view, we discuss the bound that differential privacy induces on leakage, and the trade-off between utility and privacy.
BibTeX
@inproceedings{alvim2011quantitative,
  author = {Mário S. Alvim and Miguel E. Andrés and Konstantinos Chatzikokolakis and Catuscia Palamidessi},
  title = {{Quantitative Information Flow and Applications to Differential Privacy}},
  booktitle = {Fosad},
  year = {2011},
  doi = {10.1007/978-3-642-23082-0\_8},
}

Loading related content...

Figure