×

zbMATH — the first resource for mathematics

A lattice-based group signature scheme with verifier-local revocation. (English) Zbl 1401.94163
Summary: Support of membership revocation is a desirable functionality for any group signature scheme. Among the known revocation approaches, verifier-local revocation (VLR) seems to be the most flexible one, because it only requires the verifiers to possess some up-to-date revocation information, but not the signers. All of the contemporary VLR group signatures operate in the bilinear map setting, and all of them will be insecure once quantum computers become a reality. In this work, we introduce the first lattice-based VLR group signature, and thus, the first such scheme that is believed to be quantum-resistant. In comparison with existing lattice-based group signatures, our scheme has several noticeable advantages: support of membership revocation, logarithmic-size signatures, and milder hardness assumptions. Moreover, our construction works without relying on public-key encryption schemes, which is an intriguing feature for group signatures.
The preliminary version was published in [PKC 2014, Lect. Notes Comput. Sci. 8383, 345–361 (2014; Zbl 1335.94063)].

MSC:
94A60 Cryptography
PDF BibTeX XML Cite
Full Text: DOI
References:
[1] Ajtai, M., Generating hard instances of lattice problems (extended abstract), (STOC, (1996), ACM), 99-108 · Zbl 0921.11071
[2] Ajtai, M., Generating hard instances of the short basis problem, (ICALP, Lecture Notes in Comput. Sci., vol. 1644, (1999), Springer), 1-9
[3] Alwen, J.; Peikert, C., Generating shorter bases for hard random lattices, Theory Comput. Syst., 48, 3, 535-553, (2011) · Zbl 1217.94092
[4] Ateniese, G.; Camenisch, J.; Joye, M.; Tsudik, G., A practical and provably secure coalition-resistant group signature scheme, (CRYPTO, Lecture Notes in Comput. Sci., vol. 1880, (2000), Springer), 255-270 · Zbl 0995.94544
[5] Bellare, M.; Micciancio, D.; Warinschi, B., Foundations of group signatures: formal definitions, simplified requirements, and a construction based on general assumptions, (EUROCRYPT, Lecture Notes in Comput. Sci., vol. 2656, (2003), Springer), 614-629 · Zbl 1038.94552
[6] Bellare, M.; Shi, H.; Zhang, C., Foundations of group signatures: the case of dynamic groups, (CT-RSA, Lecture Notes in Comput. Sci., vol. 3376, (2005), Springer), 136-153 · Zbl 1079.94013
[7] Bichsel, P.; Camenisch, J.; Neven, G.; Smart, N. P.; Warinschi, B., Get shorty via group signatures without encryption, (SCN, Lecture Notes in Comput. Sci., vol. 6280, (2010), Springer), 381-398 · Zbl 1291.94179
[8] Boneh, D.; Boyen, X.; Shacham, H., Short group signatures, (CRYPTO, Lecture Notes in Comput. Sci., vol. 3152, (2004), Springer), 41-55 · Zbl 1104.94044
[9] Boneh, D.; Shacham, H., Group signatures with verifier-local revocation, (ACM-CCS, (2004), ACM), 168-177
[10] Brickell, E., An efficient protocol for anonymously providing assurance of the container of the private key, Trusted Comp. Group, (April 2003), submitted for publication
[11] Camenisch, J.; Groth, J., Group signatures: better efficiency and new theoretical aspects, (SCN, Lecture Notes in Comput. Sci., vol. 3352, (2004), Springer), 120-133 · Zbl 1116.94310
[12] Camenisch, J.; Lysyanskaya, A., Dynamic accumulators and application to efficient revocation of anonymous credentials, (CRYPTO, Lecture Notes in Comput. Sci., vol. 2442, (2002), Springer), 61-76 · Zbl 1026.94545
[13] Camenisch, J.; Neven, G.; Rückert, M., Fully anonymous attribute tokens from lattices, (SCN, Lecture Notes in Comput. Sci., vol. 7485, (2012), Springer), 57-75 · Zbl 1310.94177
[14] Cash, D.; Hofheinz, D.; Kiltz, E.; Peikert, C., Bonsai trees, or how to delegate a lattice basis, (EUROCRYPT, Lecture Notes in Comput. Sci., vol. 6110, (2010), Springer), 523-552 · Zbl 1280.94043
[15] Chaum, D.; van Heyst, E., Group signatures, (EUROCRYPT, Lecture Notes in Comput. Sci., vol. 547, (1991), Springer), 257-265 · Zbl 0791.68044
[16] Chen, L.; Pedersen, T. P., New group signature schemes (extended abstract), (EUROCRYPT, Lecture Notes in Comput. Sci., vol. 950, (1994), Springer), 171-181 · Zbl 0879.94027
[17] Cheng, S.; Nguyen, K.; Wang, H., Policy-based signature scheme from lattices, Des. Codes Cryptogr., 81, 1, 43-74, (2016) · Zbl 1379.94052
[18] Fiat, A.; Shamir, A., How to prove yourself: practical solutions to identification and signature problems, (CRYPTO, Lecture Notes in Comput. Sci., vol. 263, (1986), Springer), 186-194
[19] Gentry, C.; Peikert, C.; Vaikuntanathan, V., Trapdoors for hard lattices and new cryptographic constructions, (STOC, (2008), ACM), 197-206 · Zbl 1231.68124
[20] Gordon, S. D.; Katz, J.; Vaikuntanathan, V., A group signature scheme from lattice assumptions, (ASIACRYPT, Lecture Notes in Comput. Sci., vol. 6477, (2010), Springer), 395-412 · Zbl 1253.94071
[21] Groth, J., Fully anonymous group signatures without random oracles, (ASIACRYPT, Lecture Notes in Comput. Sci., vol. 4833, (2007), Springer), 164-180 · Zbl 1153.94386
[22] Kawachi, A.; Tanaka, K.; Xagawa, K., Concurrently secure identification schemes based on the worst-case hardness of lattice problems, (ASIACRYPT, Lecture Notes in Comput. Sci., vol. 5350, (2008), Springer), 372-389 · Zbl 1206.94076
[23] Laguillaumie, F.; Langlois, A.; Libert, B.; Stehlé, D., Lattice-based group signatures with logarithmic signature size, (ASIACRYPT, Lecture Notes in Comput. Sci., vol. 8270, (2013), Springer), 41-61 · Zbl 1314.94104
[24] Langlois, A.; Ling, S.; Nguyen, K.; Wang, H., Lattice-based group signature scheme with verifier-local revocation, (PKC, Lecture Notes in Comput. Sci., vol. 8383, (2014), Springer), 345-361 · Zbl 1335.94063
[25] Libert, B.; Ling, S.; Mouhartem, F.; Nguyen, K.; Wang, H., Signature schemes with efficient protocols and dynamic group signatures from lattice assumptions, (ASIACRYPT, Lecture Notes in Comput. Sci., vol. 10032, (2016), Springer), 373-403 · Zbl 1407.94136
[26] Libert, B.; Ling, S.; Nguyen, K.; Wang, H., Zero-knowledge arguments for lattice-based accumulators: logarithmic-size ring signatures and group signatures without trapdoors, (EUROCRYPT, Lecture Notes in Comput. Sci., vol. 9666, (2016), Springer), 1-31 · Zbl 1369.94552
[27] Libert, B.; Mouhartem, F.; Nguyen, K., A lattice-based group signature scheme with message-dependent opening, (ACNS, Lecture Notes in Comput. Sci., vol. 9696, (2016), Springer), 137-155 · Zbl 1346.94145
[28] Libert, B.; Peters, T.; Yung, M., Group signatures with almost-for-free revocation, (CRYPTO, Lecture Notes in Comput. Sci., vol. 7417, (2012), Springer), 571-589 · Zbl 1296.94156
[29] Libert, B.; Vergnaud, D., Group signatures with verifier-local revocation and backward unlinkability in the standard model, (CANS, Lecture Notes in Comput. Sci., vol. 5888, (2009), Springer), 498-517 · Zbl 1287.94081
[30] Ling, S.; Nguyen, K.; Stehlé, D.; Wang, H., Improved zero-knowledge proofs of knowledge for the ISIS problem, and applications, (PKC, Lecture Notes in Comput. Sci., vol. 7778, (2013), Springer), 107-124 · Zbl 1314.94087
[31] Ling, S.; Nguyen, K.; Wang, H., Group signatures from lattices: simpler, tighter, shorter, ring-based, (PKC, Lecture Notes in Comput. Sci., vol. 9020, (2015), Springer), 427-449 · Zbl 1345.94075
[32] Ling, S.; Nguyen, K.; Wang, H.; Xu, Y., Lattice-based group signatures: achieving full dynamicity with ease, (ACNS, Lecture Notes in Comput. Sci., vol. 10355, (2017), Springer), 293-312
[33] Lyubashevsky, V., Lattice-based identification schemes secure under active attacks, (PKC, Lecture Notes in Comput. Sci., vol. 4939, (2008), Springer), 162-179 · Zbl 1162.94388
[34] Micciancio, D.; Mol, P., Pseudorandom knapsacks and the sample complexity of LWE search-to-decision reductions, (CRYPTO, Lecture Notes in Comput. Sci., vol. 6841, (2011), Springer), 465-484 · Zbl 1287.94085
[35] Micciancio, D.; Peikert, C., Trapdoors for lattices: simpler, tighter, faster, smaller, (EUROCRYPT, Lecture Notes in Comput. Sci., vol. 7237, (2012), Springer), 700-718 · Zbl 1297.94090
[36] Micciancio, D.; Regev, O., Lattice-based cryptography, (Post-Quantum Cryptography, (2009), Springer), 147-191 · Zbl 1161.81324
[37] Micciancio, D.; Vadhan, S. P., Statistical zero-knowledge proofs with efficient provers: lattice problems and more, (CRYPTO, Lecture Notes in Comput. Sci., vol. 2729, (2003), Springer), 282-298 · Zbl 1122.68448
[38] Nakanishi, T.; Funabiki, N., Verifier-local revocation group signature schemes with backward unlinkability from bilinear maps, (ASIACRYPT, Lecture Notes in Comput. Sci., vol. 3788, (2005), Springer), 533-548 · Zbl 1154.94469
[39] Nakanishi, T.; Funabiki, N., A short verifier-local revocation group signature scheme with backward unlinkability, (IWSEC, Lecture Notes in Comput. Sci., vol. 4266, (2006), Springer), 17-32
[40] Peikert, C., Public-key cryptosystems from the worst-case shortest vector problem: extended abstract, (STOC, (2009), ACM), 333-342 · Zbl 1304.94079
[41] Peikert, C., An efficient and parallel Gaussian sampler for lattices, (CRYPTO, Lecture Notes in Comput. Sci., vol. 6223, (2010), Springer), 80-97 · Zbl 1280.94091
[42] Peikert, C.; Rosen, A., Efficient collision-resistant hashing from worst-case assumptions on cyclic lattices, (TCC, Lecture Notes in Comput. Sci., vol. 3876, (2006), Springer), 145-166 · Zbl 1112.94020
[43] Pointcheval, D.; Vaudenay, S., On provable security for digital signature algorithms, (1997), Technical Report LIENS-96-17 of the Laboratoire d’Informatique de Ecole Normale Superieure
[44] Regev, O., On lattices, learning with errors, random linear codes, and cryptography, (STOC, (2005), ACM), 84-93 · Zbl 1192.94106
[45] Rückert, M., Adaptively secure identity-based identification from lattices without random oracles, (SCN, Lecture Notes in Comput. Sci., vol. 6280, (2010), Springer), 345-362 · Zbl 1291.94145
[46] Shor, P. W., Polynomial-time algorithms for prime factorization and discrete logarithms on a quantum computer, SIAM J. Comput., 26, 5, 1484-1509, (1997) · Zbl 1005.11065
[47] Stern, J., A new paradigm for public key identification, IEEE Trans. Inform. Theory, 42, 6, 1757-1768, (1996) · Zbl 0944.94008
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.