Probabilistic and nondeterministic aspects of anonymity

Romain Beauxis 1, 2 Catuscia Palamidessi 1, 2
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 : The concept of anonymity comes into play in a wide range of situations, varying from voting and anonymous donations to postings on bulletin boards and sending emails. The protocols for ensuring anonymity often use random mechanisms which can be described probabilistically, while the agents' behavior may be totally unpredictable, irregular, and hence expressible only nondeterministically. Formal definitions of the concept of anonymity have been investigated in the past either in a totally nondeterministic framework, or in a purely probabilistic one. In this paper, we investigate a notion of anonymity which combines both probability and nondeterminism, and which is suitable for describing the most general situation in which the protocol and the users can have both probabilistic and nondeterministic behavior. We also investigate the properties of the definition for the particular cases of purely nondeterministic users and purely probabilistic users. We formulate the notions of anonymity in terms of probabilistic automata, and we describe protocols and users as processes in the probabilistic $\pi$-calculus, whose semantics is again based on probabilistic automata. Throughout the paper, we illustrate our ideas by using the example of the dining cryptographers.
Type de document :
Article dans une revue
Theoretical Computer Science, Elsevier, 2009, 410 (41), pp.4006--4025. 〈10.1016/j.tcs.2009.06.008〉
Liste complète des métadonnées

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

https://hal.inria.fr/inria-00424855
Contributeur : Catuscia Palamidessi <>
Soumis le : lundi 19 octobre 2009 - 07:44:56
Dernière modification le : jeudi 17 mai 2018 - 12:52:03
Document(s) archivé(s) le : mardi 15 juin 2010 - 21:57:53

Fichier

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

Identifiants

Collections

Citation

Romain Beauxis, Catuscia Palamidessi. Probabilistic and nondeterministic aspects of anonymity. Theoretical Computer Science, Elsevier, 2009, 410 (41), pp.4006--4025. 〈10.1016/j.tcs.2009.06.008〉. 〈inria-00424855〉

Partager

Métriques

Consultations de la notice

285

Téléchargements de fichiers

158