Probable innocence revisited

K. Chatzikokolakis, C. Palamidessi

    Onderzoeksoutput: Bijdrage aan tijdschriftTijdschriftartikelAcademicpeer review

    23 Citaten (Scopus)
    1 Downloads (Pure)


    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.
    Originele taal-2Engels
    Pagina's (van-tot)123-138
    Aantal pagina's16
    TijdschriftTheoretical Computer Science
    Nummer van het tijdschrift1-2
    StatusGepubliceerd - 2006


    Duik in de onderzoeksthema's van 'Probable innocence revisited'. Samen vormen ze een unieke vingerafdruk.

    Citeer dit