zbMATH — the first resource for mathematics

A lattice-based group signature scheme with message-dependent opening. (English) Zbl 1346.94145
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, 137-155 (2016).
Summary: Group signatures are an important anonymity primitive allowing users to sign messages while hiding in a crowd. At the same time, signers remain accountable since an authority is capable of de-anonymizing signatures via a process called opening. In many situations, this authority is granted too much power as it can identify the author of any signature. Sakai et al. proposed a flavor of the primitive, called Group Signature with Message-Dependent Opening (GS-MDO), where opening operations are only possible when a separate authority (called “admitter”) has revealed a trapdoor for the corresponding message. So far, all existing GS-MDO constructions rely on bilinear maps, partially because the message-dependent opening functionality inherently implies identity-based encryption. This paper proposes the first GS-MDO candidate based on lattice assumptions. Our construction combines the group signature of Ling, Nguyen and Wang (PKC’15) with two layers of identity-based encryption. These components are tied together using suitable zero-knowledge argument systems.
For the entire collection see [Zbl 1337.94004].

94A62 Authentication, digital signatures and secret sharing
Full Text: DOI
[1] Abdalla, M., Warinschi, B.: On the minimal assumptions of group signature schemes. In: López, J., Qing, S., Okamoto, E. (eds.) ICICS 2004. LNCS, vol. 3269, pp. 1–13. Springer, Heidelberg (2004) · Zbl 1109.68438 · doi:10.1007/978-3-540-30191-2_1
[2] Alwen, J., Peikert, C.: Generating shorter bases for hard random lattices. In: STACS 2009 (2009) · Zbl 1236.94049
[3] 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) · Zbl 0995.94544 · doi:10.1007/3-540-44598-6_16
[4] Banaszczyk, W.: New bounds in some transference theorems in the geometry of number. Mathematische Annalen (1993) · Zbl 0786.11035 · doi:10.1007/BF01445125
[5] 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) · Zbl 1038.94552 · doi:10.1007/3-540-39200-9_38
[6] Benhamouda, F., Camenisch, J., Krenn, S., Lyubashevsky, V., Neven, G.: Better zero-knowledge proofs for lattice encryption and their application to group signatures. In: Sarkar, P., Iwata, T. (eds.) ASIACRYPT 2014. LNCS, vol. 8873, pp. 551–572. Springer, Heidelberg (2014) · Zbl 1306.94026 · doi:10.1007/978-3-662-45611-8_29
[7] 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
[8] Boneh, D., Franklin, M.: Identity-based encryption from the weil pairing. In: Kilian, J. (ed.) CRYPTO 2001. LNCS, vol. 2139, pp. 213–229. Springer, Heidelberg (2001) · Zbl 1002.94023 · doi:10.1007/3-540-44647-8_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) · Zbl 1281.94074 · doi:10.1007/978-3-642-13013-7_29
[10] 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
[11] 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
[12] Brakerski, Z., Langlois, A., Peikert, C., Regev, O., Stehlé, D.: On the classical hardness of learning with errors. In: STOC 2013. ACM (2013) · Zbl 1293.68159 · doi:10.1145/2488608.2488680
[13] Canetti, R., Halevi, S., Katz, J.: Chosen-ciphertext security from identity-based encryption. In: Cachin, C., Camenisch, J.L. (eds.) EUROCRYPT 2004. LNCS, vol. 3027, pp. 207–222. Springer, Heidelberg (2004) · Zbl 1122.94358 · doi:10.1007/978-3-540-24676-3_13
[14] 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) · Zbl 1280.94043 · doi:10.1007/978-3-642-13190-5_27
[15] 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
[16] Desmedt, Y., Frankel, Y.: Threshold cryptosystems. In: Brassard, G. (ed.) CRYPTO 1989. LNCS, vol. 435, pp. 307–315. Springer, Heidelberg (1989)
[17] Ezerman, M.F., Lee, H.T., Ling, S., Nguyen, K., Wang, H.: A provably secure group signature scheme from code-based assumptions. In: Iwata, T., et al. (eds.) ASIACRYPT 2015. LNCS, vol. 9452, pp. 260–285. Springer, Heidelberg (2015) · Zbl 1396.94075 · doi:10.1007/978-3-662-48797-6_12
[18] Gentry, C.: Fully homomorphic encryption using ideal lattices. In: STOC (2009) · Zbl 1304.94059 · doi:10.1145/1536414.1536440
[19] Gentry, C., Peikert, C., Vaikuntanathan, V.: Trapdoors for hard lattices and new cryptographic constructions. In: STOC 2008. ACM (2008) · Zbl 1231.68124 · doi:10.1145/1374376.1374407
[20] Goldwasser, S., Micali, S., Rackoff, C.: The knowledge complexity of interactive proof-systems. In: STOC 1985. ACM (1985) · Zbl 0900.94025 · doi:10.1145/22145.22178
[21] 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) · Zbl 1253.94071 · doi:10.1007/978-3-642-17373-8_23
[22] Groth, J.: Evaluating security of voting schemes in the universal composability framework. In: Jakobsson, M., Yung, M., Zhou, J. (eds.) ACNS 2004. LNCS, vol. 3089, pp. 46–60. Springer, Heidelberg (2004) · Zbl 1103.68515 · doi:10.1007/978-3-540-24852-1_4
[23] 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
[24] Groth, J., Sahai, A.: Efficient non-interactive proof systems for bilinear groups. In: Smart, N.P. (ed.) EUROCRYPT 2008. LNCS, vol. 4965, pp. 415–432. Springer, Heidelberg (2008) · Zbl 1149.94320 · doi:10.1007/978-3-540-78967-3_24
[25] Jain, A., Krenn, S., Pietrzak, K., Tentes, A.: Commitments and efficient zero-knowledge proofs from learning parity with noise. In: Wang, X., Sako, K. (eds.) ASIACRYPT 2012. LNCS, vol. 7658, pp. 663–680. Springer, Heidelberg (2012) · Zbl 1292.94082 · doi:10.1007/978-3-642-34961-4_40
[26] 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) · Zbl 1206.94076 · doi:10.1007/978-3-540-89255-7_23
[27] 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
[28] Laguillaumie, F., Langlois, A., Libert, B., Stehlé, D.: Lattice-based group signatures with logarithmic signature size. In: Sako, K., Sarkar, P. (eds.) ASIACRYPT 2013, Part II. LNCS, vol. 8270, pp. 41–61. Springer, Heidelberg (2013) · Zbl 1314.94104 · doi:10.1007/978-3-642-42045-0_3
[29] Libert, B., Joye, M.: Group signatures with message-dependent opening in the standard model. In: Benaloh, J. (ed.) CT-RSA 2014. LNCS, vol. 8366, pp. 286–306. Springer, Heidelberg (2014) · Zbl 1301.94136 · doi:10.1007/978-3-319-04852-9_15
[30] Libert, B., Ling, S., Mouhartem, F., Nguyen, K., Wang, H.: Signature schemes with efficient protocols and dynamic group signatures from lattice assumptions. Cryptology ePrint Archive: Report 2016/101, January 2016 · Zbl 1407.94136
[31] Libert, B., Ling, S., Nguyen, K., Wang, H.: Zero-knowledge arguments for latticebasedaccumulators: Logarithmic-size ring signatures and group signatures without trapdoors. In: Eurocrypt 2016. LNCS. Springer (2016, To appear) · Zbl 1369.94552 · doi:10.1007/978-3-662-49896-5_1
[32] Ling, S., Nguyen, K., Stehlé, D., Wang, H.: Improved zero-knowledge proofs of knowledge for the ISIS Problem, and applications. In: Hanaoka, G., Kurosawa, K. (eds.) PKC 2013. LNCS, vol. 7778, pp. 107–124. Springer, Heidelberg (2013) · Zbl 1314.94087 · doi:10.1007/978-3-642-36362-7_8
[33] 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) · Zbl 1345.94075 · doi:10.1007/978-3-662-46447-2_19
[34] 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) · Zbl 1345.94082 · doi:10.1007/978-3-662-46447-2_18
[35] Ohara, K., Sakai, Y., Emura, K., Hanaoka, G.: A group signature scheme with unbounded message-dependent opening. In: AsiaCCS 2013 (2013) · doi:10.1145/2484313.2484382
[36] Peikert, C.: Public-key cryptosystems from the worst-case shortest vector problem. In: STOC 2009. ACM (2009) · Zbl 1304.94079 · doi:10.1145/1536414.1536461
[37] Peikert, C.: A decade of lattice cryptography. Cryptology ePrint Archive: Report 2015/939, September 2015
[38] Peikert, C., Vaikuntanathan, V.: Noninteractive statistical zero-knowledge proofs for lattice problems. In: Wagner, D. (ed.) CRYPTO 2008. LNCS, vol. 5157, pp. 536–553. Springer, Heidelberg (2008) · Zbl 1183.94045 · doi:10.1007/978-3-540-85174-5_30
[39] Regev, O.: On lattices, learning with errors, random linear codes, and cryptography. In: STOC 2005. ACM (2005) · Zbl 1192.94106 · doi:10.1145/1060590.1060603
[40] 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) · Zbl 1305.94092 · doi:10.1007/978-3-642-36334-4_18
[41] Shamir, A.: Identity-based cryptosystems and signature schemes. In: Blakely, G.R., Chaum, D. (eds.) CRYPTO 1984. LNCS, vol. 196, pp. 47–53. Springer, Heidelberg (1985) · Zbl 1359.94626 · doi:10.1007/3-540-39568-7_5
[42] Stern, J.: A new paradigm for public key identification. IEEE Trans. Inf. Theory 42(6), 2757–2768 (1996) · Zbl 0944.94008 · doi:10.1109/18.556672
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.