Patrick P. Tsang
Man Ho Au
Apu Kapadia
Skip Abstract Section
Abstract
Several credential systems have been proposed in which users can authenticate to service providers 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, some systems have been proposed in which users can be deanonymized only if they authenticate “too many times,” such as “double spending” with electronic cash. While useful in some applications, such techniques cannot be generalized to more subjective definitions of misbehavior, for example, using such schemes it is not possible to block anonymous users who “deface too many Web pages” on a Web site.
We present BLAC, the first anonymous credential system in which service providers can revoke the credentials of misbehaving users without relying on a TTP . Since revoked users remain anonymous, misbehaviors can be judged subjectively without users fearing arbitrary deanonymization by a TTP . Additionally, our construction supports a d-strikes-out revocation policy, whereby users who have been subjectively judged to have repeatedly misbehaved at least d times are revoked from the system. Thus, for the first time, it is indeed possible to block anonymous users who have “defaced too many Web pages” using our scheme.
- Ateniese, G., Camenisch, J., Joye, M., and Tsudik, G. 2000. A practical and provably secure coalition-resistant group signature scheme. In Proceedings of the International Cryptology Conference (CRYPTO’00). M. Bellare Ed., Lecture Notes in Computer Science, vol. 1880, Springer, 255--270. Google Scholar
Digital Library
- Ateniese, G., Song, D. X., and Tsudik, G. 2002. Quasi-efficient revocation in group signatures. In Proceedings of the Conference on Financial Cryptography. M. Blaze Ed., Lecture Notes in Computer Science, vol. 2357, Springer, 183--197. Google ScholarDigital Library
- Au, M. H., Chow, S. S. M., and Susilo, W. 2005. Short e-cash. In Proceedings of the International Conference on Cryptology in India (INDOCRYPT’05). S. Maitra et al. Eds., Lecture Notes in Computer Science, vol. 3797, Springer, 332--346. Google ScholarDigital Library
- Au, M. H., Susilo, W., and Mu, Y. 2006. Constant-size dynamic k-TAA. In Proceedings of the 5th International Conference on Security and Cryptography for Networks (SCN’06). R. D. Prisco and M. Yung Eds., Lecture Notes in Computer Science, vol. 4116, Springer, 111--125. Google ScholarDigital Library
- Bellare, M. and Rogaway, P. 1993. Random oracles are practical: A paradigm for designing efficient protocols. In Proceedings of the ACM Conference on Computer and Communications Security. 62--73. Google ScholarDigital Library
- Boneh, D. and Boyen, X. 2004. Short signatures without random oracles. In Proceedings of the Annual International Conference on the Theory and Applications of Cryptographic Techniques (EUROCRYPT’04). C. Cachin and J. Camenisch Eds., Lecture Notes in Computer Science, vol. 3027, Springer, 56--73.Google Scholar
- Boneh, D. and Shacham, H. 2004. Group signatures with verifier-local revocation. In Proceedings of the ACM Conference on Computer and Communications Security. V. Atluri et al. Eds., ACM, 168--177. Google ScholarDigital Library
- Boneh, D., Boyen, X., and Shacham, H. 2004. Short group signatures. In Proceedings of the 24th Annual International Cryptology Conference, Advances in Cryptology (CRYPTO’04). M. K. Franklin Ed., Lecture Notes in Computer Science, vol. 3152, Springer, 41--55.Google Scholar
- Boyen, X. 2007. Mesh signatures. In Proceedings of the Annual International Conference on Theory and Applications of Cryptographic Techniques (EUROCRYPT’07). M. Naor Ed., Lecture Notes in Computer Science, vol. 4515, Springer, 210--227. Google ScholarDigital Library
- Brickell, E. and Li, J. 2007. Enhanced privacy ID: A direct anonymous attestation scheme with enhanced revocation capabilities. In Proceedings of the ACM Workshop on Privacy in the Electronic Society (WPES’07). P. Ning and T. Yu Eds., ACM, 21--30. Google ScholarDigital Library
- Camenisch, J., Hohenberger, S., Kohlweiss, M., Lysyanskaya, A., and Meyerovich, M. 2006a. How to win the clonewars: Efficient periodic n-times anonymous authentication. In Proceedings of the ACM Conference on Computer and Communications Security. A. Juels et al. Eds., ACM, 201--210. Google ScholarDigital Library
- Camenisch, J., Hohenberger, S., and Lysyanskaya, A. 2005. Compact e-cash. In Proceedings of the 24th Annual International Conference on the Theory and Applications of Cryptographic Techniques, Advances in Cryptology (EUROCRYPT’05). R. Cramer Ed., Lecture Notes in Computer Science, vol. 3494, Springer, 302--321. Google ScholarDigital Library
- Camenisch, J., Hohenberger, S., and Lysyanskaya, A. 2006b. Balancing accountability and privacy using e-cash (extended abstract). In Proceedings of the 5th International Conference on Security and Cryptography for Networks (SCN’06). R. D. Prisco and M. Yung Eds., Lecture Notes in Computer Science, vol. 4116, Springer, 141--155. Google ScholarDigital Library
- Camenisch, J. and Lysyanskaya, A. 2001. An efficient system for non-transferable anonymous credentials with optional anonymity revocation. In Proceedings of the Annual International Conference on the Theory and Applications of Cryptographic Techniqes (EUROCRYPT’01). B. Pfitzmann Ed., Lecture Notes in Computer Science, vol. 2045, Springer, 93--118. Google ScholarDigital Library
- Camenisch, J. and Lysyanskaya, A. 2002a. Dynamic accumulators and application to efficient revocation of anonymous credentials. In Proceedings of the International Cryptology Conference (CRYPTO’02). M. Yung Ed., Lecture Notes in Computer Science, vol. 2442, Springer, 61--76. Google ScholarDigital Library
- Camenisch, J. and Lysyanskaya, A. 2002b. A signature scheme with efficient protocols. In Proceedings of the International Conference on Security and Cryptography for Networks (SCN’02). S. Cimato et al. Eds., Lecture Notes in Computer Science, vol. 2576, Springer, 268--289. Google ScholarDigital Library
- Camenisch, J. and Lysyanskaya, A. 2004. Signature schemes and anonymous credentials from bilinear maps. In Proceedings of the 24th Annual International Cryptology Conference, Advances in Cryptology (CRYPTO’04). M. K. Franklin Ed., Lecture Notes in Computer Science, vol. 3152, Springer, 56--72.Google Scholar
- Camenisch, J. and Shoup, V. 2003. Practical verifiable encryption and decryption of discrete logarithms. In Proceedings of the International Cryptology Conference (CRYPTO’03). D. Boneh Ed., Lecture Notes in Computer Science, vol. 2729, Springer, 126--144.Google Scholar
- Camenisch, J. and Stadler, M. 1997. Efficient group signature schemes for large groups (extended abstract). In Proceedings of the International Cryptology Conference (CRYPTO’97). Lecture Notes in Computer Science, vol. 1294, Springer, 410--424. Google ScholarDigital Library
- Catalano, D., Fiore, D., and Messina, M. 2008. Zero-knowledge sets with short proofs. In Proceedings of the Annual International Conference on the Theory and Applications of Cryptographic Tehnqies (EUROCRYPT’08). N. P. Smart Ed., Lecture Notes in Computer Science, vol. 4965, Springer, 433--450. Google ScholarDigital Library
- Chaum, D. and van Heyst, E. 1991. Group signatures. In Proceedings of the Annual International Conference on the Theory and Applications of Cryptographic Techniques (EUROCRYPT’91). 257--265. Google ScholarDigital Library
- Cramer, R., Ed. 2005. Proceedings of the 24th Annual International Conference on the Theory and Applications of Cryptographic Techniques, Advances in Cryptology (EUROCRYPT’05). Lecture Notes in Computer Science, vol. 3494, Springer. Google ScholarDigital Library
- Cramer, R., Damgard, I., and Schoenmakers, B. 1994. Proofs of partial knowledge and simplified design of witness hiding protocols. In Proceedings of the International Cryptology Conference (CRYPTO’94). Y. Desmedt Ed., Lecture Notes in Computer Science, vol. 839, Springer, 174--187. Google ScholarDigital Library
- Damgard, I. 2000. Efficient concurrent zero-knowledge in the auxiliary string model. In Proceedings of the Annual International Conference on the Theory and Applications of Cryptographic Techniqes (EUROCRYPT’00). 418--430. Google ScholarDigital Library
- Dingledine, R., Mathewson, N., and Syverson, P. F. 2004. Tor: The second-generation onion router. In Proceedings of the USENIX Security Symposium. USENIX, 303--320. Google ScholarDigital Library
- Douceur, J. R. 2002. The sybil attack. In Proceedings of the International Workshop on Peer-to-Peer Systems (IPTPS’02). P. Druschel et al. Eds., Lecture Notes in Computer Science, vol. 2429, Springer, 251--260. Google ScholarDigital Library
- Franklin, M. K., Ed. 2004. Proceedings of the 24th Annual International Cryptology Conference, Advances in Cryptology (CRYPTO’04). Lecture Notes in Computer Science, vol. 3152, Springer.Google Scholar
- Goldwasser, S., Micali, S., and Rackoff, C. 1989. The knowledge complexity of interactive proof systems. SIAM J. Comput. 18, 1, 186--208. Google ScholarDigital Library
- Goldwasser, S., Micali, S., and Rivest, R. L. 1988. A digital signature scheme secure against adaptive chosen-message attacks. SIAM J. Comput. 17, 2, 281--308. Google ScholarDigital Library
- Johnson, P. C., Kapadia, A., Tsang, P. P., and Smith, S. W. 2007. Nymble: Anonymous IP-address blocking. In Proceedings of the Conference on Privacy Enhancing Technologies. N. Borisov and P. Golle Eds., Lecture Notes in Computer Science, vol. 4776, Springer, 113--133. Google ScholarDigital Library
- Kiayias, A. and Yung, M. 2005. Group signatures with efficient concurrent join. In Proceedings of the 24th Annual International Conference on the Theory and Applications of Cryptographic Techniques, Advances in Cryptology (EUROCRYPT’05). R. Cramer Ed., Lecture Notes in Computer Science, vol. 3494, Springer, 198--214. Google ScholarDigital Library
- Liu, J. K., Wei, V. K., and Wong, D. S. 2004. Linkable spontaneous anonymous group signature for ad hoc groups (extended abstract). In Proceedings of the Australian Conference on Information Security and Privacy (ACISP’04). H. Wang et al. Eds., Lecture Notes in Computer Science, vol. 3108, Springer, 325--335.Google Scholar
- Nguyen, L. 2005. Accumulators from bilinear pairings and applications. In Proceedings of the Cryptographer’s Track at the RSA Conference (CT-RSA’05). A. Menezes Ed., Lecture Notes in Computer Science, vol. 3376, Springer, 275--292. Google ScholarDigital Library
- Nguyen, L. and Safavi-Naini, R. 2005. Dynamic k-times anonymous authentication. In Proceedings of the International Conference on Applied Cryptography and Network Security (ACNS’05). J. Ioannidis et al. Eds., Lecture Notes in Computer Science, vol. 3531, Springer, 318--333. Google ScholarDigital Library
- Prisco, R. D. and Yung, M., Eds. 2006. Proceedings of the 5th International Conference on Security and Cryptography for Networks (SCN’06). Lecture Notes in Computer Science, vol. 4116, Springer. Google ScholarDigital Library
- Schnorr, C.-P. 1991. Efficient signature generation by smart cards. J. Cryptol. 4, 3, 161--174.Google ScholarDigital Library
- Syverson, P. F., Stubblebine, S. G., and Goldschlag, D. M. 1997. Unlinkable serial transactions. In Proceedings of the Conference on Financial Cryptography. R. Hirschfeld Ed., Lecture Notes in Computer Science, vol. 1318, Springer, 39--56. Google ScholarDigital Library
- Teranishi, I., Furukawa, J., and Sako, K. 2004. k-times anonymous authentication (extended abstract). In Proceedings of the Annual International Conference on the Theory and Application of Cryptology and Information Security (ASIACRYPT’04). P. J. Lee Ed., Lecture Notes in Computer Science, vol. 3329, Springer, 308--322.Google Scholar
- Teranishi, I. and Sako, K. 2006. k-times anonymous authentication with a constant proving cost. In Proceedings of the Conference on Public Key Cryptography. M. Yung et al. Eds., Lecture Notes in Computer Science, vol. 3958, Springer, 525--542. Google ScholarDigital Library
- TPM Work Group. 2006. TCG TPM specification version 1.2 revision 94. Tech. rep., Trusted Computing Group.Google Scholar
- Tsang, P. P., Au, M. H., Kapadia, A., and Smith, S. W. 2007a. Blacklistable anonymous credentials: Blocking misbehaving users without TTPs. In Proceedings of the ACM Conference on Computer and Communications Security. P. Ning et al. Eds., ACM, 72--81. Google ScholarDigital Library
- Tsang, P. P., Au, M. H., Kapadia, A., and Smith, S. W. 2007b. Blacklistable anonymous credentials: Blocking misbehaving users without TTPs (full version). Tech. rep. TR2007-601, Dartmouth College.Google Scholar
- Tsang, P. P., Au, M. H., Kapadia, A., and Smith, S. W. 2008. PEREA: Towards practical TTP-free revocation in anonymous authentication. In Proceedings of the ACM Conference on Computer and Communications Security. P. Ning et al. Eds., ACM, 333--344. Google ScholarDigital Library
- Tsang, P. P., Wei, V. K., Chan, T. K., Au, M. H., Liu, J. K., and Wong, D. S. 2004. Separable linkable threshold ring signatures. In Proceedings of the International Conference on Cryptology in India (INDOCRYPT’04). A. Canteaut and K. Viswanathan Eds., Lecture Notes in Computer Science, vol. 3348, Springer, 384--398. Google ScholarDigital Library
Index Terms
- BLAC: Revoking Repeatedly Misbehaving Anonymous Users without Relying on TTPs
Recommendations
PEREA: towards practical TTP-free revocation in anonymous authentication
CCS '08: Proceedings of the 15th ACM conference on Computer and communications securitySeveral 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 ...
Blacklistable anonymous credentials: blocking misbehaving users without ttps
CCS '07: Proceedings of the 14th ACM conference on Computer and communications securitySeveral 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 ...
PEREA: Practical TTP-free revocation of repeatedly misbehaving anonymous users
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' ...
Comments