Blacklistable anonymous credentials: blocking misbehaving users without ttps

ABSTRACT

Several credential systems have been proposed in which users can authenticate to services anonymously. Since anonymity can give users the license to misbehave, some variants allow the selective deanonymization (or linking) of misbehaving users upon a complaint to a trusted third party (TTP). The ability of the TTP to revoke a user's privacy at any time, however, is too strong a punishment for misbehavior. To limit the scope of deanonymization, systems such as "e-cash" have been proposed in which users are deanonymized under only certain types of well-defined misbehavior such as "double spending." While useful in some applications, it is not possible to generalize such techniques to more subjective definitions of misbehavior.

We present the first anonymous credential system in which services can "blacklist" misbehaving users without contacting a TTP. Since blacklisted users remain anonymous, misbehaviors can be judged subjectively without users fearing arbitrary deanonymization by a TTP.

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: M. H. Au, S. S. M. Chow, and W. Susilo. Short e-cash. In INDOCRYPT, volume 3797 of LNCS, pages 332--346. Springer, 2005.
• 4: M. H. Au, W. Susilo, and Y. Mu. Constant-size dynamic k-TAA. In SCN, volume 4116 of LNCS, pages 111--125. Springer, 2006.
• 5: Mihir Bellare , Phillip Rogaway, Random oracles are practical: a paradigm for designing efficient protocols, Proceedings of the 1st ACM conference on Computer and communications security, p.62-73, November 03-05, 1993, Fairfax, Virginia, United States [doi>10.1145/168588.168596]
• 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: E. Brickell and J. Li. Enhanced privacy ID: A direct anonymous attestation scheme with enhanced revocation capabilities. Cryptology ePrint Archive, Report 2007/194, 2007. http://eprint.iacr.org/.
• 9: 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]
• 10: J. Camenisch, S. Hohenberger, and A. Lysyanskaya. Compact e-cash. In EUROCRYPT, volume 3494 of LNCS, pages 302--321. Springer, 2005.
• 11: J. Camenisch, S. Hohenberger, and A. Lysyanskaya. Balancing accountability and privacy using e-cash (extended abstract). In SCN, volume 4116 of LNCS, pages 141--155. Springer, 2006.
• 12: Jan Camenisch , Anna Lysyanskaya, An Efficient System for Non-transferable Anonymous Credentials with Optional Anonymity Revocation, Proceedings of the International Conference on the Theory and Application of Cryptographic Techniques: Advances in Cryptology, p.93-118, May 06-10, 2001
• 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: J. Camenisch and A. Lysyanskaya. A signature scheme with efficient protocols. In SCN, volume 2576 of LNCS, pages 268--289. Springer, 2002.
• 15: J. Camenisch and A. Lysyanskaya. Signature schemes and anonymous credentials from bilinear maps. In CRYPTO, volume 3152 of LNCS, pages 56--72. Springer, 2004.
• 16: J. Camenisch and V. Shoup. Practical verifiable encryption and decryption of discrete logarithms. In CRYPTO, volume 2729 of LNCS, pages 126--144. Springer, 2003.
• 17: 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
• 18: D. Chaum and E. van Heyst. Group signatures. In EUROCRYPT, pages 257--265, 1991.
• 19: Ronald Cramer , Ivan Damgård , Berry Schoenmakers, Proofs of Partial Knowledge and Simplified Design of Witness Hiding Protocols, Proceedings of the 14th Annual International Cryptology Conference on Advances in Cryptology, p.174-187, August 21-25, 1994
• 20: I. Damgård. Efficient concurrent zero-knowledge in the auxiliary string model. In EUROCRYPT, pages 418--430, 2000.
• 21: Roger Dingledine , Nick Mathewson , Paul Syverson, Tor: the second-generation onion router, Proceedings of the 13th conference on USENIX Security Symposium, p.21-21, August 09-13, 2004, San Diego, CA
• 22: John R. Douceur, The Sybil Attack, Revised Papers from the First International Workshop on Peer-to-Peer Systems, p.251-260, March 07-08, 2002
• 23: 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]
• 24: Shafi Goldwasser , Silvio Micali , Ronald L. Rivest, A digital signature scheme secure against adaptive chosen-message attacks, SIAM Journal on Computing, v.17 n.2, p.281-308, April 1988 [doi>10.1137/0217017]
• 25: P. C. Johnson, A. Kapadia, P. P. Tsang, and S. W. Smith. Nymble: Anonymous IP-address blocking. In Privacy Enhancing Technologies Symposium (PET '07), Ottawa, Canada, June 2007. To appear.
• 26: A. Kiayias and M. Yung. Group signatures with efficient concurrent join. In EUROCRYPT, volume 3494 of LNCS, pages 198--214. Springer, 2005.
• 27: J. K. Liu, V. K. Wei, and D. S. Wong. Linkable spontaneous anonymous group signature for ad hoc groups (extended abstract). In ACISP, volume 3108 of LNCS, pages 325--335. Springer, 2004.
• 28: L. Nguyen. Accumulators from bilinear pairings and applications. In CT-RSA, volume 3376 of LNCS, pages 275--292. Springer, 2005.
• 29: L. Nguyen and R. Safavi-Naini. Dynamic k-times anonymous authentication. In ACNS, volume 3531 of LNCS, pages 318--333. Springer, 2005.
• 30: C.-P. Schnorr. Efficient signature generation by smart cards. J. Cryptology, 4(3):161--174, 1991.
• 31: Paul F. Syverson , Stuart G. Stubblebine , David M. Goldschlag, Unlinkable Serial Transactions, Proceedings of the First International Conference on Financial Cryptography, p.39-56, February 24-28, 1997
• 32: I. Teranishi, J. Furukawa, and K. Sako. k-times anonymous authentication (extended abstract). In ASIACRYPT, volume 3329 of LNCS, pages 308--322. Springer, 2004.
• 33: I. Teranishi and K. Sako. k-times anonymous authentication with a constant proving cost. In Public Key Cryptography, volume 3958 of LNCS, pages 525--542. Springer, 2006.
• 34: TPM Work Group. TCG TPM specification version 1.2 revision 94. Technical report, Trusted Computing Group, 2006.
• 35: P. P. Tsang, M. H. Au, A. Kapadia, and S. W. Smith. Blacklistable anonymous credentials: Blocking misbehaving users without TTPs (full version). Technical Report TR2007-601, Dartmouth College, Aug 2007.
• 36: P. P. Tsang and V. K. Wei. Short linkable ring signatures for e-voting, e-cash and attestation. In ISPEC, volume 3439 of LNCS, pages 48--60. Springer, 2005.
• 37: P. P. Tsang, V. K. Wei, T. K. Chan, M. H. Au, J. K. Liu, and D. S. Wong. Separable linkable threshold ring signatures. In INDOCRYPT, volume 3348 of LNCS, pages 384--398. Springer, 2004.

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, anonymous blacklisting, privacy, revocation, user misbehavior