PEREA: towards practical TTP-free revocation in anonymous authentication

ABSTRACT

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 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. 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.

REFERENCES

• 1: Giuseppe Ateniese , Jan Camenisch , Marc Joye , Gene Tsudik, A Practical and Provably Secure Coalition-Resistant Group Signature Scheme, Proceedings of the 20th Annual International Cryptology Conference on Advances in Cryptology, p.255-270, August 20-24, 2000
• 2: G. Ateniese, D.X. Song, and G. Tsudik. Quasi-efficient revocation in group signatures. In Financial Cryptography, volume 2357 of LNCS, pages 183--197. Springer, 2002.
• 3: Giuseppe Ateniese , Gene Tsudik, Some Open Issues and New Directions in Group Signatures, Proceedings of the Third International Conference on Financial Cryptography, p.196-211, February 01, 1999
• 4: M.H. Au, S.S. M. Chow, and W. Susilo. Short e-cash. In INDOCRYPT, volume 3797 of LNCS, pages 332--346. Springer, 2005.
• 5: N. Baric and B. Pfitzmann. Collision-free accumulators and fail-stop signature schemes without trees. In EUROCRYPT, pages 480--494, 1997.
• 6: D. Boneh, X. Boyen, and H. Shacham. Short group signatures. In CRYPTO, volume 3152 of LNCS, pages 41--55. Springer, 2004.
• 7: Dan Boneh , Hovav Shacham, Group signatures with verifier-local revocation, Proceedings of the 11th ACM conference on Computer and communications security, October 25-29, 2004, Washington DC, USA [doi>10.1145/1030083.1030106]
• 8: F. Boudot. Efficient proofs that a committed number lies in an interval. In EUROCRYPT, pages 431--444, 2000.
• 9: Ernie Brickell , Jiangtao Li, Enhanced privacy id: a direct anonymous attestation scheme with enhanced revocation capabilities, Proceedings of the 2007 ACM workshop on Privacy in electronic society, October 29-29, 2007, Alexandria, Virginia, USA [doi>10.1145/1314333.1314337]
• 10: J. Camenisch. Group Signature Schemes and Payment Systems Based on the Discrete Logarithm Problem. PhD thesis, ETH Zurich, 1998. Reprint as vol. 2 of ETH Series in Information Security and Cryptography, ISBN 3-89649-286-1, Hartung-Gorre Verlag, Konstanz, 1998.
• 11: Jan Camenisch , Susan Hohenberger , Markulf Kohlweiss , Anna Lysyanskaya , Mira Meyerovich, How to win the clonewars: efficient periodic n-times anonymous authentication, Proceedings of the 13th ACM conference on Computer and communications security, October 30-November 03, 2006, Alexandria, Virginia, USA [doi>10.1145/1180405.1180431]
• 12: J. Camenisch and A. Lysyanskaya. A Signature Scheme with Efficient Protocols. In SCN, volume 2576 of LNCS, pages 268--289. Springer, 2002.
• 13: Jan Camenisch , Anna Lysyanskaya, Dynamic Accumulators and Application to Efficient Revocation of Anonymous Credentials, Proceedings of the 22nd Annual International Cryptology Conference on Advances in Cryptology, p.61-76, August 18-22, 2002
• 14: Jan Camenisch , Markus Stadler, Efficient Group Signature Schemes for Large Groups (Extended Abstract), Proceedings of the 17th Annual International Cryptology Conference on Advances in Cryptology, p.410-424, August 17-21, 1997
• 15: D. Chaum and E. van Heyst. Group signatures. In EUROCRYPT, pages 257--265, 1991.
• 16: I. Damgaard. Efficient concurrent zero-knowledge in the auxiliary string model. In EUROCRYPT, pages 418--430, 2000.
• 17: Pierre Dusart, The kth prime is greater than k(lnk + ln lnk - 1) for k ≥ 2, Mathematics of Computation, v.68 n.225, p.411-415, Jan. 1999 [doi>10.1090/S0025-5718-99-01037-6]
• 18: Eiichiro Fujisaki , Tatsuaki Okamoto, Statistical Zero Knowledge Protocols to Prove Modular Polynomial Relations, Proceedings of the 17th Annual International Cryptology Conference on Advances in Cryptology, p.16-30, August 17-21, 1997
• 19: Oded Goldreich , Hugo Krawczyk, On the Composition of Zero-Knowledge Proof Systems, SIAM Journal on Computing, v.25 n.1, p.169-192, Feb. 1996 [doi>10.1137/S0097539791220688]
• 20: S. Goldwasser , S. Micali , C. Rackoff, The knowledge complexity of interactive proof systems, SIAM Journal on Computing, v.18 n.1, p.186-208, Feb. 1989 [doi>10.1137/0218012]
• 21: P.C. Johnson, A. Kapadia, P.P. Tsang, and S.W. Smith. Nymble: Anonymous ip-address blocking. In Privacy Enhancing Technologies, volume 4776 of LNCS, pages 113--133. Springer, 2007.
• 22: A. Kiayias, Y. Tsiounis, and M. Yung. Traceable signatures. In EUROCRYPT, volume 3027 of LNCS, pages 571--589. Springer, 2004.
• 23: Jiangtao Li , Ninghui Li , Rui Xue, Universal Accumulators with Efficient Nonmembership Proofs, Proceedings of the 5th international conference on Applied Cryptography and Network Security, June 05-08, 2007, Zhuhai, China [doi>10.1007/978-3-540-72738-5_17]
• 24: L. Nguyen. Accumulators from bilinear pairings and applications. In CT-RSA, volume 3376 of LNCS, pages 275--292. Springer, 2005.
• 25: I. Teranishi, J. Furukawa, and K. Sako. k-times anonymous authentication (extended abstract). In ASIACRYPT, volume 3329 of LNCS, pages 308--322. Springer, 2004.
• 26: Patrick P. Tsang , Man Ho Au , Apu Kapadia , Sean W. Smith, Blacklistable anonymous credentials: blocking misbehaving users without ttps, Proceedings of the 14th ACM conference on Computer and communications security, October 28-31, 2007, Alexandria, Virginia, USA [doi>10.1145/1315245.1315256]

INDEX TERMS

Primary Classification:
  K. Computing Milieux
  K.6 MANAGEMENT OF COMPUTING AND INFORMATION SYSTEMS
      K.6.5 Security and Protection (D.4.6, K.4.2)
          Subjects: Authentication

Additional Classification:
  E. Data
  E.3 DATA ENCRYPTION
      Subjects: Public key cryptosystems

General Terms:
Algorithms, Security

Keywords:
anonymous authentication, non-membership proofs, privacy-enhanced revocation, subjective blacklisting