Abstract
Group signatures, introduced by Chaum and van Heijst at Eurocrypt’91, allow members of a group to make signatures on behalf of the group while remaining anonymous. Furthermore, in case of disputes a designated group authority, who is given some auxiliary information, can identify the signer. Chaum and van Heijst presented four schemes, one of which protects the anonymity of the signer information-theoretically. However, this scheme as well as subsequent schemes with this property requires that the signer basically needs a new secret key for each signature and that the group authority secretly stores a very long string.
This paper analyses such group signature schemes and obtains lower bounds on the length of both the secret keys of the group members and the auxiliary information of the authority depending on the number of signatures each is allowed to make and the number of group members. These bounds are optimal as they are met by the scheme suggested by Chaum and van Heijst.
Work done while visiting Aarhus University
Supproted by Carlsbergfondet
Chapter PDF
Keywords
These keywords were added by machine and not by the authors. This process is experimental and the keywords may be updated as the learning algorithm improves.
References
C. Boyd. Digital Multisignatures. In Cryptography and Coding, pages 241–246, 1989.
D. Chaum and E. van Heijst. Group Signatures. In Advances in Cryptology-proceedings of EUROCRYPT 91, Lecture Notes in Computer Science #547, pages 257–265. Springer-Verlag, 1991.
D. Chaum and S. Roijakkers Unconditionally Secure Digital Signatures In Advances in Cryptology — proceedings of CRYPTO 90. Lecture Notes in Computer Science #537, pages 206–214, 1991.
L. Chen and T. P. Pedersen New Group Signature Schemes. In Advances in Cryptology — Proceedings of Eurocrypt’ 94.
L. Chen and T.P. Pedersen. Group Signatures: Unconditional Security for Members. Technical Report DAIMI PB-481, Aarhus University, September 1994.
R. A. Croft and S. P. Harris. Public-Key Cryptography and Reusable Shared Secrets. In Cryptography and Coding, pages 189–201, 1989.
Y. Desmedt. Threshold Cryptosystems. In Advances in Cryptology — proceedings of AUSCRYPT 92, Lecture Notes in Computer Science #718, pages 3–14, 1993.
S. Goldwasser, S. Micali, and R. L. Rivest. A Digital Signature Scheme Secure Against Adaptive Chosen Message Attack. SIAM Journal of Computing, 17(2):281–308, April 1988.
S. Goldwasser, S. Micali, and C. Rackoff. The Knowledge Complexity of Interactive Proof-Systems. SIAM Journal of Computation, 18(1):186–208, 1989.
E. van Heijst. Special Signature Schemes. PhD thesis, CWI, 1992.
T. Okamoto. A Digital Multisignature Scheme Using Bijective Public-Key Cryptosystems. ACM Trans. on Comp. Sys., 6(8):432–441, 1988.
K. Ohta and T. Okamoto. A Digital Multisignature Scheme Based on the Fiat-Shamir Scheme. In Advances in Cryptology — proceedings of ASI ACRYPT 91, Lecture Notes in Computer Science #739, pages 139–148. Springer-Verlag, 1993.
M. Waidner and B. Pfitzmann. The Dining Cryptographers in the Disco: Unconditional Sender and Recipient Untraceability with Computationally Secure Serviceability In Advances in Cryptology — proceedings of Eurocrypt 89. Lecture Notes in Computer Science #434, page 690, 1990.
Author information
Authors and Affiliations
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 1995 Springer-Verlag Berlin Heidelberg
About this paper
Cite this paper
Chen, L., Pedersen, T.P. (1995). On the Efficiency of Group Signatures Providing Information-Theoretic Anonymity. In: Guillou, L.C., Quisquater, JJ. (eds) Advances in Cryptology — EUROCRYPT ’95. EUROCRYPT 1995. Lecture Notes in Computer Science, vol 921. Springer, Berlin, Heidelberg. https://doi.org/10.1007/3-540-49264-X_4
Download citation
DOI: https://doi.org/10.1007/3-540-49264-X_4
Published:
Publisher Name: Springer, Berlin, Heidelberg
Print ISBN: 978-3-540-59409-3
Online ISBN: 978-3-540-49264-1
eBook Packages: Springer Book Archive