PEREA: Towards practical TTP-free revocation in anonymous authentication

Patrick P. Tsang, Man Ho Allen Au, Apu Kapadia, Sean W. Smith

Research output: Chapter in book / Conference proceedingConference article published in proceeding or bookAcademic researchpeer-review

45 Citations (Scopus)


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. Recent schemes such as Biacklistable Anonymous Credentials (BLAG) 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 coniputation required for authentication at the server is linear in tire size (L) of the revocation list. 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 (K « L) of a revocation window, the number of subsequent authentications before which a user's misbehavior must be recognized if the user is to be revoked. We prove the security of our construction, and have developed a prototype implementation of PEREA to validate its efficiency experimentally.
Original languageEnglish
Title of host publicationProceedings of the 15th ACM Conference on Computer and Communications Security, CCS'08
Number of pages11
Publication statusPublished - 1 Dec 2008
Externally publishedYes
Event15th ACM conference on Computer and Communications Security, CCS'08 - Alexandria, VA, United States
Duration: 27 Oct 200831 Oct 2008


Conference15th ACM conference on Computer and Communications Security, CCS'08
Country/TerritoryUnited States
CityAlexandria, VA


  • Anonymous authentication
  • Non-membership proofs
  • Privacy-enhanced revocation
  • Subjective blacklisting

ASJC Scopus subject areas

  • Software
  • Computer Networks and Communications


Dive into the research topics of 'PEREA: Towards practical TTP-free revocation in anonymous authentication'. Together they form a unique fingerprint.

Cite this