Abstract
The concept of group signatures allows a group member to sign messages anonymously on behalf of the group. However, in the case of a dispute, the identity of a signature’s originator can be revealed by a designated entity. In this paper we propose a new group signature scheme that is well suited for large groups, i.e., the length of the group’s public key and of signatures do not depend on the size of the group. Our solution based on a variation of the RSA problem is more efficient than previous ones satisfying these requirements.
Part of this work was done while this author was with ETH Zurich.
Basic Research in Computer Science, Center of the Danish National Research Foundation.
Work was done while this author was with Ubilab, UBS, Switzerland.
Chapter PDF
Similar content being viewed by others
References
N. Barić and B. Pfitzmann. Collision-free accumulators and fail-stop signature schemes without trees. In W. Fumy, ed., Advances in Cryptology — EUROCRYPT’ 97, volume 1233 of LNCS, pages 480–494. Springer Verlag, 1997.
M. Bellare and P. Rogaway. Random oracles are practical: A paradigm for designing efficient protocols. In First ACM Conference on Computer and Communication Security, pages 62–73. Association for Computing Machinery, 1993.
D. Boneh and M. Franklin. Efficient generation of shared RSA keys. In B. Kaliski, ed., Advances in Cryptology — CRYPTO’ 97, volume 1296 of LNCS, pages 425–439. Springer Verlag, 1997.
J. Boyar, K. Friedl, and C. Lund. Practical zero-knowledge proofs: Giving hints and using deficiencies. Journal of Cryptology, 4(3):185–206, 1991.
J. Boyar and R. Peralta. Short discreet proofs. In U. Maurer, ed., Advances in Cryptology — EUROCRYPT’ 96, volume 1070 of LNCS, pages 131–142. Springer Verlag, 1996.
G. Brassard, D. Chaum, and C. Crépeau. Minimum disclosure proofs of knowledge. Journal of Computer and System Sciences, 37(2):156–189, Oct. 1988.
J. Camenisch. Efficient and generalized group signatures. In W. Fumy, ed., Advances in Cryptology — EUROCRYPT’ 97, volume 1233 of LNCS, pages 465–479. Springer Verlag, 1997.
J. Camenisch, U. Maurer, and M. Stadler. Digital payment systems with passive anonymity-revoking trustees. In Computer Security — ESORICS 96, volume 1146 of LNCS, pages 33–43. Springer Verlag, 1996.
J. Camenisch and M. Stadler. Efficient group signature schemes for large groups. In B. Kaliski, ed., Advances in Cryptology — CRYPTO’ 97, volume 1296 of LNCS, pages 410–424. Springer Verlag, 1997.
J. L. Camenisch. Group Signature Schemes and Payment Systems Based on the Discrete Logarithm Problem. PhD thesis, ETH Zürich, 1998. Diss. ETH No. 12520, ISBN 3-89649-286-1, Hartung Gorre Verlag, Konstanz.
R. Canetti, O. Goldreich, and S. Halevi. The random oracle methodology, revisited. In Proc. 30th Annual ACM Symposium on Theory of Computing (STOC), 1998.
D. Catalano and R. Gennaro. New efficient and secure protocols for verifiable signature sharing and other applications. In Advances in Cryptology — CRYPTO’ 98, LNCS. Springer Verlag, 1998.
A. Chan, Y. Frankel, and Y. Tsiounis. Easy come-easy go divisible cash. In Advances in Cryptology — EUROCRYPT’ 98, volume 1403 of LNCS.
D. Chaum, J.-H. Evertse, and J. van de Graaf. An improved protocol for demonstrating possession of discrete logarithms and some generalizations. In Advances in Cryptology — EUROCRYPT’ 87, pages 127–141.
D. Chaum and T. P. Pedersen. Transferred cash grows in size. In R. A. Rueppel, ed., Advances in Cryptology — EUROCRYPT’ 92, volume 658 of LNCS, pages 390–407. Springer-Verlag, 1993
D. Chaum and E. van Heyst. Group signatures. In D. W. Davies, ed., Advances in Cryptology — EUROCRYPT’ 91, volume 547 of LNCS, pages 257–265.
L. Chen and T. P. Pedersen. New group signature schemes. In Advances in Cryptology — EUROCRYPT’ 94, volume 950 of LNCS, pages 171–181.
D. Coppersmith. Finding a Small Root of a Bivariatre Interger Equation; Factoring with High Bits Known In U. Maurer, ed., Advances in Cryptology — EUROCRYPT’ 96, volume 1070 of LNCS, pages 178–189. Springer Verlag, 1996.
R. Cramer and I. Damgård. Linear zero-knowledge: A note on efficient zero-knowledge proofs and arguments. In Proc. 29th Annual ACM Symposium on Theory of Computing (STOC), pages 436–445. ACM press, 1997.
R. Cramer, I. Damgård, and B. Schoenmakers. Proofs of partial knowledge and simplified design of witness hiding protocols. In Y. G. Desmedt, ed., Advances in Cryptology — CRYPTO’ 94, volume 839 of LNCS, pages 174–187.
T. ElGamal. A public key cryptosystem and a signature scheme based on discrete logarithms. In G. R. Blakley and D. Chaum, eds., Advances in Cryptology — CRYPTO’ 84, volume 196 of LNCS, pages 10–18. Springer Verlag, 1985.
J.-H. Evertse and E. van Heyst. Which new RSA signatures can be computed from certain given RSA signatures? Journal of Cryptology, 5:41–52, 1992.
U. Feige, A. Fiat, and A. Shamir. Zero-knowledge proofs of identity. Journal of Cryptology, 1:77–94, 1988.
A. Fiat and A. Shamir. How to prove yourself: Practical solution to identification and signature problems. In A. M. Odlyzko, ed., Advances in Cryptology — CRYPTO’ 86, volume 263 of LNCS, pages 186–194. Springer Verlag, 1987.
E. Fujisaki and T. Okamoto. Statistical zero knowledge protocols to prove modular polynomial relations. In B. S. Kaliski, ed., Advances in Cryptology — CRYPTO’ 97, volume 1294 of LNCS, pages 16–30. Springer Verlag, 1997.
M. Girault. An identity-based identification scheme based on discrete logarihtms modulo a composite number. In I. B. Damgård, ed., Advances in Cryptology — EUROCRYPT’ 90, volume 473 of LNCS, pages 481–486. Springer-Verlag, 1991.
M. Girault. Self-certified public keys. In Advances in Cryptology — EUROCRYPT’ 91, volume 547 of LNCS, pages 490–497. Springer-Verlag, 1992.
J. Kilian and E. Petrank. Identity escrow. In Advances in Cryptology — CRYPTO’ 98, LNCS. Springer Verlag, 1998.
S. J. Kim, S. J. Park, and D. H. Won. Convertible group signatures. In Advances in Cryptology — ASIACRYPT’ 96, volume 1163 of LNCS, pages 311–321.
K. Koyama, U. Maurer, T. Okamoto, and S. Vanstone New Public-key Schemes Based on Elliptic Curves over the Ring Z n. In Advances in Cryptology — CRYPTO’ 91, volume 576 of LNCS, pages 252–266.
C. H. Lim and P. J. Lee. On the security of convertible group signatures. Electronics Letters, 1996.
A. Lysyanskaya and Z. Ramzan. Group blind digital signatures: A scalable solution to electronic cash. In Proc. Second Int. Conf. on Financial Cryptography, 1998.
M. Michels. Comments on some group signature schemes. TR-96-3-D, Departement of Computer Science, University of Technology, Chemnitz-Zwickau, Nov. 1996.
T. Okamoto. Provable secure and practical identification schemes and corresponding signature schemes. In E. F. Brickell, ed., Advances in Cryptology — CRYPTO’ 92, volume 740 of LNCS, pages 31–53. Springer-Verlag, 1993.
S. J. Park, I. S. Lee, and D. H. Won. A practical group signature. In Proc. of the 1995 Japan-Korea Workshop on Information Security and Cryptography.
H. Petersen. How to convert any digital signature scheme into a group signature scheme. In Security Protocols Workshop, Paris, 1997.
D. Pointcheval and J. Stern. Security proofs for signature schemes. In U. Maurer, ed., Advances in Cryptology — EUROCRYPT’ 96, volume 1070 of LNCS, pages 387–398. Springer Verlag, 1996.
G. Poupard and J. Stern. Security analysis of a practical “on the fly„ authentication and signature generation. In K. Nyberg, ed., Advances in Cryptology — EUROCRYPT’ 98, volume 1403 of LNCS, pages 422–436. Springer Verlag, 1998.
R. Rivest, A. Shamir, and L. Adleman. A method for obtaining digital signatures and public-key cryptosystems. Comm. of the ACM, 21(2):120–126, Feb. 1978.
C. P. Schnorr. Efficient signature generation for smart cards. Journal of Cryptology, 4(3):239–252, 1991.
A. Shamir. On the generation of cryptographically strong pseudorandom sequences. In ACM Trans. on Computer Systems, volume 1, pages 38–44, 1983.
M. Stadler. Cryptographic Protocols for Revocable Privacy. PhD thesis, ETH Zürich, 1996. Diss. ETH No. 11651.
J. van de Graaf and R. Peralta. A simple and secure way to show the validity of your public key. In C. Pomerance, ed., Advances in Cryptology — CRYPTO’ 87, volume 293 of LNCS, pages 128–134. Springer-Verlag, 1988.
Author information
Authors and Affiliations
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2000 Springer-Verlag Berlin Heidelberg
About this paper
Cite this paper
Camenisch, J., Michels, M. (2000). A Group Signature Scheme with Improved Efficiency (Extended Abstract). In: Ohta, K., Pei, D. (eds) Advances in Cryptology — ASIACRYPT’98. ASIACRYPT 1998. Lecture Notes in Computer Science, vol 1514. Springer, Berlin, Heidelberg. https://doi.org/10.1007/3-540-49649-1_14
Download citation
DOI: https://doi.org/10.1007/3-540-49649-1_14
Published:
Publisher Name: Springer, Berlin, Heidelberg
Print ISBN: 978-3-540-65109-3
Online ISBN: 978-3-540-49649-6
eBook Packages: Springer Book Archive