Advanced Probabilistic Couplings for Differential Privacy

Abstract : Differential privacy is a promising formal approach to data privacy, which provides a quantitative bound on the privacy cost of an algorithm that operates on sensitive information. Several tools have been developed for the formal verification of differentially private algorithms, including program logics and type systems. However, these tools do not capture fundamental techniques that have emerged in recent years, and cannot be used for reasoning about cutting-edge differentially private algorithms. Existing techniques fail to handle three broad classes of algorithms: 1) algorithms where privacy depends on accuracy guarantees, 2) algorithms that are analyzed with the advanced composition theorem, which shows slower growth in the privacy cost, 3) algorithms that interactively accept adaptive inputs. We address these limitations with a new formalism extending apRHL [6], a relational program logic that has been used for proving differential privacy of non-interactive algorithms, and incorporating aHL [11], a (non-relational) program logic for accuracy properties. We illustrate our approach through a single running example, which exemplifies the three classes of algorithms and explores new variants of the Sparse Vector technique, a well-studied algorithm from the privacy literature. We implement our logic in EasyCrypt, and formally verify privacy. We also introduce a novel coupling technique called optimal subset coupling that may be of independent interest.
Type de document :
Communication dans un congrès
23rd ACM Conference on Computer and Communications Security , Oct 2016, Vienne, Austria. pp.55 - 67, 2016, 〈10.1145/2976749.2978391〉
Liste complète des métadonnées

Littérature citée [50 références]  Voir  Masquer  Télécharger
Contributeur : Benjamin Gregoire <>
Soumis le : mardi 6 décembre 2016 - 15:07:10
Dernière modification le : jeudi 11 janvier 2018 - 16:36:44
Document(s) archivé(s) le : mardi 21 mars 2017 - 01:00:02


Fichiers produits par l'(les) auteur(s)




Gilles Barthe, Noémie Fong, Marco Gaboardi, Benjamin Grégoire, Justin Hsu, et al.. Advanced Probabilistic Couplings for Differential Privacy. 23rd ACM Conference on Computer and Communications Security , Oct 2016, Vienne, Austria. pp.55 - 67, 2016, 〈10.1145/2976749.2978391〉. 〈hal-01410196〉



Consultations de la notice


Téléchargements de fichiers