How to win the clonewars

ABSTRACT

We create a credential system that lets a user anonymously authenticate at most $n$ times in a single time period. A user withdraws a dispenser of n e-tokens. She shows an e-token to a verifier to authenticate herself; each e-token can be used only once, however, the dispenser automatically refreshes every time period. The only prior solution to this problem, due to Damgård et al. [29], uses protocols that are a factor of k slower for the user and verifier, where k is the security parameter. Damgård et al. also only support one authentication per time period, while we support n. Because our construction is based on e-cash, we can use existing techniques to identify a cheating user, trace all of her e-tokens, and revoke her dispensers. We also offer a new anonymity service: glitch protection for basically honest users who (occasionally) reuse e-tokens. The verifier can always recognize a reused e-token; however, we preserve the anonymity of users who do not reuse e-tokens too often.

REFERENCES

Note: OCR errors may be found in this Reference List extracted from the full text article. ACM has opted to expose the complete List rather than only correct and linked 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, K. Fu, M. Green, and S. Hohenberger. Improved Proxy Re-encryption Schemes with Applications to Secure Distributed Storage. In NDSS, p. 29--43, 2005.
	3	L. Ballard, M. Green, B. de Medeiros, and F. Monrose. Correlation-Resistant Storage. Johns Hopkins University, Technical Report # TR-SP-BGMM-050705, 2005.
	4	N. Barić and B. Pfitzmann. Collision-free accumulators and fail-stop signature schemes without trees. In EUROCRYPT '97, volume 1233, p. 480--494, 1997.
	5	D. Boneh and X. Boyen. Short signatures without random oracles. In EUROCRYPT, v.3027 of LNCS, p. 56--73, 2004.
	6	D. Boneh, X. Boyen, and H. Shacham. Short group signatures using strong Diffie-Hellman. In CRYPTO, volume 3152 of LNCS, p. 41--55, 2004.
	7	Dan Boneh , Matthew K. Franklin, Identity-Based Encryption from the Weil Pairing, Proceedings of the 21st Annual International Cryptology Conference on Advances in Cryptology, p.213-229, August 19-23, 2001
	8	F. Boudot. Efficient proofs that a committed number lies in an interval. In EUROCRYPT, vol. 1807, p. 431--444, 2000.
	9	S. Brands. Rethinking Public Key Infrastructure and Digital Certificates--- Building in Privacy. PhD thesis, Eindhoven Inst. of Tech., The Netherlands, 1999.
	10	Ernie Brickell , Peter Gemmell , David Kravitz, Trustee-based tracing extensions to anonymous cash and the making of anonymous change, Proceedings of the sixth annual ACM-SIAM symposium on Discrete algorithms, p.457-466, January 22-24, 1995, San Francisco, California, United States
	11	Jan Camenisch , Ivan Damgård, Verifiable Encryption, Group Encryption, and Their Applications to Separable Group Signatures and Signature Sharing Schemes, Proceedings of the 6th International Conference on the Theory and Application of Cryptology and Information Security: Advances in Cryptology, p.331-345, December 03-07, 2000
	12	J. Camenisch, S. Hohenberger, and A. Lysyanskaya. Compact E-Cash. In EUROCRYPT, volume 3494 of LNCS, p. 302--321, 2005.
	13	J. Camenisch, S. Hohenberger, and A. Lysyanskaya. Balancing accountability and privacy using e-cash. In SCN (to appear), 2006.
	14	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
	15	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
	16	J. Camenisch and A. Lysyanskaya. A signature scheme with efficient protocols. In SCN 2002, volume 2576 of LNCS, p. 268--289, 2003.
	17	J. Camenisch and A. Lysyanskaya. Signature schemes and anonymous credentials from bilinear maps. In CRYPTO 2004, volume 3152 of LNCS, p. 56--72, 2004.
	18	Jan Camenisch , Ueli M. Maurer , Markus Stadler, Digital Payment Systems with Passive Anonymity-Revoking Trustees, Proceedings of the 4th European Symposium on Research in Computer Security: Computer Security, p.33-43, September 25-27, 1996
	19	J. Camenisch and M. Michels. Proving in zero-knowledge that a number $n$ is the product of two safe primes. In EUROCRYPT '99, volume 1592, p. 107--122, 1999.
	20	Jan Camenisch , Markus Michels, Separability and Efficiency for Generic Group Signature Schemes, Proceedings of the 19th Annual International Cryptology Conference on Advances in Cryptology, p.413-430, August 15-19, 1999
	21	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
	22	A. Chan, Y. Frankel, and Y. Tsiounis. Easy come -- easy go divisible cash. In EUROCRYPT, v. 1403, p. 561--575, 1998.
	23	D. Chaum. Blind signatures for untraceable payments. In CRYPTO '82, p. 199--203. Plenum Press, 1982.
	24	D. Chaum. Blind signature systems. In CRYPTO '83, p. 153--156. Plenum, 1983.
	25	David Chaum, Security without identification: transaction systems to make big brother obsolete, Communications of the ACM, v.28 n.10, p.1030-1044, Oct. 1985 [doi>10.1145/4372.4373]
	26	D. Chaum, A. Fiat, and M. Naor. Untraceable electronic cash. In CRYPTO, volume 403 of LNCS, p. 319--327, 1990.
	27	D. Chaum and E. van Heyst. Group signatures. In EUROCRYPT '91, volume 547 of LNCS, p. 257--265, 1991.
	28	S. Chawla, C. Dwork, F. McSherry, A. Smith, and H. Wee. Toward privacy in public databases. In TCC, volume 3378 of LNCS, p. 363--385, 2005.
	29	I. Damgard, K. Dupont, and M. O. Pedersen. Unclonable group identification. In EUROCRYPT, volume 4004 of LNCS, p. 555--572, 2006.
	30	I. B. Damgård. Payment systems and credential mechanism with provable security against abuse by individuals. In CRYPTO, volume 403 of LNCS, p. 328--335, 1990.
	31	Yevgeniy Dodis, Efficient Construction of (Distributed) Verifiable Random Functions, Proceedings of the 6th International Workshop on Theory and Practice in Public Key Cryptography: Public Key Cryptography, p.1-17, January 06-08, 2003
	32	Y. Dodis and A. Yampolskiy. A Verifiable Random Function with Short Proofs an Keys. In PKC, volume 3386 of LNCS, p. 416--431, 2005.
	33	Amos Fiat , Adi Shamir, How to prove yourself: practical solutions to identification and signature problems, Proceedings on Advances in cryptology---CRYPTO '86, p.186-194, January 1987, Santa Barbara, California, United States
	34	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
	35	Steven D. Galbraith, Supersingular Curves in Cryptography, Proceedings of the 7th International Conference on the Theory and Application of Cryptology and Information Security: Advances in Cryptology, p.495-513, December 09-13, 2001
	36	S. Jarecki and V. Shmatikov. Handcuffing big brother: an abuse-resilient transaction escrow scheme. In EUROCRYPT, volume 3027 of LNCS, p. 590--608, 2004.
	37	A. Kiayias, M. Yung, and Y. Tsiounis. Traceable signatures. In EUROCRYPT, vol. 3027, p. 571--589, 2004.
	38	Anna A. Lysyanskaya , Ronald L. Rivest, Signature schemes and applications to cryptographic protocol design, 2002
	39	Anna Lysyanskaya , Ronald L. Rivest , Amit Sahai , Stefan Wolf, Pseudonym Systems, Proceedings of the 6th Annual International Workshop on Selected Areas in Cryptography, p.184-199, August 09-10, 1999
	40	N. McCullagh and P. S. L. M. Barreto. A new two-party identity-based authenticated key agreement. In CT-RSA, volume 3376 of LNCS, p. 262--274, 2004.
	41	V. I. Nechaev. Complexity of a determinate algorithm for the discrete log. Mathematical Notes, 55:165--172, 1994.
	42	L. Nguyen and R. Safavi-Naini. Dynamic k-times anonymous authentication. In ACNS, volume 3531 in LNCS, p. 318--333, 2005.
	43	Torben P. Pedersen, Non-Interactive and Information-Theoretic Secure Verifiable Secret Sharing, Proceedings of the 11th Annual International Cryptology Conference on Advances in Cryptology, p.129-140, August 11-15, 1991
	44	M. Scott. Authenticated ID-based key exchange and remote log-in with simple token and PIN number, 2002. http://eprint.iacr.org/2002/164.
	45	V. Shoup. Lower bounds for discrete logarithms and related problems. In EUROCRYPT , LNCS, p. 256--266, 1997. Update: urlhttp://www.shoup.net/papers/.
	46	Latanya Sweeney, k-anonymity: a model for protecting privacy, International Journal of Uncertainty, Fuzziness and Knowledge-Based Systems, v.10 n.5, p.557-570, October 2002 [doi>10.1142/S0218488502001648]
	47	I. Teranishi, J. Furukawa, and K. Sako. k-times anonymous authentication (extended abstract). In Asiacrypt, volume 3329 of LNCS, p. 308--322, 2004.

Collaborative Colleagues:

Jan Camenisch: colleagues

Susan Hohenberger: colleagues

Markulf Kohlweiss: colleagues

Anna Lysyanskaya: colleagues

Mira Meyerovich: colleagues