Probable innocence revisited

K. Chatzikokolakis, C. Palamidessi

    Research output: Chapter in Book/Report/Conference proceedingConference contributionAcademicpeer-review

    5 Citations (Scopus)


    In this paper we study probable innocence, a notion of probabilistic anonymity provided by protocols such as Crowds. The authors of Crowds, Reiter and Rubin, gave a definition of probable innocence which later has been interpreted by other authors in terms of the probability of the users from the point of view of the observer. This formalization however does not seem to correspond exactly to the property that Reiter and Rubin have shown for Crowds, the latter, in fact, is independent from the probability of the users.

    We take the point of view that anonymity should be a concept depending only on the protocol, and should abstract from the probabilities of the users. For strong anonymity, this abstraction leads to a concept known as conditional anonymity. The main goal of this paper is to establish a notion which is to probable innocence as conditional anonymity is to strong anonymity. We show that our definition, while being more general, corresponds exactly to the property that Reiter and Rubin have shown for Crowds, under specific conditions. We also show that in the particular case that the users have uniform probabilities we obtain a property similar to the definition of probable innocence given by Halpern and O’Neill.
    Original languageEnglish
    Title of host publicationFormal Aspects in Security and Trust
    Subtitle of host publicationThird International Workshop, FAST 2005, Newcastle upon Tyne, UK, July 18-19, 2005. Revised Selected Papers
    EditorsT. Dimitrakos, F. Martinelli, P.Y.A. Ryan, S.A. Schneider
    Place of PublicationBerlin
    Number of pages16
    ISBN (Electronic)978-3-540-32629-8
    ISBN (Print)3-540-32628-6, 978-3-540-32628-1
    Publication statusPublished - 2006

    Publication series

    NameLecture Notes in Computer Science (LNCS)
    ISSN (Print)0302-9743


    Dive into the research topics of 'Probable innocence revisited'. Together they form a unique fingerprint.

    Cite this