Document Type

Journal Article

Publication Details

Au, M., Tsang, P. P. & Kapadia, A. (2011). PEREA: Practical TTP-free revocation of repeatedly misbehaving anonymous users. ACM Transactions on Information and System Security, 14 (4), 29:1-29:34.


Several anonymous authentication schemes allow servers to revoke a misbehaving user’s ability to make future accesses. Traditionally, these schemes have relied on powerful Trusted Third Parties (TTPs) capable of deanonymizing (or linking) users’ connections. Such TTPs are undesirable because users’ anonymity is not guaranteed, and users must trust them to judge misbehaviors fairly. Recent schemes such as Blacklistable Anonymous Credentials (BLAC) and Enhanced Privacy ID (EPID) support “privacy-enhanced revocation”—servers can revoke misbehaving users without a TTP’s involvement, and without learning the revoked users’identities.In BLAC and EPID, however, the computation required for authentication at the server is linear in the size (L) of the revocation list, which is impractical as the size approaches thousands of entries.We propose PEREA, a new anonymous authentication scheme for which this bottleneck computation is independent of the size of the revocation list. Instead, the time complexity of authentication is linear in the size of a revocation window K