Comparing systems: max-case refinement orders and application to differential privacy

Konstantinos Chatzikokolakis, Natasha Fernandes, Catuscia Palamidessi

Research output: Chapter in Book/Report/Conference proceedingConference proceeding contributionpeer-review

11 Citations (Scopus)


Quantitative Information Flow (QIF) and Differential Privacy (DP) are both concerned with the protection of sensitive information, but they are rather different approaches. In particular, QIF considers the expected probability of a successful attack, while DP (in both its standard and local versions) is a max-case measure, in the sense that it is compromised by the existence of a possible attack, regardless of its probability. Comparing systems is a fundamental task in these areas: one wishes to guarantee that replacing a system A by a system B is a safe operation, that is the privacy of B is no-worse than that of A. In QIF, a refinement order provides strong such guarantees, while in DP mechanisms are typically compared (w.r.t. privacy) based on the ϵ privacy parameter that they provide. In this paper we explore a variety of refinement orders, inspired by the one of QIF, providing precise guarantees for max-case leakage. We study simple structural ways of characterising them, the relation between them, efficient methods for verifying them and their lattice properties. Moreover, we apply these orders in the task of comparing DP mechanisms, raising the question of whether the order based on ϵ provides strong privacy guarantees. We show that, while it is often the case for mechanisms of the same 'family' (geometric, randomised response, etc.), it rarely holds across different families.

Original languageEnglish
Title of host publicationProceedings of 2019 IEEE 32nd Computer Security Foundations Symposium
PublisherInstitute of Electrical and Electronics Engineers (IEEE)
Number of pages16
ISBN (Electronic)9781728114064
Publication statusPublished - 2019
Externally publishedYes
Event32nd IEEE Computer Security Foundations Symposium, CSF 2019 - Hoboken, United States
Duration: 25 Jun 201928 Jun 2019

Publication series

NameProceedings IEEE Computer Security Foundations Symposium
ISSN (Print)1940-1434


Conference32nd IEEE Computer Security Foundations Symposium, CSF 2019
Country/TerritoryUnited States


  • Differential privacy
  • Quantitative information flow

Cite this