zbMATH — the first resource for mathematics

Lattice-based group signatures with verifier-local revocation: achieving shorter key-sizes and explicit traceability with ease. (English) Zbl 1444.94124
Mu, Yi (ed.) et al., Cryptology and network security. 18th international conference, CANS 2019, Fuzhou, China, October 25–27, 2019. Proceedings. Cham: Springer. Lect. Notes Comput. Sci. 11829, 120-140 (2019).
Summary: For lattice-based group signatures (GS) with verifier-local revocation (VLR), it only requires the verifiers to possess up-to-date group information (i.e., a revocation list, RL, consists of a series of revocation tokens for revoked members), but not the signers. The first such scheme was introduced by A. Langlois et al. in 2014 [PKC 2014, Lect. Notes Comput. Sci. 8383, 345–361 (2014; Zbl 1335.94063)], and subsequently, a full and corrected version (to fix a flaw in the original revocation mechanism) was proposed by S. Ling et al. in 2018 [Theor. Comput. Sci. 730, 1–20 (2018; Zbl 1401.94163)]. However, both constructions are within the structure of a Bonsai Tree, and thus features bit-sizes of the group public-key and the member secret-key proportional to \(\log N\), where N is the maximum number of group members. On the other hand, the tracing algorithm for both schemes runs in a linear time in N (i.e., one by one, until the real signer is traced). Therefore for a large group, the tracing algorithm of conventional GS-VLR is not convenient and both lattice-based constructions are not that efficient.
In this work, we propose a much more efficient lattice-based GS-VLR, which is efficient by saving the \(\mathcal{O}(\log N)\) factor for both bit-sizes of the group public-key and the member secret-key. Moreover, we achieve this result in a relatively simple manner. Starting with K. Nguyen et al.’s efficient and compact identity-encoding technique in 2015 [PKC 2015, Lect. Notes Comput. Sci. 9020, 427–449 (2015; Zbl 1345.94075)] – which only needs a constant number of matrices to encode the member’s identity, we develop an improved identity-encoding function, and introduce an efficient Stern-type statistical zero-knowledge argument of knowledge (ZKAoK) protocol corresponding to our improved identity-encoding function, which may be of independent cryptographic interest.
Furthermore, we demonstrate how to equip the obtained lattice-based GS-VLR with explicit traceability (ET) in some simple way. This attractive functionality, only satisfied in the non-VLR constructions, can enable the tracing authority in lattice-based GS-VLR to determine the signer’s real identity in a constant time, independent of N. In the whole process, we show that the proposed scheme is proven secure in the random oracle model (ROM) based on the hardness of the Short Integer Solution (SIS) problem, and the Learning With Errors (LWE) problem.
For the entire collection see [Zbl 1428.68039].
94A62 Authentication, digital signatures and secret sharing
Full Text: DOI
[1] Agrawal, S., Boneh, D., Boyen, X.: Efficient lattice (H)IBE in the standard model. In: Gilbert, H. (ed.) EUROCRYPT 2010. LNCS, vol. 6110, pp. 553-572. Springer, Heidelberg (2010). https://doi.org/10.1007/978-3-642-13190-5_28 · Zbl 1227.94022
[2] Ajtai, M.: Generating hard instances of lattice problems (extended abstract). In: STOC, pp. 99-108. ACM (1996). https://doi.org/10.1145/237814.237838 · Zbl 0921.11071
[3] Alwen, J., Peikert, C.: Generating shorter bases for hard random lattices. Theory Comput. Syst. 48(3), 535-553 (2011). https://doi.org/10.1007/s00224-010-9278-3 · Zbl 1217.94092
[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). https://doi.org/10.1007/3-540-39200-9_38 · Zbl 1038.94552
[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). https://doi.org/10.1007/978-3-540-30574-3_11 · Zbl 1079.94013
[6] Boneh, D., Shacham, H.: Group signatures with verifier-local revocation. In: CCS, pp. 168-177. ACM (2004). https://doi.org/10.1145/1030083.1030106
[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). https://doi.org/10.1007/978-3-319-39555-5_7 · Zbl 1346.94141
[8] Camenisch, J., Neven, G., Rückert, M.: Fully anonymous attribute tokens from lattices. In: Visconti, I., De Prisco, R. (eds.) SCN 2012. LNCS, vol. 7485, pp. 57-75. Springer, Heidelberg (2012). https://doi.org/10.1007/978-3-642-32928-9_4 · Zbl 1310.94177
[9] 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). https://doi.org/10.1007/978-3-642-13190-5_27 · Zbl 1280.94043
[10] 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 · Zbl 0791.68044
[11] Gao, W., Hu, Y., Zhang, Y., Wang, B.: Lattice-Based Group Signature with Verifier-Local Revocation. J. Shanghai JiaoTong Univ. (Sci.) 22(3), 313-321 (2017). https://doi.org/10.1007/s12204-017-1837-1
[12] Gentry, C., Peikert, C., Vaikuntanathan, V.: Trapdoor for hard lattices and new cryptographic constructions. In: STOC, pp. 197-206. ACM (2008) https://doi.org/10.1145/1374376.1374407 · Zbl 1231.68124
[13] 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). https://doi.org/10.1007/978-3-642-17373-8_23 · Zbl 1253.94071
[14] Katsumata, S., Yamada, S.: Group signatures without NIZK: from lattices in the standard model. In: Ishai, Y., Rijmen, V. (eds.) EUROCRYPT 2019. LNCS, vol. 11478, pp. 312-344. Springer, Cham (2019). https://doi.org/10.1007/978-3-030-17659-4_11 · Zbl 07162732
[15] 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). https://doi.org/10.1007/978-3-540-89255-7_23 · Zbl 1206.94076
[16] Kiayias, A., Yung, M.: Secure scalable group signature with dynamic joins and separable authorities. Int. J. Secur. Netw. 1(1/2), 24-45 (2006). https://doi.org/10.1504/ijsn.2006.010821
[17] 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). https://doi.org/10.1007/978-3-642-42045-0_3 · Zbl 1314.94104
[18] 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). https://doi.org/10.1007/978-3-642-54631-0_20 · Zbl 1335.94063
[19] 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). https://doi.org/10.1007/978-3-662-53890-6_13 · Zbl 1407.94136
[20] 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). https://doi.org/10.1007/978-3-662-49896-5_1 · Zbl 1369.94552
[21] 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). https://doi.org/10.1007/978-3-319-39555-5_8 · Zbl 1346.94145
[22] Ling, S., Nguyen, K., Roux-Langlois, A., Wang, H.: A lattice-based group signature scheme with verifier-local revocation. Theor. Comput. Sci. 730, 1-20 (2018) · Zbl 1401.94163
[23] 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). https://doi.org/10.1007/978-3-642-36362-7_8 · Zbl 1314.94087
[24] 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). https://doi.org/10.1007/978-3-662-46447-2_19 · Zbl 1345.94075
[25] Ling, S., Nguyen, K., Wang, H., Xu, Y.: Constant-size group signatures from lattices. In: Abdalla, M., Dahab, R. (eds.) PKC 2018. LNCS, vol. 10770, pp. 58-88. Springer, Cham (2018). https://doi.org/10.1007/978-3-319-76581-5_3 · Zbl 1406.94072
[26] Ling, S., Nguyen, K., Wang, H., Xu, Y.: Forward-secure group signatures from lattices. In: Ding, J., Steinwandt, R. (eds.) PQCrypto 2019. LNCS, vol. 11505, pp. 44-64. Springer, Cham (2019). https://doi.org/10.1007/978-3-030-25510-7_3 · Zbl 07173856
[27] 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 · Zbl 07093354
[28] Micciancio, D., Regev, O.: Worst-case to average-case reductions based on Gaussian measures. SIAM J. Comput. 37(1), 267-302 (2007). https://doi.org/10.1137/s0097539705447360 · Zbl 1142.68037
[29] 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). https://doi.org/10.1007/978-3-642-40041-4_2 · Zbl 1310.94161
[30] Micciancio, D., Peikert, C.: Trapdoors for lattices: simpler, tighter, faster, smaller. In: Pointcheval, D., Johansson, T. (eds.) EUROCRYPT 2012. LNCS, vol. 7237, pp. 700-718. Springer, Heidelberg (2012). https://doi.org/10.1007/978-3-642-29011-4_41 · Zbl 1297.94090
[31] 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). https://doi.org/10.1007/978-3-662-46447-2_18 · Zbl 1345.94082
[32] Perera, M.N.S., Koshiba, T.: Achieving strong security and verifier-local revocation for dynamic group signatures from lattice assumptions. In: Katsikas, S.K., Alcaraz, C. (eds.) STM 2018. LNCS, vol. 11091, pp. 3-19. Springer, Cham (2018). https://doi.org/10.1007/978-3-030-01141-3_1
[33] Perera, M.N.S., Koshiba, T.: Zero-knowledge proof for lattice-based group signature schemes with verifier-local revocation. In: Barolli, L., Kryvinska, N., Enokido, T., Takizawa, M. (eds.) NBiS 2018. LNDECT, vol. 22, pp. 772-782. Springer, Cham (2019). https://doi.org/10.1007/978-3-319-98530-5_68
[34] Regev, O.: On lattices, learning with errors, random linear codes, and cryptography. In: STOC, pp. 84-93. ACM (2005). https://doi.org/10.1145/1060590.1060603 · Zbl 1192.94106
[35] Zhang, Y.
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.