Practical forward secure group signature schemes

ABSTRACT

A group signature scheme allows a group member to sign messages anonymously on behalf of the group, while in case of a dispute, a designated entity can reveal the identity of a signature's originator. Group signature schemes can be used as a basic building block for many security applications such as electronic banking systems and electronic voting. Two important issues -- forward security and efficient revocation -- have not been addressed by prior schemes. We construct the first forward-secure group signature schemes. While satisfying all the security properties proposed in previous group signature schemes, our schemes provide a new desired security property, forward-security: while the group public key stays fixed, a group signing key of a group member evolves over time such that compromise of a group signing key of the current time period does not enable an attacker to forge group signatures pertaining to the past time periods. Such forward-security is important to mitigate the damage caused by key exposure and particularly desirable for group signature schemes because the risk of signing key exposure escalates as the size of the group increases. Our schemes are provably secure in the random oracle model and under the strong RSA and decisional Diffie Hellman assumptions.Furthermore, we extend our forward-secure group signature scheme to provide a solution for the problem of group member exclusion without the need to re-key all other group members. When a group member is excluded, he should not be able to generate valid signatures any more and yet his previous signatures remain anonymous. We provide the first solutions which support both retroactive public revocation and backward unlinkability and the signature size is independent of the number of revoked members.

REFERENCES

• 1: Michel Abdalla , Leonid Reyzin, A New Forward-Secure Digital Signature Scheme, Proceedings of the 6th International Conference on the Theory and Application of Cryptology and Information Security: Advances in Cryptology, p.116-129, December 03-07, 2000
• 2: Ross Anderson.Invited Lecture,4th ACM Computer and Communications Security,1997.
• 3: 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
• 4: 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
• 5: N.Baric and B.P .tzman.Collision-free accumulators and fail-stopsignature schemes without trees.In Advances in Cryptology - EUROCRYPT 1997 pages 480 -494. Springer-Verlag,1997.Lecture Notes in Computer Science Volume 1233.
• 6: Mihir Bellare , Sara K. Miner, A Forward-Secure Digital Signature Scheme, Proceedings of the 19th Annual International Cryptology Conference on Advances in Cryptology, p.431-448, August 15-19, 1999
• 7: Dan Boneh, The Decision Diffie-Hellman Problem, Proceedings of the Third International Symposium on Algorithmic Number Theory, p.48-63, June 21-25, 1998
• 8: F.Boudot.E .cient proofs that committed number lies in an interval.In B.Preneel,editor,Advances in Cryptology - EUROCRYPT 2000 pages 431 -444,Berlin, 2000.Springer-Verlag.Lecture Notes in Computer Science Volume 1807.
• 9: Stefan A. Brands, An Efficient Off-line Electronic Cash System Based On The Representation Problem., CWI (Centre for Mathematics and Computer Science), Amsterdam, The Netherlands, 1993
• 10: Emmanuel Bresson , Jacques Stern, Efficient Revocation in Group Signatures, Proceedings of the 4th International Workshop on Practice and Theory in Public Key Cryptography: Public Key Cryptography, p.190-206, February 13-15, 2001
• 11: Jan Camenisch , Markus Michels, A Group Signature Scheme with Improved Efficiency, Proceedings of the International Conference on the Theory and Applications of Cryptology and Information Security: Advances in Cryptology, p.160-174, October 18-22, 1998
• 12: 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
• 13: 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
• 14: David Chaum, Zero-knowledge undeniable signatures (extended abstract), Proceedings of the workshop on the theory and application of cryptographic techniques on Advances in cryptology, p.458-464, February 1991, Aarhus, Denmark
• 15: D.Chaum,J.H.Evertse,and J.van de Graaf.An improved protocol for demonstrating possession of discrete logarithms nd some generalizations.In D vid Chaum nd Wyn L.Price,editors,Advances in Cryptology - EuroCrypt '87 pages 127 -142,Berlin,1987.Springer-Verlag.Lecture Notes in Computer Science Volume 304.
• 16: D.Chaum nd E.v n Heyst.Groupsignatures.In Donald W.Davies,editor,Advances in Cryptology -EuroCrypt '91 pages 257 -265,Berlin,1991. Springer-Verlag.Lecture Notes in Computer Science Volume 547.
• 17: David Chaum , Torben P. Pedersen, Wallet Databases with Observers, Proceedings of the 12th Annual International Cryptology Conference on Advances in Cryptology, p.89-105, August 16-20, 1992
• 18: L.Chen and T.P.Pedersen.New groupsignature schemes. In Alfredo De Santis,editor,Advances in Cryptology -EuroCrypt '94 pages 171 -181,Berlin,1995. Springer-Verlag.Lecture Notes in Computer Science Volume 950.
• 19: I.Damgard.E .cient concurrent zero-knowledge in the auxiliary string model.In B.Preneel,editor,Advances in Cryptology - EUROCRYPT 2000 pages 431 -444,Berlin, 2000.Springer-Verlag.Lecture Notes in Computer Science Volume 1807.
• 20: W.Difie and M.E.Hellman.New directions in cryptography.IEEE Transactions on Information Theory 6(IT-22):644 -654,1976.
• 21: 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
• 22: 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
• 23: Amir Herzberg , Stanislaw Jarecki , Hugo Krawczyk , Moti Yung, Proactive Secret Sharing Or: How to Cope With Perpetual Leakage, Proceedings of the 15th Annual International Cryptology Conference on Advances in Cryptology, p.339-352, August 27-31, 1995
• 24: Gene Itkis , Leonid Reyzin, Forward-Secure Signatures with Optimal Signing and Verifying, Proceedings of the 21st Annual International Cryptology Conference on Advances in Cryptology, p.332-354, August 19-23, 2001
• 25: Joe Kilian , Erez Petrank, Identity Escrow, Proceedings of the 18th Annual International Cryptology Conference on Advances in Cryptology, p.169-185, August 23-27, 1998
• 26: Hugo Krawczyk, Simple forward-secure signatures from any signature scheme, Proceedings of the 7th ACM conference on Computer and communications security, p.108-115, November 01-04, 2000, Athens, Greece [doi>10.1145/352600.352617]
• 27: Anna Lysyanskaya , Zulfikar Ramzan, Group Blind Digital Signatures: A Scalable Solution to Electronic Cash, Proceedings of the Second International Conference on Financial Cryptography, p.184-197, February 23-25, 1998
• 28: Chanathip Namprempre Michel Abdalla,Sara Miner. Forward security in threshold signature schemes.In RSA 2001 2001.
• 29: Claus P. Schnorr, Efficient identification and signatures for smart cards, Proceedings of the workshop on the theory and application of cryptographic techniques on Advances in cryptology, p.688-689, November 1990, Houthalen, Belgium

INDEX TERMS

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

Additional Classification:
  D. Software
  D.4 OPERATING SYSTEMS
      D.4.6 Security and Protection
          Subjects: Authentication

  K. Computing Milieux
  K.4 COMPUTERS AND SOCIETY
      K.4.4 Electronic Commerce
          Subjects: Security; Electronic data interchange (EDI)

General Terms:
Algorithms, Design, Security