×

zbMATH — the first resource for mathematics

Foundations of fully dynamic group signatures. (English) Zbl 1346.94141
Manulis, Mark (ed.) et al., Applied cryptography and network security. 14th international conference, ACNS 2016, Guildford, UK, June 19–22, 2016. Proceedings. Cham: Springer (ISBN 978-3-319-39554-8/pbk; 978-3-319-39555-5/ebook). Lecture Notes in Computer Science 9696, 117-136 (2016).
Summary: Group signatures are a central cryptographic primitive that has received a considerable amount of attention from the cryptographic community. They allow members of a group to anonymously sign on behalf of the group. Membership is overseen by a designated group manager. There is also a tracing authority that can revoke anonymity by revealing the identity of the signer if and when needed, to enforce accountability and deter abuse. For the primitive to be applicable in practice, it needs to support fully dynamic groups, i.e. users can join and leave at any time. In this work we take a close look at existing security definitions for fully dynamic group signatures. We identify a number of shortcomings in existing security definitions and fill the gap by providing a formal rigorous security model for the primitive. Our model is general and is not tailored towards a specific design paradigm and can therefore, as we show, be used to argue about the security of different existing constructions following different design paradigms. Our definitions are stringent and when possible incorporate protection against maliciously chosen keys. In the process, we identify a subtle issue inherent to one design paradigm, where new members might try to implicate older ones by means of back-dated signatures. This is not captured by existing models. We propose some inexpensive fixes for some existing constructions to avoid the issue.
For the entire collection see [Zbl 1337.94004].

MSC:
94A62 Authentication, digital signatures and secret sharing
PDF BibTeX XML Cite
Full Text: DOI
References:
[1] Ateniese, G., Camenisch, J., Hohenberger, S., de Medeiros, B.: Practical group signatures without random oracles, IACR Cryptology ePrint Archive (2005)
[2] Ateniese, G., Camenisch, J.L., 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) · Zbl 0995.94544 · doi:10.1007/3-540-44598-6_16
[3] Abe, M., Haralambiev, K., Ohkubo, M.: Signing on elements in bilinear groups for modular protocol design. IACR Cryptology ePrint Archive (2010)
[4] Ateniese, G., Song, D., Tsudik, G.: Quasi-efficient revocation of group signatures. IACR Cryptology ePrint Archive 2001:101 (2001) · Zbl 1275.94037
[5] Boneh, D., Boyen, X., Shacham, H.: Short group signatures. In: Franklin, M. (ed.) CRYPTO 2004. LNCS, vol. 3152, pp. 41–55. Springer, Heidelberg (2004) · Zbl 1104.94044 · doi:10.1007/978-3-540-28628-8_3
[6] Brickell, E.F., Camenisch, J., Chen, L.: Direct anonymous attestation. In: Conference on Computer and Communications Security, CCS (2004) · doi:10.1145/1030083.1030103
[7] Bootle, J., Cerulli, A., Chaidos, P., Ghadafi, E., Groth, J., Petit, C.: Short accountable ring signatures based on DDH. In: Pernul, G., Y A Ryan, P., Weippl, E. (eds.) ESORICS 2015. LNCS, vol. 9326, pp. 243–265. Springer, Heidelberg (2015). doi: 10.1007/978-3-319-24174-6_13 · doi:10.1007/978-3-319-24174-6_13
[8] Bootle, J., Cerulli, A., Chaidos, P., Ghadafi, E., Groth, J.: Foundations of fully dynamic group signatures. IACR Cryptology ePrint Archive (2016) · Zbl 1346.94141
[9] 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) · Zbl 1291.94179 · doi:10.1007/978-3-642-15317-4_24
[10] 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. Springer, Heidelberg (2003) · Zbl 1038.94552
[11] Bellare, M., Rogaway, P.: Random oracles are practical: a paradigm for designing efficient protocols. In: Conference on Computer and Communications Security - CCS (1993) · doi:10.1145/168588.168596
[12] Brickell, E.: An efficient protocol for anonymously providing assurance of the container of a private key. Submitted to the Trusted Computing Group (2004)
[13] Bresson, E., Stern, J.: Efficient revocation in group signatures. In: Kim, K. (ed.) PKC 2001. LNCS, vol. 1992, pp. 190–206. Springer, Heidelberg (2001) · Zbl 0993.94553 · doi:10.1007/3-540-44586-2_15
[14] Boneh, D., Shacham, H.: Group signatures with verifier-local revocation. In: Conference on Computer and Communications Security, CCS (2004) · doi:10.1145/1030083.1030106
[15] 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) · Zbl 1079.94013 · doi:10.1007/978-3-540-30574-3_11
[16] Boyen, X., Waters, B.: Compact group signatures without random oracles. In: Vaudenay, S. (ed.) EUROCRYPT 2006. LNCS, vol. 4004, pp. 427–444. Springer, Heidelberg (2006) · Zbl 1140.94327 · doi:10.1007/11761679_26
[17] Boyen, X., Waters, B.: Full-domain subgroup hiding and constant-size group signatures. In: Okamoto, T., Wang, X. (eds.) PKC 2007. LNCS, vol. 4450, pp. 1–15. Springer, Heidelberg (2007) · Zbl 1127.94020 · doi:10.1007/978-3-540-71677-8_1
[18] Camenisch, J.L., Chaabouni, R., Shelat, A.: Efficient protocols for set membership and range proofs. In: Pieprzyk, J. (ed.) ASIACRYPT 2008. LNCS, vol. 5350, pp. 234–252. Springer, Heidelberg (2008) · Zbl 1206.94057 · doi:10.1007/978-3-540-89255-7_15
[19] Camenisch, J.L., 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) · Zbl 1116.94310 · doi:10.1007/978-3-540-30598-9_9
[20] Camenisch, J.L., 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) · Zbl 1026.94545 · doi:10.1007/3-540-45708-9_5
[21] Camenisch, J.L., 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) · Zbl 1104.94045 · doi:10.1007/978-3-540-28628-8_4
[22] Camenisch, J.L., Michels, M.: A group signature scheme with improved efficiency. In: Ohta, K., Pei, D. (eds.) ASIACRYPT 1998. LNCS, vol. 1514, pp. 160–174. Springer, Heidelberg (1998) · Zbl 0984.94519
[23] Camenisch, J.L., Stadler, M.A.: Efficient group signature schemes for large groups. In: Kaliski Jr., B.S. (ed.) CRYPTO 1997. LNCS, vol. 1294, pp. 410–424. Springer, Heidelberg (1997) · Zbl 0882.94018 · doi:10.1007/BFb0052252
[24] Chaum, D., van Heyst, E.: Group signatures. In: Davies, D.W. (ed.) EUROCRYPT 1991. LNCS, vol. 547, pp. 257–265. Springer, Heidelberg (1991) · Zbl 0791.68044 · doi:10.1007/3-540-46416-6_22
[25] Dodis, Y., Kiayias, A., Nicolosi, A., Shoup, V.: Anonymous identification in Ad Hoc groups. In: Cachin, C., Camenisch, J.L. (eds.) EUROCRYPT 2004. LNCS, vol. 3027, pp. 609–626. Springer, Heidelberg (2004) · Zbl 1122.94414 · doi:10.1007/978-3-540-24676-3_36
[26] Delerablée, C., Pointcheval, D.: Dynamic fully anonymous short group signatures. In: Nguyên, P.Q. (ed.) VIETCRYPT 2006. LNCS, vol. 4341, pp. 193–210. Springer, Heidelberg (2006) · Zbl 1295.94177 · doi:10.1007/11958239_13
[27] Furukawa, J., Imai, H.: An efficient group signature scheme from bilinear maps. In: Boyd, C., González Nieto, J.M. (eds.) ACISP 2005. LNCS, vol. 3574, pp. 455–467. Springer, Heidelberg (2005) · Zbl 1127.94366 · doi:10.1007/11506157_38
[28] Furukawa, J., Yonezawa, S.: Group signatures with separate and distributed authorities. In: Blundo, C., Cimato, S. (eds.) SCN 2004. LNCS, vol. 3352, pp. 77–90. Springer, Heidelberg (2005) · Zbl 1116.94321 · doi:10.1007/978-3-540-30598-9_6
[29] Groth, J.: Simulation-sound NIZK proofs for a practical language and constant size group signatures. In: Lai, X., Chen, K. (eds.) ASIACRYPT 2006. LNCS, vol. 4284, pp. 444–459. Springer, Heidelberg (2006) · Zbl 1172.94615 · doi:10.1007/11935230_29
[30] Groth, J.: Fully anonymous group signatures without random oracles. In: Kurosawa, K. (ed.) ASIACRYPT 2007. LNCS, vol. 4833, pp. 164–180. Springer, Heidelberg (2007) · Zbl 1153.94386 · doi:10.1007/978-3-540-76900-2_10
[31] Kiayias, A., Tsiounis, Y., Yung, M.: Traceable signatures. In: Cachin, C., Camenisch, J.L. (eds.) EUROCRYPT 2004. LNCS, vol. 3027, pp. 571–589. Springer, Heidelberg (2004) · Zbl 1122.94427 · doi:10.1007/978-3-540-24676-3_34
[32] Kiayias, A., Yung, M.: Group signatures with efficient concurrent join. In: Cramer, R. (ed.) EUROCRYPT 2005. LNCS, vol. 3494, pp. 198–214. Springer, Heidelberg (2005) · Zbl 1137.94373 · doi:10.1007/11426639_12
[33] Kiayias, A., Yung, M.: Secure scalable group signature with dynamic joins and separable authorities. IJSN 1(1/2), 24 (2006) · Zbl 05464290 · doi:10.1504/IJSN.2006.010821
[34] Langlois, A., Ling, S., Nguyen, K., Wang, H.: Lattice-based group signature scheme with verifier-local revocation. In: Krawczyk, H. (ed.) PKC 2014. LNCS, vol. 8383, pp. 345–361. Springer, Heidelberg (2014) · Zbl 1335.94063 · doi:10.1007/978-3-642-54631-0_20
[35] Libert, B., Peters, T., Yung, M.: Group signatures with almost-for-free revocation. In: Safavi-Naini, R., Canetti, R. (eds.) CRYPTO 2012. LNCS, vol. 7417, pp. 571–589. Springer, Heidelberg (2012) · Zbl 1296.94156 · doi:10.1007/978-3-642-32009-5_34
[36] Libert, B., Peters, T., Yung, M.: Scalable group signatures with revocation. In: Pointcheval, D., Johansson, T. (eds.) EUROCRYPT 2012. LNCS, vol. 7237, pp. 609–627. Springer, Heidelberg (2012) · Zbl 1296.94155 · doi:10.1007/978-3-642-29011-4_36
[37] Libert, B., Vergnaud, D.: Group signatures with verifier-local revocation and backward unlinkability in the standard model. In: Garay, J.A., Miyaji, A., Otsuka, A. (eds.) CANS 2009. LNCS, vol. 5888, pp. 498–517. Springer, Heidelberg (2009) · Zbl 1287.94081 · doi:10.1007/978-3-642-10433-6_34
[38] Nakanishi, T., Funabiki, N.: Verifier-local revocation group signature schemes with backward unlinkability from bilinear maps. In: Roy, B. (ed.) ASIACRYPT 2005. LNCS, vol. 3788, pp. 533–548. Springer, Heidelberg (2005) · Zbl 1154.94469 · doi:10.1007/11593447_29
[39] Attrapadung, N., Emura, K., Hanaoka, G., Sakai, Y.: A revocable group signature scheme from identity-based revocation techniques: achieving constant-size revocation list. In: Boureanu, I., Owesarski, P., Vaudenay, S. (eds.) ACNS 2014. LNCS, vol. 8479, pp. 419–437. Springer, Heidelberg (2014) · Zbl 1404.94037 · doi:10.1007/978-3-319-07536-5_25
[40] Nguyen, L.: Accumulators from bilinear pairings and applications. In: Menezes, A. (ed.) CT-RSA 2005. LNCS, vol. 3376, pp. 275–292. Springer, Heidelberg (2005) · Zbl 1079.94568 · doi:10.1007/978-3-540-30574-3_19
[41] Naor, D., Naor, M., Lotspiech, J.: Revocation and tracing schemes for stateless receivers. In: Kilian, J. (ed.) CRYPTO 2001. LNCS, vol. 2139, pp. 41–62. Springer, Heidelberg (2001) · Zbl 1002.94522 · doi:10.1007/3-540-44647-8_3
[42] Nguyen, L., Safavi-Naini, R.: Efficient and provably secure trapdoor-free group signature schemes from bilinear pairings. In: Lee, P.J. (ed.) ASIACRYPT 2004. LNCS, vol. 3329, pp. 372–386. Springer, Heidelberg (2004) · Zbl 1094.94530 · doi:10.1007/978-3-540-30539-2_26
[43] Song, D.X.: Practical forward secure group signature schemes. In: Conference on Computer and Communications Security, CCS (2001) · doi:10.1145/501983.502015
[44] Sakai, Y., Schuldt, J.C.N., Emura, K., Hanaoka, G., Ohta, K.: On the security of dynamic group signatures: preventing signature hijacking. In: Fischlin, M., Buchmann, J., Manulis, M. (eds.) PKC 2012. LNCS, vol. 7293, pp. 715–732. Springer, Heidelberg (2012) · Zbl 1291.94196 · doi:10.1007/978-3-642-30057-8_42
[45] Teranishi, I., Sako, K.: k-times anonymous authentication with a constant proving cost. In: Yung, M., Dodis, Y., Kiayias, A., Malkin, T. (eds.) PKC 2006. LNCS, vol. 3958, pp. 525–542. Springer, Heidelberg (2006) · Zbl 1151.94574 · doi:10.1007/11745853_34
[46] Tsudik, G., Xu, S.: Accumulating composites and improved group signing. In: Laih, C.-S. (ed.) ASIACRYPT 2003. LNCS, vol. 2894, pp. 269–286. Springer, Heidelberg (2003) · Zbl 1205.94113 · doi:10.1007/978-3-540-40061-5_16
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.