Abstract
This paper provides theoretical foundations for the group signature primitive. We introduce strong, formal definitions for the core requirements of anonymity and traceability. We then show that these imply the large set of sometimes ambiguous existing informal requirements in the literature, thereby unifying and simplifying the requirements for this primitive. Finally we prove the existence of a construct meeting our definitions based only on the sole assumption that trapdoor permutations exist.
Chapter PDF
Similar content being viewed by others
References
R. Anderson. Invited talk. Fourth Annual Conference on Computer and Communications Security, 1997.
G. Ateniese, J. Camenisch, M. Joye, and G. Tsudik. A practical and provably secure coalition-resistant group signature scheme. In M. Bellare, editor, CRYPTO’00, volume 1880 of LNCS, pages 255–270. Springer-Verlag, 2000.
G. Ateniese and G. Tsudik. Quasi-efficient revocation in group signature schemes. Available at http://eprint.iacr.org/2001/101.pdf.
G. Ateniese and G. Tsudik. Group signatures à la carte. In ACM Symposium on Discrete Algorithms, pages 848–849. ACM Press, 1999.
G. Ateniese and G. Tsudik. Some open issues and directions in group signature. In Financial Crypto’99, volume 1648 of LNCS, pages 196–211. Springer-Verlag, 1999.
M. Bellare and S. Micali. How to sign given any trapdoor permutation. Journal of ACM, 39(1): 214–233, January 1992.
M. Bellare, D. Micciancio, and B. Warinschi. Full version of this paper. Available at http://www.cs.ucsd.edu/users/bogdan.
M. Bellare and S. Miner. A forward-secure digital signature scheme. In M. Wiedner, editor, CRYPTO’99, volume 1666 of LNCS, pages 431–448. Springer-Verlag, 1999.
M. Blum, A. DeSantis, S. Micali, and G. Persiano. Non-interactive zero-knowledge proof systems. SIAM Journal on Computing, 20(6):1084–1118, December 1991.
E. Bresson and J. Stern. Efficient revocation in group signatures. In PKC’2001, volume 1992 of LNCS, pages 190–206. Springer-Verlag, 2001.
J. Camenisch. Efficient and generalized group signature. In EUROCRYPT’97, volume 1233 of LNCS, pages 465–479. Springer-Verlag, 1997.
J. Camenisch and M. Michels. A group signature scheme with improved efficiency. In K. Ohta and D. Pei, editors, ASIACRYPT’98, volume 1514 of LNCS, pages 160–174. Springer-Verlag, 1999.
J. Camenisch and M. Stadler. Efficient group signatures schemes for large groups. In B. Kaliski, editor, CRYPTO’97, volume 1294 of LNCS, pages 410–424. Springer-Verlag, 1997.
D. Chaum and E. van Heyst. Group signatures. In D. W. Davis, editor, EUROCRYPT’91, volume 547 of LNCS, pages 257–265. Springer-Verlag, 1991.
L. Chen and T. P. Pedersen. New group signature schemes. In A. DeSantis, editor, EUROCRYPT’94, volume 950 of LNCS, pages 171–181. Springer-Verlag, 1994.
D. Dolev, C. Dwork, and M. Naor. Nonmalleable cryptography. SIAM Journal of Computing, 30(2): 391–437, 2000.
U. Feige, D. Lapidot, and A. Shamir. Multiple non-interactive zero-knowledge proofs under general assumptions. SIAM Journal on Computing, 29(1):1–28, September 1999.
O. Goldreich. A uniform-complexity treatment of encryption and zero-knowledge. Journal of Cryptology, 6(1):21–53, 1993.
S. Goldwasser and S. Micali. Probabilistic encryption. Journal of Computer and System Science, 28: 270–299, 1984.
S. Goldwasser, S. Micali, and R. Rivest. A digital signature scheme secure against adaptive chosen-message attacks. SIAM Journal of Computing, 17(2):281–308, April 1988.
S. Micali, C. Rackoff, and B. Sloan. The notion of security for probabilistic cryptosystems. SIAM Journal of Computing, 17(2):412–426, 1988.
M. Naor and M. Yung. Public-key cryptosystems provably secure against chosen ciphertext attacks. In STOC’90, pages 427–437, 1990.
N. I. of Standards and Technology. Dictionary of algorithms and data structures. http://www.nist.gov/dads/.
H. Petersen. How to convert any digital signature scheme into a group signature scheme. In Proceedings of Security Protocols Workshop’97, pages 177–190, 1997.
C. Rackoff and D. Simon. Non-interactive zero-knowledge proof of knowledge and chosen ciphertext attack. In CRYPTO’91, pages 433–444, 1992.
J. Rompel. One-way functions are necessary and sufficient for secure signatures. In 22nd Annual Symposium on Theory of Computing, pages 387–394. ACM, ACM Press, 1990.
A. Sahai. Non-malleable non-interactive zero knowledge and adaptive chosen-ciphertext security. In FOCS’99, pages 543–553, 1999.
D. Song. Practical forward-secure group signature schemes. In ACM Symposium on Computer and Communication Security, pages 225–234, November 2001.
Author information
Authors and Affiliations
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2003 International Association for Cryptologic Research
About this paper
Cite this paper
Bellare, M., Micciancio, D., Warinschi, B. (2003). Foundations of Group Signatures: Formal Definitions, Simplified Requirements, and a Construction Based on General Assumptions. In: Biham, E. (eds) Advances in Cryptology — EUROCRYPT 2003. EUROCRYPT 2003. Lecture Notes in Computer Science, vol 2656. Springer, Berlin, Heidelberg. http://doi.org/10.1007/3-540-39200-9_38
Download citation
DOI: http://doi.org/10.1007/3-540-39200-9_38
Published:
Publisher Name: Springer, Berlin, Heidelberg
Print ISBN: 978-3-540-14039-9
Online ISBN: 978-3-540-39200-2
eBook Packages: Springer Book Archive