Abstract
Traditional group signatures feature a single issuer who can add users to the group of signers and a single opening authority who can reveal the identity of the group member who computed a signature. Interestingly, despite being designed for privacy-preserving applications, they require strong trust in these central authorities who constitute single points of failure for critical security properties. To reduce the trust placed on authorities, we introduce dynamic group signatures which distribute the role of issuer and opener over several entities, and support \( t _I\)-out-of-\(n_I\) issuance and \( t _O\)-out-of-\(n_O\) opening. We first define threshold dynamic group signatures and formalize their security. We then give an efficient construction relying on the pairing-based Pointcheval–Sanders (PS) signature scheme (CT-RSA 2018), which yields very short group signatures of two first-group elements and three field elements. We also give a simpler variant of our scheme in which issuance requires the participation of all \(n_I\) issuers, but still supports \( t _O\)-out-of-\(n_O\) opening. It is based on a new multi-signature variant of the PS scheme which allows for efficient proofs of knowledge and is a result of independent interest. We prove our schemes secure in the random-oracle model under a non-interactive q-type of assumption.
Access this chapter
Tax calculation will be finalised at checkout
Purchases are for personal use only
Similar content being viewed by others
References
Ateniese, G., Camenisch, J., Joye, M., Tsudik, G.: A practical and provably secure coalition-resistant group signature scheme. In: Bellare, M. (ed.) CRYPTO 2000. LNCS, vol. 1880, pp. 255–270. Springer, Heidelberg (2000). https://doi.org/10.1007/3-540-44598-6_16
Bellare, M., Fuchsbauer, G., Scafuro, A.: NIZKs with an untrusted CRS: security in the face of parameter subversion. In: Cheon, J.H., Takagi, T. (eds.) ASIACRYPT 2016, Part II. LNCS, vol. 10032, pp. 777–804. Springer, Heidelberg (2016). https://doi.org/10.1007/978-3-662-53890-6_26
Bellare, M., Micciancio, D., Warinschi, B.: Foundations of group signatures: formal definitions, simplified requirements, and a construction based on general assumptions. In: Biham, E. (ed.) EUROCRYPT 2003. LNCS, vol. 2656, pp. 614–629. Springer, Heidelberg (2003). https://doi.org/10.1007/3-540-39200-9_38
Bellare, M., Shi, H., Zhang, C.: Foundations of group signatures: the case of dynamic groups. In: Menezes, A. (ed.) CT-RSA 2005. LNCS, vol. 3376, pp. 136–153. Springer, Heidelberg (2005). https://doi.org/10.1007/978-3-540-30574-3_11
Bichsel, P., Camenisch, J., Neven, G., Smart, N.P., Warinschi, B.: Get shorty via group signatures without encryption. In: Garay, J.A., De Prisco, R. (eds.) SCN 2010. LNCS, vol. 6280, pp. 381–398. Springer, Heidelberg (2010). https://doi.org/10.1007/978-3-642-15317-4_24
Blömer, J., Juhnke, J., Löken, N.: Short group signatures with distributed traceability. In: Kotsireas, I.S., Rump, S.M., Yap, C.K. (eds.) MACIS 2015. LNCS, vol. 9582, pp. 166–180. Springer, Cham (2016). https://doi.org/10.1007/978-3-319-32859-1_14
Boldyreva, A.: Threshold signatures, multisignatures and blind signatures based on the gap-Diffie-Hellman-group signature scheme. In: Desmedt, Y.G. (ed.) PKC 2003. LNCS, vol. 2567, pp. 31–46. Springer, Heidelberg (2003). https://doi.org/10.1007/3-540-36288-6_3
Boneh, D., Boyen, X., Shacham, H.: Short group signatures. In: Franklin, M. (ed.) CRYPTO 2004. LNCS, vol. 3152, pp. 41–55. Springer, Heidelberg (2004). https://doi.org/10.1007/978-3-540-28628-8_3
Boneh, D., Drijvers, M., Neven, G.: Compact multi-signatures for smaller blockchains. In: Peyrin, T., Galbraith, S. (eds.) ASIACRYPT 2018, Part II. LNCS, vol. 11273, pp. 435–464. Springer, Cham (2018). https://doi.org/10.1007/978-3-030-03329-3_15
Boneh, D., Eskandarian, S., Fisch, B.: Post-quantum EPID group signatures from symmetric primitives. Cryptology ePrint Archive, Report 2018/261 (2018). https://eprint.iacr.org/2018/261
Boneh, D., Shacham, H.: Group signatures with verifier-local revocation. In: Atluri, V., Pfitzmann, B., McDaniel, P. (eds.) ACM CCS 2004, pp. 168–177. ACM Press, New York (2004)
Boschini, C., Camenisch, J., Neven, G.: Floppy-sized group signatures from lattices. In: Preneel, B., Vercauteren, F. (eds.) ACNS 2018. LNCS, vol. 10892, pp. 163–182. Springer, Cham (2018). https://doi.org/10.1007/978-3-319-93387-0_9
Brickell, E.F., Camenisch, J., Chen, L.: Direct anonymous attestation. In: Atluri, V., Pfitzmann, B., McDaniel, P. (eds.) ACM CCS 2004, pp. 132–145. ACM Press, New York (2004)
Camenisch, J., Chen, L., Drijvers, M., Lehmann, A., Novick, D., Urian, R.: One TPM to bind them all: fixing TPM 2.0 for provably secure anonymous attestation. In: 2017 IEEE Symposium on Security and Privacy, pp. 901–920. IEEE Computer Society Press, May 2017
Camenisch, J., Drijvers, M., Lehmann, A., Neven, G., Towa, P.: Short threshold dynamic group signatures. Cryptology ePrint Archive, Report 2020/016 (2020). https://eprint.iacr.org/2020/016
Camenisch, J., Groth, J.: Group signatures: better efficiency and new theoretical aspects. In: Blundo, C., Cimato, S. (eds.) SCN 2004. LNCS, vol. 3352, pp. 120–133. Springer, Heidelberg (2005). https://doi.org/10.1007/978-3-540-30598-9_9
Camenisch, J., Lysyanskaya, A.: Dynamic accumulators and application to efficient revocation of anonymous credentials. In: Yung, M. (ed.) CRYPTO 2002. LNCS, vol. 2442, pp. 61–76. Springer, Heidelberg (2002). https://doi.org/10.1007/3-540-45708-9_5
Camenisch, J., Lysyanskaya, A.: Signature schemes and anonymous credentials from bilinear maps. In: Franklin, M. (ed.) CRYPTO 2004. LNCS, vol. 3152, pp. 56–72. Springer, Heidelberg (2004). https://doi.org/10.1007/978-3-540-28628-8_4
Chaum, D., van Heyst, E.: Group signatures. In: Davies, D.W. (ed.) EUROCRYPT 1991. LNCS, vol. 547, pp. 257–265. Springer, Heidelberg (1991). https://doi.org/10.1007/3-540-46416-6_22
Derler, D., Slamanig, D.: Highly-efficient fully-anonymous dynamic group signatures. In: Kim, J., Ahn, G.J., Kim, S., Kim, Y., López, J., Kim, T. (eds.) ASIACCS 2018, pp. 551–565. ACM Press, New York (2018)
Desmedt, Y., Frankel, Y.: Threshold cryptosystems. In: Brassard, G. (ed.) CRYPTO 1989. LNCS, vol. 435, pp. 307–315. Springer, New York (1990). https://doi.org/10.1007/0-387-34805-0_28
Feldman, P.: A practical scheme for non-interactive verifiable secret sharing. In: 28th FOCS, pp. 427–437. IEEE Computer Society Press, October 1987
Fiat, A., Shamir, A.: How to prove yourself: practical solutions to identification and signature problems. In: Odlyzko, A.M. (ed.) CRYPTO 1986. LNCS, vol. 263, pp. 186–194. Springer, Heidelberg (1987). https://doi.org/10.1007/3-540-47721-7_12
Fuchsbauer, G., Orrù, M.: Non-interactive zaps of knowledge. In: Preneel, B., Vercauteren, F. (eds.) ACNS 2018. LNCS, vol. 10892, pp. 44–62. Springer, Cham (2018). https://doi.org/10.1007/978-3-319-93387-0_3
Garfinkel, T., Pfaff, B., Chow, J., Rosenblum, M., Boneh, D.: Terra: a virtual machine-based platform for trusted computing. In: Proceedings of the Nineteenth ACM Symposium on Operating Systems Principles, SOSP 2003. ACM (2003)
Gennaro, R., Goldfeder, S., Ithurburn, B.: Fully distributed group signatures (2019). https://www.orbs.com/wp-content/uploads/2019/04/Crypto_Group_signatures-2.pdf
Gennaro, R., Jarecki, S., Krawczyk, H., Rabin, T.: Secure distributed key generation for discrete-log based cryptosystems. In: Stern, J. (ed.) EUROCRYPT 1999. LNCS, vol. 1592, pp. 295–310. Springer, Heidelberg (1999). https://doi.org/10.1007/3-540-48910-X_21
Ghadafi, E.: Efficient distributed tag-based encryption and its application to group signatures with efficient distributed traceability. In: Aranha, D.F., Menezes, A. (eds.) LATINCRYPT 2014. LNCS, vol. 8895, pp. 327–347. Springer, Cham (2015). https://doi.org/10.1007/978-3-319-16295-9_18
Trusted Computing Group: Trusted platform module library specification, family “2.0” (2014). https://trustedcomputinggroup.org/resource/tpm-library-specification/
Guillevic, A., Masson, S., Thomé, E.: Cocks-pinch curves of embedding degrees five to eight and optimal ate pairing computation (2019). https://eprint.iacr.org/2019/431.pdf
Libert, B., Ling, S., Mouhartem, F., Nguyen, K., Wang, H.: Adaptive oblivious transfer with access control from lattice assumptions. In: Takagi, T., Peyrin, T. (eds.) ASIACRYPT 2017, Part I. LNCS, vol. 10624, pp. 533–563. Springer, Cham (2017). https://doi.org/10.1007/978-3-319-70694-8_19
Libert, B., Yung, M.: Dynamic fully forward-secure group signatures. In: Feng, D., Basin, D.A., Liu, P. (eds.) ASIACCS 2010, pp. 70–81. ACM Press, New York (2010)
Ling, S., Nguyen, K., Wang, H., Xu, Y.: Lattice-based group signatures: achieving full dynamicity with ease. In: Gollmann, D., Miyaji, A., Kikuchi, H. (eds.) ACNS 2017. LNCS, vol. 10355, pp. 293–312. Springer, Cham (2017). https://doi.org/10.1007/978-3-319-61204-1_15
Ling, S., Nguyen, K., Wang, H., Xu, Y.: Constant-size group signatures from lattices. In: Abdalla, M., Dahab, R. (eds.) PKC 2018, Part II. LNCS, vol. 10770, pp. 58–88. Springer, Cham (2018). https://doi.org/10.1007/978-3-319-76581-5_3
Manulis, M.: Democratic group signatures on example of joint ventures. Cryptology ePrint Archive, Report 2005/446 (2005). http://eprint.iacr.org/2005/446
Manulis, M., Fleischhacker, N., Günther, F., Kiefer, F., Poettering, B.: Group signatures: authentication with privacy (2012). https://www.bsi.bund.de/SharedDocs/Downloads/EN/BSI/Publications/Studies/GruPA/GruPA.pdf
Maxwell, G., Poelstra, A., Seurin, Y., Wuille, P.: Simple Schnorr multi-signatures with applications to bitcoin. Designs, Codes and Cryptography (2019). https://doi.org/10.1007/s10623-019-00608-x
Micali, S., Ohta, K., Reyzin, L.: Accountable-subgroup multisignatures: extended abstract. In: ACM CCS 2001, pp. 245–254. ACM Press, November 2001
Neven, G., Baldini, G., Camenisch, J., Neisse, R.: Privacy-preserving attribute-based credentials in cooperative intelligent transport systems. In: 2017 IEEE Vehicular Networking Conference, VNC 2017, pp. 131–138. IEEE (2017)
Petit, J., Schaub, F., Feiri, M., Kargl, F.: Pseudonym schemes in vehicular networks: a survey. IEEE Commun. Surv. Tut. 17(1), 228–255 (2015)
Pointcheval, D., Sanders, O.: Short randomizable signatures. In: Sako, K. (ed.) CT-RSA 2016. LNCS, vol. 9610, pp. 111–126. Springer, Cham (2016). https://doi.org/10.1007/978-3-319-29485-8_7
Pointcheval, D., Sanders, O.: Reassessing security of randomizable signatures. In: Smart, N.P. (ed.) CT-RSA 2018. LNCS, vol. 10808, pp. 319–338. Springer, Cham (2018). https://doi.org/10.1007/978-3-319-76953-0_17
Shamir, A.: How to share a secret. Commun. Assoc. Comput. Mach. 22(11), 612–613 (1979)
Sonnino, A., Al-Bassam, M., Bano, S., Danezis, G.: Coconut: threshold issuance selective disclosure credentials with applications to distributed ledgers. CoRR abs/1802.07344 (2018). http://arxiv.org/abs/1802.07344
International Organization for Standardization: ISO/IEC 11889: Information technology - Trusted platform module library (2015). https://www.iso.org/standard/66510.html
Whyte, W., Weimerskirch, A., Kumar, V., Hehn, T.: A security credential management system for V2V communications. In: 2013 IEEE Vehicular Networking Conference, pp. 1–8. IEEE (2013)
Zheng, D., Li, X., Ma, C., Chen, K., Li, J.: Democratic group signatures with threshold traceability. Cryptology ePrint Archive, Report 2008/112 (2008). http://eprint.iacr.org/2008/112
Acknowledgements
Most of the work of the first four authors was done while being at IBM Research – Zurich. The authors thank David Pointcheval for helpful discussions. This work was supported by the CHIST-ERA USEIT project and the EU H2020 Research and Innovation Program under Grant Agreement No. 786725 (OLYMPUS).
Author information
Authors and Affiliations
Corresponding author
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2020 Springer Nature Switzerland AG
About this paper
Cite this paper
Camenisch, J., Drijvers, M., Lehmann, A., Neven, G., Towa, P. (2020). Short Threshold Dynamic Group Signatures. In: Galdi, C., Kolesnikov, V. (eds) Security and Cryptography for Networks. SCN 2020. Lecture Notes in Computer Science(), vol 12238. Springer, Cham. https://doi.org/10.1007/978-3-030-57990-6_20
Download citation
DOI: https://doi.org/10.1007/978-3-030-57990-6_20
Published:
Publisher Name: Springer, Cham
Print ISBN: 978-3-030-57989-0
Online ISBN: 978-3-030-57990-6
eBook Packages: Computer ScienceComputer Science (R0)