Group signatures with verifier-local revocation

ABSTRACT

Group signatures have recently become important for enabling privacy-preserving attestation in projects such as Microsoft's ngscb effort (formerly Palladium). Revocation is critical to the security of such systems. We construct a short group signature scheme that supports Verifier-Local Revocation (VLR). In this model, revocation messages are only sent to signature verifiers (as opposed to both signers and verifiers). Consequently there is no need to contact individual signers when some user is revoked. This model is appealing for systems providing attestation capabilities. Our signatures are as short as standard RSA signatures with comparable security. Security of our group signature (in the random oracle model) is based on the Strong Diffie-Hellman assumption and the Decision Linear assumption in bilinear groups. We give a precise model for VLR group signatures and discuss its implications.

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,G.Tsudik,and D.Song.Quasi-efficient revocation of group signatures. In M.Blaze, editor, Proceedings of Financial Cryptography 2002 Mar. 2002.
• 3: N. Baric and B. Pfitzman. Collision-free accumulators and fail-stop signature schemes with out trees. In Proceedings of Eurocrypt 1997 pages 480--494. Springer-Verlag, May 1997.
• 4: M. Bellare, D. Micciancio,and B. Warinschi. Foundations of group signatures: Formal definitions, simplified requirements, and a construction based on general assumptions. In E. Biham, editor, Proceedings of Eurocrypt 2003 volume 2656 of LNCS pages 614--29. Springer-Verlag,May 2003.
• 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 and X. Boyen. Short signatures with out random oracles. In C. Cachin and J. Camenisch, editors, Proceedings of Eurocrypt 2004 LNCS, pages 56--73. Springer-Verlag, May 2004.
• 7: D. Bone ,X. Boyen,and H. Shacham. Short group signatures. In M. Franklin, editor, Proceedings of Crypto 2004 volume 3152 of LNCS pages 41--55. Springer-Verlag, Aug.2004.
• 8: Dan Boneh , Ben Lynn , Hovav Shacham, Short Signatures from the Weil Pairing, Proceedings of the 7th International Conference on the Theory and Application of Cryptology and Information Security: Advances in Cryptology, p.514-532, December 09-13, 2001
• 9: E.Brickell. An eficient protocol for anonymously providing assurance of the container of a private key, Apr. 2003. Submitted to the Trusted Computing Group.
• 10: 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
• 11: D.Chaum and E.van Heyst.Group signatures. In D. W. Davies, editor, Proceedings of Eurocrypt 1991 volume 547 of LNCS pages 257--65. Springer-Verlag, Apr. 1991.
• 12: Xuhua Ding , Gene Tsudik , Shouhuai Xu, Leak-Free Group Signatures with Immediate Revocation, Proceedings of the 24th International Conference on Distributed Computing Systems (ICDCS'04), p.608-615, March 24-26, 2004
• 13: 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
• 14: A. Kiayias, Y. Tsiounis,and M. Yung. Traceable signatures. In C. Cachin and J. Camenisch,editors, Proceedings of Eurocrypt 2004 volume 3027 of LNCS pages 571--89. Springer-Verlag, May 2004.
• 15: S. Mitsunari,R. Sakai,and M. Kasahara. A new traitor tracing.IEICE Trans. Fundamentals E85-A(2):481--4, Feb.2002.
• 16: A. Miyaji,M. Nakabayashi,and S. Takano. New explicit conditions of elliptic curve traces for FR-reduction. IEICE Trans. Fundamentals E84-A(5):1234--43, May 2001.
• 17: D. Pointcheval and J. Stern. Security arguments for digital signatures and blind signatures. J. Cryptology 13(3): 361--96,2000.
• 18: C. Schnorr. Eficient signature generation by smart cards. J. Cryptology 4(3): 161--174, 1991.
• 19: V.Shoup. Lower bounds for discrete logarithms and related problems.In W.Fumy,editor,Proceedings of Eurocrypt 1997 volume 1233 of LNCS pages 256--66. Springer-Verlag,May 1997.
• 20: Trusted Computing Group. Trusted Computing Platform Alliance (TCPA) Main Specification, 2003. Online:www.trustedcomputinggroup.org
• 21: G. Tsudik and S. Xu. Accumulating composites and improved group signing. In C. S. Laih, editor, Proceedings of Asiacrypt 2003 volume 2894 of LNCS pages 269--86. Springer-Verlag, Dec.2003.

INDEX TERMS

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

General Terms:
Design, Theory

Keywords:
group signatures, revocation, trusted computing