Paper 2013/317

Anon-Pass: Practical Anonymous Subscriptions

Michael Z. Lee, Alan M. Dunn, Jonathan Katz, Brent Waters, and Emmett Witchel


We present the design, security proof, and implementation of an anonymous subscription service. Users register for the service by providing some form of identity, which might or might not be linked to a real-world identity such as a credit card, a web login, or a public key. A user logs on to the system by presenting a credential derived from information received at registration. Each credential allows only a single login in any authentication window, or epoch. Logins are anonymous in the sense that the service cannot distinguish which user is logging in any better than random guessing. This implies unlinkability of a user across different logins. We find that a central tension in an anonymous subscription service is the service provider’s desire for a long epoch (to reduce server-side computation) versus users’ desire for a short epoch (so they can repeatedly “re-anonymize” their sessions). We balance this tension by having short epochs, but adding an efficient operation for clients who do not need unlinkability to cheaply re-authenticate themselves for the next time period. We measure performance of a research prototype of our pro- tocol that allows an independent service to offer anonymous access to existing services. We implement a music service, an Android-based subway-pass application, and a web proxy, and show that adding anonymity adds minimal client latency and only requires 33 KB of server memory per active user.

Available format(s)
Publication info
Published elsewhere. This is the full version of the IEEE Symposium on Security & Privacy 2013 paper.
AnonymitySubscriptionsImplementationZero Knowledge
Contact author(s)
mzlee @ cs utexas edu
2013-06-02: received
Short URL
Creative Commons Attribution


      author = {Michael Z.  Lee and Alan M.  Dunn and Jonathan Katz and Brent Waters and Emmett Witchel},
      title = {Anon-Pass: Practical Anonymous Subscriptions},
      howpublished = {Cryptology ePrint Archive, Paper 2013/317},
      year = {2013},
      note = {\url{}},
      url = {}
Note: In order to protect the privacy of readers, does not use cookies or embedded third party content.