Unpublished Manuscript, November 2000
In this paper we discuss protocols that allow a user to subscribe to an electronic service, and then anonymously access the service. That is, neither the service provider nor anyone else knows who accesses the service at any time, and moreover no one can link two accesses to the same person. On the other hand, the provider obtains proof that the user is authorized to use the service. We formally define the problem and discuss the security features these protocols should have. An important property for a protocol is termination: the access privileges can be used only a fixed number of times. In this paper, we state and analyze two practical schemes which have this property while maintaining unconditional anonymity and unlinkability. The protocols also achieve lower storage and communication requirements than related schemes. In our first protocol, the vendor signs blinded access tokens, while in the second protocol, the client is given limited signing capabilities to create his own access tokens. The security analysis of the second protocol includes identifying a new equivalent variant of the Decisional Diffie-Hellman security assumption, which may be of independent interest.