How to Win the Clone Wars: Efficient Periodic n-Times Anonymous Authentication

We create a credential system that lets a user anonymously authenticate at most ‘n’ times in a single time period. A user withdraws a dispenser of ‘n’ e-tokens. She shows an e-token to a verifier to authenticate herself; each e-token can be used only once, however, the dispenser automatically refreshes every time period. The only prior solution to this problem, due to Damgaard et al.[DDP05], uses protocols that are a factor of ‘k’ slower for the user and verifier, where ‘k’ is the security parameter. Damgaard et al. also only support one authentication per time period, while we support ‘n’. Because our construction is based on e-cash, we can use existing techniques to identify a cheating user, trace all of her e-tokens, and revoke her dispensers. We also offer a new anonymity service: glitch protection for basically honest users who (occasionally) reuse e-tokens. The verifier can always recognize a reused e-token; however, we preserve the anonymity of users who do not reuse e-tokens too often.