Anonymity Protocols as Noisy Channels

Konstantinos Chatzikokolakis 1 Catuscia Palamidessi 1 Prakash Panangaden 2
1 COMETE - Concurrency, Mobility and Transactions
LIX - Laboratoire d'informatique de l'École polytechnique [Palaiseau], Inria Saclay - Ile de France, Polytechnique - X, CNRS - Centre National de la Recherche Scientifique : UMR7161
Abstract : We consider a framework in which anonymity protocols are interpreted as noisy channels in the information-theoretic sense, and we explore the idea of using the notion of capacity as a measure of the loss of anonymity. Such idea was already suggested by Moskowitz, Newman and Syverson, in their analysis of the covert channel that can be created as a result of non-perfect anonymity. We consider the case in which some leak of information is intended by design, and we introduce the notion of conditional capacity to rule out this factor, thus retrieving a natural correspondence with the notion of anonymity. Furthermore, we show how to compute the capacity and the conditional capacity when the anonymity protocol satisfies certain symmetries. We also investigate how the adversary can test the system to try to infer the user's identity, and we study how his probability of success depends on the characteristics of the channel. We then illustrate how various notions of anonymity can be expressed in this framework, and show the relation with some definitions of probabilistic anonymity in literature. Finally, we show how to compute the matrix of the channel (and hence the capacity and conditional capacity) using model checking.
Type de document :
Communication dans un congrès
Ugo Montanari and Don Sannella. 2nd Symposium on Trustworthy Global Computing (TGC), Nov 2006, Lucca, Italy. Springer, 4661, pp.281-300, 2006, Lecture Notes in Computer Science. 〈10.1007/978-3-540-75336-0_18〉
Liste complète des métadonnées

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

https://hal.inria.fr/inria-00201110
Contributeur : Catuscia Palamidessi <>
Soumis le : dimanche 23 décembre 2007 - 19:30:45
Dernière modification le : jeudi 11 janvier 2018 - 06:22:13
Document(s) archivé(s) le : mardi 13 avril 2010 - 15:07:43

Fichier

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

Identifiants

Collections

Citation

Konstantinos Chatzikokolakis, Catuscia Palamidessi, Prakash Panangaden. Anonymity Protocols as Noisy Channels. Ugo Montanari and Don Sannella. 2nd Symposium on Trustworthy Global Computing (TGC), Nov 2006, Lucca, Italy. Springer, 4661, pp.281-300, 2006, Lecture Notes in Computer Science. 〈10.1007/978-3-540-75336-0_18〉. 〈inria-00201110〉

Partager

Métriques

Consultations de la notice

358

Téléchargements de fichiers

86