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

Abstract : 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 (wrt 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.
Document type :
Conference papers
Complete list of metadatas

Cited literature [7 references]  Display  Hide  Download

https://hal.archives-ouvertes.fr/hal-02126848
Contributor : Catuscia Palamidessi <>
Submitted on : Wednesday, May 15, 2019 - 6:53:01 PM
Last modification on : Friday, May 17, 2019 - 1:27:53 AM

File

main.pdf
Files produced by the author(s)

Identifiers

  • HAL Id : hal-02126848, version 1

Collections

Citation

Konstantinos Chatzikokolakis, Natasha Fernandes, Catuscia Palamidessi. Comparing systems: max-case refinement orders and application to differential privacy. IEEE Computer Security Foundations Symposium, 2019, Hoboken, United States. ⟨hal-02126848⟩

Share

Metrics

Record views

81

Files downloads

47