zbMATH — the first resource for mathematics

Probabilistic anonymity. (English) Zbl 1134.68426
Abadi, MartĂ­n (ed.) et al., CONCUR 2005 – concurrency theory. 16th international conference, CONCUR 2005, San Francisco, CA, USA, August 23–26, 2005. Proceedings. Berlin: Springer (ISBN 3-540-28309-9/pbk). Lecture Notes in Computer Science 3653, 171-185 (2005).
Summary: 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 mails. The systems for ensuring anonymity often use random mechanisms which can be described probabilistically, while the agents’ interest in performing the anonymous action may be totally unpredictable, irregular, and hence expressable 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 both the systems and the user 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 our notions of anonymity in terms of observables for processes in the probabilistic \(\pi\)-calculus, whose semantics is based on Probabilistic Automata.
We illustrate our ideas by using the example of the dining cryptographers.
For the entire collection see [Zbl 1084.68002].

68Q85 Models and methods for concurrent and distributed computing (process algebras, bisimulation, transition nets, etc.)
68Q45 Formal languages and automata
68Q60 Specification and verification (program logics, model checking, etc.)
94A60 Cryptography
Full Text: DOI