Lattice-based group signatures: achieving full dynamicity with ease. (English) Zbl 1522.94070
Gollmann, Dieter (ed.) et al., Applied cryptography and network security. 15th international conference, ACNS 2017, Kanazawa, Japan, July 10–12, 2017. Proceedings. Cham: Springer. Lect. Notes Comput. Sci. 10355, 293-312 (2017).
Summary: Lattice-based group signature is an active research topic in recent years. Since the pioneering work byS. D. Gordon et al. [Lect. Notes Comput. Sci. 6477, 395–412 (2010; Zbl 1253.94071)], eight other schemes have been proposed, providing various improvements in terms of security, efficiency and functionality. However, most of the existing constructions work only in the static setting where the group population is fixed at the setup phase. The only two exceptions are the schemes by A. Langlois et al. [Lect. Notes Comput. Sci. 8383, 345–361 (2014; Zbl 1335.94063)] that handles user revocations (but new users cannot join), and by B. Libert et al. [Lect. Notes Comput. Sci. 10032, 373–403 (2016; Zbl 1407.94136)] which addresses the orthogonal problem of dynamic user enrollments (but users cannot be revoked).
In this work, we provide the first lattice-based group signature that offers full dynamicity (i.e., users have the flexibility in joining and leaving the group), and thus, resolve a prominent open problem posed by previous works. Moreover, we achieve this non-trivial feat in a relatively simple manner. Starting with B. Libert et al.’s fully static construction [Lect. Notes Comput. Sci. 9666, 1–31 (2016; Zbl 1369.94552)] – which is arguably the most efficient lattice-based group signature to date, we introduce simple-but-insightful tweaks that allow to upgrade it directly into the fully dynamic setting. More startlingly, our scheme even produces slightly shorter signatures than the former. The scheme satisfies the strong security requirements of J. Bootle et al.’s model [Lect. Notes Comput. Sci. 9696, 117–136 (2016; Zbl 1346.94141)], under the Short Integer Solution (SIS) and the Learning With Errors (LWE) assumptions.
For the entire collection see [Zbl 1366.94005].
In this work, we provide the first lattice-based group signature that offers full dynamicity (i.e., users have the flexibility in joining and leaving the group), and thus, resolve a prominent open problem posed by previous works. Moreover, we achieve this non-trivial feat in a relatively simple manner. Starting with B. Libert et al.’s fully static construction [Lect. Notes Comput. Sci. 9666, 1–31 (2016; Zbl 1369.94552)] – which is arguably the most efficient lattice-based group signature to date, we introduce simple-but-insightful tweaks that allow to upgrade it directly into the fully dynamic setting. More startlingly, our scheme even produces slightly shorter signatures than the former. The scheme satisfies the strong security requirements of J. Bootle et al.’s model [Lect. Notes Comput. Sci. 9696, 117–136 (2016; Zbl 1346.94141)], under the Short Integer Solution (SIS) and the Learning With Errors (LWE) assumptions.
For the entire collection see [Zbl 1366.94005].
Keywords:
lattice-based group signatures; full dynamicity; updatable Merkle trees; Stern-like zero-knowledge protocolsReferences:
| [1] | Ajtai, M.: Generating hard instances of lattice problems (extended abstract). In: STOC 1996, pp. 99-108. ACM (1996) · Zbl 0921.11071 |
| [2] | 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). doi:10.1007/3-540-44598-6_16 · Zbl 0995.94544 · doi:10.1007/3-540-44598-6_16 |
| [3] | Barić, N., Pfitzmann, B.: Collision-free accumulators and fail-stop signature schemes without trees. In: Fumy, W. (ed.) EUROCRYPT 1997. LNCS, vol. 1233, pp. 480-494. Springer, Heidelberg (1997). doi:10.1007/3-540-69053-0_33 |
| [4] | 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). doi:10.1007/3-540-39200-9_38 · Zbl 1038.94552 · doi:10.1007/3-540-39200-9_38 |
| [5] | 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). doi:10.1007/978-3-540-30574-3_11 · Zbl 1079.94013 · doi:10.1007/978-3-540-30574-3_11 |
| [6] | Boneh, D., Shacham, H.: Group signatures with verifier-local revocation. In: ACM CCCS 2004, pp. 168-177. ACM (2004) |
| [7] | Bootle, J., Cerulli, A., Chaidos, P., Ghadafi, E., Groth, J.: Foundations of fully dynamic group signatures. In: Manulis, M., Sadeghi, A.-R., Schneider, S. (eds.) ACNS 2016. LNCS, vol. 9696, pp. 117-136. Springer, Cham (2016). doi:10.1007/978-3-319-39555-5_7. Full version: https://eprint.iacr.org/2016/368.pdf · Zbl 1346.94141 |
| [8] | Bootle, J., Cerulli, A., Chaidos, P., Ghadafi, E., Groth, J., Petit, C.: Short accountable ring signatures based on DDH. In: Pernul, G., Ryan, P.Y.A., Weippl, E. (eds.) ESORICS 2015. LNCS, vol. 9326, pp. 243-265. Springer, Cham (2015). doi:10.1007/978-3-319-24174-6_13 · Zbl 1499.94054 · doi:10.1007/978-3-319-24174-6_13 |
| [9] | Boyen, X.: Lattice mixing and vanishing trapdoors: a framework for fully secure short signatures and more. In: Nguyen, P.Q., Pointcheval, D. (eds.) PKC 2010. LNCS, vol. 6056, pp. 499-517. Springer, Heidelberg (2010). doi:10.1007/978-3-642-13013-7_29 · Zbl 1281.94074 · doi:10.1007/978-3-642-13013-7_29 |
| [10] | Bresson, E., Stern, J.: Efficient revocation in group signatures. In: Kim, K. (ed.) PKC 2001. LNCS, vol. 1992, pp. 190-206. Springer, Heidelberg (2001). doi:10.1007/3-540-44586-2_15 · Zbl 0993.94553 · doi:10.1007/3-540-44586-2_15 |
| [11] | 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). doi:10.1007/3-540-45708-9_5 · Zbl 1026.94545 · doi:10.1007/3-540-45708-9_5 |
| [12] | Camenisch, J., Neven, G., Rückert, M.: Fully anonymous attribute tokens from lattices. In: Visconti, I., Prisco, R. (eds.) SCN 2012. LNCS, vol. 7485, pp. 57-75. Springer, Heidelberg (2012). doi:10.1007/978-3-642-32928-9_4 · Zbl 1310.94177 · doi:10.1007/978-3-642-32928-9_4 |
| [13] | Cash, D., Hofheinz, D., Kiltz, E., Peikert, C.: Bonsai trees, or how to delegate a lattice basis. In: Gilbert, H. (ed.) EUROCRYPT 2010. LNCS, vol. 6110, pp. 523-552. Springer, Heidelberg (2010). doi:10.1007/978-3-642-13190-5_27 · Zbl 1280.94043 · doi:10.1007/978-3-642-13190-5_27 |
| [14] | Chaum, D., Heyst, E.: Group signatures. In: Davies, D.W. (ed.) EUROCRYPT 1991. LNCS, vol. 547, pp. 257-265. Springer, Heidelberg (1991). doi:10.1007/3-540-46416-6_22 · Zbl 0791.68044 |
| [15] | Cheng, S., Nguyen, K., Wang, H.: Policy-based signature scheme from lattices. Des. Codes Cryptogr. 81(1), 43-74 (2016) · Zbl 1379.94052 · doi:10.1007/s10623-015-0126-y |
| [16] | Delerablée, C., Pointcheval, D.: Dynamic fully anonymous short group signatures. In: Nguyen, P.Q. (ed.) VIETCRYPT 2006. LNCS, vol. 4341, pp. 193-210. Springer, Heidelberg (2006). doi:10.1007/11958239_13 · Zbl 1295.94177 · doi:10.1007/11958239_13 |
| [17] | 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). doi:10.1007/3-540-47721-7_12 · Zbl 0636.94012 |
| [18] | Gentry, C., Peikert, C., Vaikuntanathan, V.: Trapdoors for hard lattices and new cryptographic constructions. In: STOC 2008, pp. 197-206. ACM (2008) · Zbl 1231.68124 |
| [19] | Gordon, S.D., Katz, J., Vaikuntanathan, V.: A group signature scheme from lattice assumptions. In: Abe, M. (ed.) ASIACRYPT 2010. LNCS, vol. 6477, pp. 395-412. Springer, Heidelberg (2010). doi:10.1007/978-3-642-17373-8_23 · Zbl 1253.94071 · doi:10.1007/978-3-642-17373-8_23 |
| [20] | Groth, J.: Fully anonymous group signatures without random oracles. In: Kurosawa, K. (ed.) ASIACRYPT 2007. LNCS, vol. 4833, pp. 164-180. Springer, Heidelberg (2007). doi:10.1007/978-3-540-76900-2_10 · Zbl 1153.94386 · doi:10.1007/978-3-540-76900-2_10 |
| [21] | Kawachi, A., Tanaka, K., Xagawa, K.: Multi-bit cryptosystems based on lattice problems. In: Okamoto, T., Wang, X. (eds.) PKC 2007. LNCS, vol. 4450, pp. 315-329. Springer, Heidelberg (2007). doi:10.1007/978-3-540-71677-8_21 · Zbl 1161.94411 · doi:10.1007/978-3-540-71677-8_21 |
| [22] | Kawachi, A., Tanaka, K., Xagawa, K.: Concurrently secure identification schemes based on the worst-case hardness of lattice problems. In: Pieprzyk, J. (ed.) ASIACRYPT 2008. LNCS, vol. 5350, pp. 372-389. Springer, Heidelberg (2008). doi:10.1007/978-3-540-89255-7_23 · Zbl 1206.94076 · doi:10.1007/978-3-540-89255-7_23 |
| [23] | Kiayias, A., Yung, M.: Secure scalable group signature with dynamic joins and separable authorities. Int. J. Secur. Netw. 1(1), 24-45 (2006) · doi:10.1504/IJSN.2006.010821 |
| [24] | Laguillaumie, F., Langlois, A., Libert, B., Stehlé, D.: Lattice-based group signatures with logarithmic signature size. In: Sako, K., Sarkar, P. (eds.) ASIACRYPT 2013. LNCS, vol. 8270, pp. 41-61. Springer, Heidelberg (2013). doi:10.1007/978-3-642-42045-0_3 · Zbl 1314.94104 · doi:10.1007/978-3-642-42045-0_3 |
| [25] | 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). doi:10.1007/978-3-642-54631-0_20 · Zbl 1335.94063 · doi:10.1007/978-3-642-54631-0_20 |
| [26] | Libert, B., Ling, S., Mouhartem, F., Nguyen, K., Wang, H.: Signature schemes with efficient protocols and dynamic group signatures from lattice assumptions. In: Cheon, J.H., Takagi, T. (eds.) ASIACRYPT 2016. LNCS, vol. 10032, pp. 373-403. Springer, Heidelberg (2016). doi:10.1007/978-3-662-53890-6_13 · Zbl 1407.94136 · doi:10.1007/978-3-662-53890-6_13 |
| [27] | Libert, B., Ling, S., Mouhartem, F., Nguyen, K., Wang, H.: Zero-knowledge arguments for matrix-vector relations and lattice-based group encryption. In: Cheon, J.H., Takagi, T. (eds.) ASIACRYPT 2016. LNCS, vol. 10032, pp. 101-131. Springer, Heidelberg (2016). doi:10.1007/978-3-662-53890-6_4 · Zbl 1407.94135 · doi:10.1007/978-3-662-53890-6_4 |
| [28] | Libert, B., Ling, S., Nguyen, K., Wang, H.: Zero-knowledge arguments for lattice-based accumulators: logarithmic-size ring signatures and group signatures without trapdoors. In: Fischlin, M., Coron, J.-S. (eds.) EUROCRYPT 2016. LNCS, vol. 9666, pp. 1-31. Springer, Heidelberg (2016). doi:10.1007/978-3-662-49896-5_1 · Zbl 1369.94552 · doi:10.1007/978-3-662-49896-5_1 |
| [29] | Libert, B., Mouhartem, F., Nguyen, K.: A lattice-based group signature scheme with message-dependent opening. In: Manulis, M., Sadeghi, A.-R., Schneider, S. (eds.) ACNS 2016. LNCS, vol. 9696, pp. 137-155. Springer, Cham (2016). doi:10.1007/978-3-319-39555-5_8 · Zbl 1346.94145 |
| [30] | 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). doi:10.1007/978-3-642-32009-5_34 · Zbl 1296.94156 · doi:10.1007/978-3-642-32009-5_34 |
| [31] | 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). doi:10.1007/978-3-642-29011-4_36 · Zbl 1296.94155 · doi:10.1007/978-3-642-29011-4_36 |
| [32] | Libert, B., Peters, T., Yung, M.: Short group signatures via structure-preserving signatures: standard model security from simple assumptions. In: Gennaro, R., Robshaw, M. (eds.) CRYPTO 2015. LNCS, vol. 9216, pp. 296-316. Springer, Heidelberg (2015). doi:10.1007/978-3-662-48000-7_15 · Zbl 1352.94048 · doi:10.1007/978-3-662-48000-7_15 |
| [33] | Ling, S., Nguyen, K., Stehlé, D., Wang, H.: Improved zero-knowledge proofs of knowledge for the ISIS problem, and applications. In: Kurosawa, K., Hanaoka, G. (eds.) PKC 2013. LNCS, vol. 7778, pp. 107-124. Springer, Heidelberg (2013). doi:10.1007/978-3-642-36362-7_8 · Zbl 1314.94087 · doi:10.1007/978-3-642-36362-7_8 |
| [34] | Ling, S., Nguyen, K., Wang, H.: Group signatures from lattices: simpler, tighter, shorter, ring-based. In: Katz, J. (ed.) PKC 2015. LNCS, vol. 9020, pp. 427-449. Springer, Heidelberg (2015). doi:10.1007/978-3-662-46447-2_19 · Zbl 1345.94075 |
| [35] | Micciancio, D., Mol, P.: Pseudorandom knapsacks and the sample complexity of LWE search-to-decision reductions. In: Rogaway, P. (ed.) CRYPTO 2011. LNCS, vol. 6841, pp. 465-484. Springer, Heidelberg (2011). doi:10.1007/978-3-642-22792-9_26 · Zbl 1287.94085 · doi:10.1007/978-3-642-22792-9_26 |
| [36] | Micciancio, D., Peikert, C.: Hardness of SIS and LWE with small parameters. In: Canetti, R., Garay, J.A. (eds.) CRYPTO 2013. LNCS, vol. 8042, pp. 21-39. Springer, Heidelberg (2013). doi:10.1007/978-3-642-40041-4_2 · Zbl 1310.94161 · doi:10.1007/978-3-642-40041-4_2 |
| [37] | Nakanishi, T., Fujii, H., Hira, Y., Funabiki, N.: Revocable group signature schemes with constant costs for signing and verifying. In: Jarecki, S., Tsudik, G. (eds.) PKC 2009. LNCS, vol. 5443, pp. 463-480. Springer, Heidelberg (2009). doi:10.1007/978-3-642-00468-1_26 · Zbl 1227.94081 · doi:10.1007/978-3-642-00468-1_26 |
| [38] | Naor, M., Yung, M.: Public-key cryptosystems provably secure against chosen ciphertext attacks. In: STOC 1990, pp. 427-437. ACM (1990) |
| [39] | Nguyen, L.: Accumulators from bilinear pairings and applications. In: Menezes, A. (ed.) CT-RSA 2005. LNCS, vol. 3376, pp. 275-292. Springer, Heidelberg (2005). doi:10.1007/978-3-540-30574-3_19 · Zbl 1079.94568 · doi:10.1007/978-3-540-30574-3_19 |
| [40] | 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). doi:10.1007/978-3-540-30539-2_26 · Zbl 1094.94530 · doi:10.1007/978-3-540-30539-2_26 |
| [41] | Nguyen, P.Q., Zhang, J., Zhang, Z.: Simpler efficient group signatures from lattices. In: Katz, J. (ed.) PKC 2015. LNCS, vol. 9020, pp. 401-426. Springer, Heidelberg (2015). doi:10.1007/978-3-662-46447-2_18 · Zbl 1345.94082 |
| [42] | Regev, O.: On lattices, learning with errors, random linear codes, and cryptography. In: STOC 2005, pp. 84-93. ACM (2005) · Zbl 1192.94106 |
| [43] | Sakai, Y., Emura, K., Hanaoka, G., Kawai, Y., Matsuda, T., Omote, K.: Group signatures with message-dependent opening. In: Abdalla, M., Lange, T. (eds.) Pairing 2012. LNCS, vol. 7708, pp. 270-294. Springer, Heidelberg (2013). doi:10.1007/978-3-642-36334-4_18 · Zbl 1305.94092 · doi:10.1007/978-3-642-36334-4_18 |
| [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). doi:10.1007/978-3-642-30057-8_42 · Zbl 1291.94196 · doi:10.1007/978-3-642-30057-8_42 |
| [45] | Stern, J.: A new paradigm for public key identification. IEEE Trans. Inf. Theory 42(6), 1757-1768 (1996) · Zbl 0944.94008 · doi:10.1109/18.556672 |
| [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). doi:10.1007/978-3-540-40061-5_16 · 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. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.
