Abstract: Often we wish to ensure that the identity of the user performing a certain action is maintained secret. This property is called anonymity. Examples of situations in which we may wish to provide anonymity include: publishing on the web, retrieving information from the web, sending a message, etc. Many protocols have been designed for this purpose, for example, Crowds [15], Onion Routing [23], the Free Haven [7], Web MIX [1] and Freenet [4].