Article

Practical forward secure group signature schemes

Author:

Dawn Xiaodong SongAuthors Info & Claims

CCS '01: Proceedings of the 8th ACM conference on Computer and Communications Security

Pages 225 - 234

https://doi.org/10.1145/501983.502015

Published: 05 November 2001 Publication History

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 and Leonid Reyzin.A new forward-secure digital signature scheme.In ASIACRYPT pages 116 -129, 2000.]]

Digital Library

[2]

Ross Anderson.Invited Lecture,4th ACM Computer and Communications Security,1997.]]

[3]

Giuseppe Ateniese,Jan Camenisch,Marc Joye,and Gene Tsudik.A practical and prov bly secure coalition-resistant groupsignature scheme.In M.Bellare,editor,Advances in Cryptology - CRYPTO 2000 pages 255 -270. Springer-Verlag,2000.Lecture Notes in Computer Science Volume 1880.]]

Digital Library

[4]

Giuseppe Ateniese nd Gene Tsudik.Some open issues and new directions in groupsignatures.In Financial Crypto 1999 Springer-Verlag,1999.]]

Digital Library

[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 and Sara Miner.A forward-secure digital signature scheme.In Advances in Cryptology -CRYPTO'99 1999.]]

Digital Library

[7]

D.Boneh.The decision difie-hellman problem.In Proceedings of the Third Algorithmic Number Theory Symposium pages 48 -63.Springer-Verlag,1998.Lecture Notes in Computer Science Volume 1423.]]

Digital Library

[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 Brands.An e .cient o .-line electronic cash system based on the representation problem.Technical Report CS-R9323,CWI,1993.]]

Digital Library

[10]

Emmanuel Bresson nd Jacques Stern.E .cient revocation in groupsignatures.In Proceeding of Public Key Cryptography (PKC 2001),2001.]]

Digital Library

[11]

J.Camenisch nd M.Michels.A groupsignature with improved e .ciency.In Advances in Cryptology -ASIACRYPT '98 pages 160 -174,Berlin,1998. Springer-Verlag.Lecture Notes in Computer Science Volume 1514.]]

Digital Library

[12]

J.Camenisch nd M.Michels.Separability nd e .ciency for generic groupsignature schemes.In M.Wiener,editor, Advances in Cryptology - Crypto '99 pages 413 -430, Berlin,1999.Springer-Verlag.Lecture Notes in Computer Science Volume 1666.]]

Digital Library

[13]

J.Camenisch nd M.Stadler.E .cient groupsignature schemes for large groups.In B.Kaliski,editor,Advances in Cryptology - CRYPTO'97 pages 410 -424.Springer-Verlag, 1997.Lecture Notes in Computer Science Volume 1296.]]

Digital Library

[14]

D.Chaum.Zero-knowledge undeniable signatures (extended bstract).In Ivan B.Damg~rd,editor,Advances in Cryptology - EuroCrypt '90 pages 458 -464,Berlin, 1990.Springer-Verlag.Lecture Notes in Computer Science Volume 473.]]

Digital Library

[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]

D.Chaum nd T.P.Pedersen.Wallet databases with observers.In Ernest F.Brickell,editor,Advances in Cryptology - Crypto '92 pages 89 -105,Berlin,1992. Springer-Verlag.Lecture Notes in Computer Science Volume 740.]]

Digital Library

[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]

A.Fiat and A.Shamir.How to prove yourself:practical solutions to identification and signature problems.In A.M. Odlyzko,editor,Advances in Cryptology - Crypto '86 pages 186 -194,Berlin,1986.Springer-Verlag.Lecture Notes in Computer Science Volume 263.]]

Digital Library

[22]

E.Fujisaki and T.Ok moto.Statistical zero-knowledge protocols to prove modular polynomial relations.In B.Kaliski,editor,Advances in Cryptology - Crypto '97 pages 16 -30,Berlin,1997.Springer-Verlag.Lecture Notes in Computer Science Volume 1294.]]

Digital Library

[23]

A.Herzberg,M.Jrecki,H.Krwczyk,ndM.Yung. Proactive secret sharing or:How to cope with perpetual leakage.In Advances in Cryptology - CRYPTO'95 Springer-Verlag,1995.Lecture Notes in Computer Science Volume 1807.]]

Digital Library

[24]

Gene Itkis nd Leonid Reyzin.Forw rd-secure signatures with optimal signing and verifying.In To Appear i n CRYPTO 2001 2001.]]

Digital Library

[25]

J.Kilian nd E.Petrank.Identity escrow.In Advances in Cryptology - CRYPTO'98 pages 169 -185.Springer-Verlag, 1998.Lecture Notes in Computer Science Volume 1642.]]

Digital Library

[26]

Hugo Krawczyk.Simple forward-secure signatures from any signature scheme.In 7th ACM Conference on Computer and Communication Security 2000.]]

Digital Library

[27]

A.Lysy nsk y and Z.Ramzan.Groupblind digital signatures:A scalable solution to electronic cash.In Financial Cryptography (FC'98),pages 184 -197. Springer-Verlag,1998.Lecture Notes in Computer Science Volume 1465.]]

Digital Library

[28]

Chanathip Namprempre Michel Abdalla,Sara Miner. Forward security in threshold signature schemes.In RSA 2001 2001.]]

[29]

C.P.Schnorr. Efficient identification and signatures for smart cards.In Jean-Jacques Quisquater and Joos Vandew lle,editors,Advances in Cryptology - EuroCrypt '89 pages 688 -689,Berlin,1989.Springer-Verlag.Lecture Notes in Computer Science Volume 434.]]

Digital Library

Cited By

Chen SChen J(2023)Lattice-based group signatures with forward security for anonymous authenticationHeliyon10.1016/j.heliyon.2023.e149179:4(e14917)Online publication date: Apr-2023
https://doi.org/10.1016/j.heliyon.2023.e14917
Jiao ZZhou FWang QSun J(2022)RPVC: A Revocable Publicly Verifiable Computation Solution for Edge ComputingSensors10.3390/s2211401222:11(4012)Online publication date: 25-May-2022
https://doi.org/10.3390/s22114012
Zhang YLiu XHu YGan YJia H(2022)Verifier-local revocation group signatures with backward unlinkability from lattices格上后向无关联性安全的验证者本地撤销群签名Frontiers of Information Technology & Electronic Engineering10.1631/FITEE.200050723:6(876-892)Online publication date: 5-Jul-2022
https://doi.org/10.1631/FITEE.2000507
Show More Cited By

Index Terms

Practical forward secure group signature schemes
1. Applied computing
  1. Electronic commerce
    1. Electronic data interchange
    2. Secure online transactions
2. Security and privacy

Recommendations

Forward-secure multisignature and blind signature schemes

Forward-secure signature schemes address the key exposure problem, in which all previously generated signatures are still considered to be valid even after the secret key is compromised. Multisignature scheme allow any subgroup of a group of users to ...
Provably secure delegation-by-certification proxy signature schemes
InfoSecu '04: Proceedings of the 3rd international conference on Information security

In this paper, we first show that a previous proxy signature scheme by delegation with certificate is not provably secure under adaptive-chosen message attacks and adaptive-chosen warrant attacks. The scheme does not provide the strong undeniability. ...
Fine-grained forward-secure signature schemes without random oracles
Special issue: Coding and cryptography

We propose the concept of fine-grained forward-secure signature schemes. Such signature schemes not only provide non-repudiation w.r.t. past time periods the way ordinary forward-secure signature schemes do but, in addition, allow the signer to specify ...

Comments

Information & Contributors

Information

Published In

cover image ACM Conferences

CCS '01: Proceedings of the 8th ACM conference on Computer and Communications Security

November 2001

274 pages

ISBN:1581133855

DOI:10.1145/501983

Conference Chair:
Mike Reiter
Bell Labs, USA
,
Editor:
Pierangela Samarati
University of Milan, Italy

Copyright © 2001 ACM.

Permission to make digital or hard copies of all or part of this work for personal or classroom use is granted without fee provided that copies are not made or distributed for profit or commercial advantage and that copies bear this notice and the full citation on the first page. Copyrights for components of this work owned by others than ACM must be honored. Abstracting with credit is permitted. To copy otherwise, or republish, to post on servers or to redistribute to lists, requires prior specific permission and/or a fee. Request permissions from [email protected]

Sponsors

SIGSAC: ACM Special Interest Group on Security, Audit, and Control

Publisher

Association for Computing Machinery

New York, NY, United States

Publication History

Published: 05 November 2001

Permissions

Request permissions for this article.

Request Permissions

Check for updates

Qualifiers

Article

Conference

CCS01

Sponsor:

SIGSAC

CCS01: 8th ACM Conference on Computer and Communications Security

November 5 - 8, 2001

PA, Philadelphia, USA

Acceptance Rates

CCS '01 Paper Acceptance Rate 27 of 153 submissions, 18%;

Overall Acceptance Rate 1,261 of 6,999 submissions, 18%

Upcoming Conference

CCS '24

Sponsor:
sigsac

ACM SIGSAC Conference on Computer and Communications Security

October 14 - 18, 2024

Salt Lake City , UT , USA

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

104
Total Citations
View Citations
1,318
Total Downloads

Downloads (Last 12 months)25
Downloads (Last 6 weeks)3

Reflects downloads up to 21 Sep 2024

Other Metrics

View Author Metrics

Citations

Cited By

Chen SChen J(2023)Lattice-based group signatures with forward security for anonymous authenticationHeliyon10.1016/j.heliyon.2023.e149179:4(e14917)Online publication date: Apr-2023
https://doi.org/10.1016/j.heliyon.2023.e14917
Jiao ZZhou FWang QSun J(2022)RPVC: A Revocable Publicly Verifiable Computation Solution for Edge ComputingSensors10.3390/s2211401222:11(4012)Online publication date: 25-May-2022
https://doi.org/10.3390/s22114012
Zhang YLiu XHu YGan YJia H(2022)Verifier-local revocation group signatures with backward unlinkability from lattices格上后向无关联性安全的验证者本地撤销群签名Frontiers of Information Technology & Electronic Engineering10.1631/FITEE.200050723:6(876-892)Online publication date: 5-Jul-2022
https://doi.org/10.1631/FITEE.2000507
Liao ZHuang QChen X(2022)A fully dynamic forward-secure group signature from latticeCybersecurity10.1186/s42400-022-00122-z5:1Online publication date: 2-Oct-2022
https://doi.org/10.1186/s42400-022-00122-z
An ZPan JWen YZhang F(2022)Forward-Secure Revocable Secret Handshakes from LatticesPost-Quantum Cryptography10.1007/978-3-031-17234-2_21(453-479)Online publication date: 21-Sep-2022
https://doi.org/10.1007/978-3-031-17234-2_21
Pan JChen XZhang FSusilo W(2021)Forward-Secure Group Encryptions from LatticesInformation Security and Privacy10.1007/978-3-030-90567-5_31(610-629)Online publication date: 4-Nov-2021
https://doi.org/10.1007/978-3-030-90567-5_31
Diaz JLehmann A(2021)Group Signatures with User-Controlled and Sequential LinkabilityPublic-Key Cryptography – PKC 202110.1007/978-3-030-75245-3_14(360-388)Online publication date: 1-May-2021
https://doi.org/10.1007/978-3-030-75245-3_14
Li CWang LXu QLi DLiu PLi X(2020)GroupchainProceedings of the 2020 4th International Conference on High Performance Compilation, Computing and Communications10.1145/3407947.3407959(42-49)Online publication date: 27-Jun-2020
https://dl.acm.org/doi/10.1145/3407947.3407959
Bootle JCerulli AChaidos PGhadafi EGroth J(2020)Foundations of Fully Dynamic Group SignaturesJournal of Cryptology10.1007/s00145-020-09357-wOnline publication date: 2-Jun-2020
https://doi.org/10.1007/s00145-020-09357-w
Canard SGeorgescu AKaim GRoux-Langlois ATraoré J(2020)Constant-Size Lattice-Based Group Signature with Forward Security in the Standard ModelProvable and Practical Security10.1007/978-3-030-62576-4_2(24-44)Online publication date: 20-Nov-2020
https://doi.org/10.1007/978-3-030-62576-4_2
Show More Cited By

View Options

Get Access

Login options

Check if you have access through your login credentials or your institution to get full access on this article.

Full Access

Get this Publication

View options

PDF

View or Download as a PDF file.

eReader

View online with eReader.

Media

Figures

Other

Tables

View Table of Contents