English

37 Pages

Gain access to the library to view online

__
Learn more
__

Description

Niveau: Supérieur

Anonymity Protocols as Noisy Channels ? Konstantinos Chatzikokolakis a, Catuscia Palamidessi aPrakash Panangaden b a INRIA and LIX, Ecole Polytechnique, Palaiseau, France b School of Computer Science, McGill University, Montreal, Quebec, Canada 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 sug- gested 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 correspon- dence 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 ma- trix of the channel (and hence the capacity and conditional capacity) using model checking.

Anonymity Protocols as Noisy Channels ? Konstantinos Chatzikokolakis a, Catuscia Palamidessi aPrakash Panangaden b a INRIA and LIX, Ecole Polytechnique, Palaiseau, France b School of Computer Science, McGill University, Montreal, Quebec, Canada 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 sug- gested 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 correspon- dence 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 ma- trix of the channel (and hence the capacity and conditional capacity) using model checking.

- capacity might
- link between ?
- joint probability
- anonymity protocols
- distance between
- been dedicated
- has been
- channel capacity
- joint distribution

Subjects

Informations

Published by | chaeh |

Reads | 22 |

Language | English |

Report a problem