Technical Report Results

Technical Report TR688:
PEREA: Practical TTP-Free Revocation of Repeatedly Misbehaving Anonymous Users

Man Ho Au, Patrick P. Tsang, Apu Kapadia
(Jul 2011)
[Updated July 2011]
Several anonymous authentication schemes allow servers to revoke a misbehaving userís ability to make future accesses. Traditionally, these schemes have relied on powerful 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 << L, the number of subsequent authentications before which a userís misbehavior must be recognized if the user is to be revoked. We extend PEREA to support more complex revocation policies that take the severity of misbehaviors into account. Users can authenticate anonymously if their naughtiness, i.e., the sum of the severities of their blacklisted misbehaviors, is below a certain naughtiness threshold. We call our extension PEREA-Naughtiness. We prove the security of our constructions, and validate their efficiency as compared to BLAC analytically and quantitatively.

Available as:
  • PDF (475 KBytes)