Probable Innocence Revisited

Konstantinos Chatzikokolakis 1 Catuscia Palamidessi 1
1 COMETE - Concurrency, Mobility and Transactions
LIX - Laboratoire d'informatique de l'École polytechnique [Palaiseau], Inria Saclay - Ile de France, X - École polytechnique, CNRS - Centre National de la Recherche Scientifique : UMR7161
Abstract : In this paper we propose a formalization of probable innocence, a notion of probabilistic anonymity that is associated to “realistic” protocols such as Crowds. We analyze critically two different definitions of probable innocence from the literature. The first one, corresponding to the property that Reiter and Rubin have proved for Crowds, aims at limiting the probability of detection. The second one, by Halpern and O'Neill, aims at constraining the attacker's confidence. Our proposal combines the spirit of both these definitions while generalizing them. In particular, our definition does not need symmetry assumptions, and it does not depend on the probabilities of the users to perform the action of interest. We show that, in case of a symmetric system, our definition corresponds exactly to the one of Reiter and Rubin. Furthermore, in the case of users with uniform probabilities, it amounts to a property similar to that of Halpern and O'Neill. Another contribution of our paper is the study of probable innocence in the case of protocol composition, namely when multiple runs of the same protocol can be linked, as in the case of Crowds.
Type de document :
Communication dans un congrès
Theodosis Dimitrakos and Fabio Martinelli and Peter Y. A. Ryan and Steve A. Schneider. Third International Workshop on Formal Aspects in Security and Trust (FAST 2005), Jul 2005, Newcastle Upon Tyne, United Kingdom. Springer, 3866, pp.142-157, 2006, Lecture Notes in Computer Science
Liste complète des métadonnées

Littérature citée [24 références]  Voir  Masquer  Télécharger

https://hal.inria.fr/inria-00201109
Contributeur : Catuscia Palamidessi <>
Soumis le : dimanche 23 décembre 2007 - 19:03:32
Dernière modification le : jeudi 10 mai 2018 - 02:06:28
Document(s) archivé(s) le : mardi 13 avril 2010 - 15:33:45

Fichier

reportPI.pdf
Fichiers produits par l'(les) auteur(s)

Identifiants

  • HAL Id : inria-00201109, version 1

Collections

Citation

Konstantinos Chatzikokolakis, Catuscia Palamidessi. Probable Innocence Revisited. Theodosis Dimitrakos and Fabio Martinelli and Peter Y. A. Ryan and Steve A. Schneider. Third International Workshop on Formal Aspects in Security and Trust (FAST 2005), Jul 2005, Newcastle Upon Tyne, United Kingdom. Springer, 3866, pp.142-157, 2006, Lecture Notes in Computer Science. 〈inria-00201109〉

Partager

Métriques

Consultations de la notice

483

Téléchargements de fichiers

107