Among several post quantum primitives proposed in the past few decades, lattice-based cryptography
is considered as the most promising one, due to its underlying rich combinatorial structure, and the worst-case
to average-case reductions. The first lattice-based group signature scheme with verifier-local revocation (VLR) is
treated as the first quantum-resistant scheme supported member revocation, and was put forward by Langlois et
al. This VLR group signature (VLR-GS) has group public key size of O(nmlogN log q), and a signature size of
O(tm logN log q log β). Nguyen et al. constructed a simple efficient group signature from lattice, with significant
advantages in bit-size of both the group public key and the signature. Based on their work, we present a VLR-GS
scheme with group public key size of O(nm log q) and signature size of O(tm log q). Our group signature has
notable advantages: support of membership revocation, and short in both the public key size and the signature
size.
GAO Wen* (高雯), HU Yupu (胡予濮), ZHANG Yanhua (张彦华), WANG Baocang (王保仓)
. Lattice-Based Group Signature with Verifier-Local Revocation[J]. Journal of Shanghai Jiaotong University(Science), 2017
, 22(3)
: 313
-321
.
DOI: 10.1007/s12204-017-1837-1
[1] CHAUM D, HEYST E. Group signatures[C]//Advances in Cryptology (EUROCRYPT ’91).Berlin Heidelberg: Springer, 1991: 257-265.
[2] ATENIESE G, CAMENISCH J, JOYE M, et al.A practical and provably secure coalition-resistantgroup signature scheme [C]//Advances in Cryptology(CRYPTO 2000). Berlin Heidelberg: Springer, 2000:255-270.
[3] BONEH D, BOYEN X, SHACHAM H. Short groupsignatures [C]//Advances in Cryptology: CRYPTO2004. Berlin Heidelberg: Springer, 2004: 41-55.
[4] BONEH D, SHACHAM H. Group signatures withverifier-local revocation [C]//Proceedings of 11th ACMConference on Computer and Communications Security.New York, USA: ACM, 2004: 168-177.
[5] LIBERT B, PETERS T, YUNG M. Group signatureswith almost-for-free revocation [C]//Advancesin Cryptology: CRYPTO 2012. Berlin Heidelberg:Springer, 2012: 571-589.
[6] SHOR PW. Polynomial-time algorithms for prime factorizationand discrete logarithms on a quantum computer[J]. SIAM Journal on Computing, 1997, 26(5):1484-1509.
[7] PHONG Q N, ZHANG J, ZHANG Z F. Simpler efficientgroup signatures from lattices [C]// Public-Key Cryptography (PKC) 2015. Berlin Heidelberg:Springer, 2015: 401-426.
[8] LANGLOIS A, LING S, NGUYEN K, et al. Latticebasedgroup signature scheme with verifier-local revocation[C]//Proceedings of 17th International Conferenceon Practice and Theory in Public-Key Cryptography.Berlin Heidelberg: Springer, 2014: 345-361.
[9] BONEH D, SHACHAM H. Group signatures withverifier-local revocation [C]//Proceedings of 11th ACMConference on Computer and Communications Security.New York, USA: ACM, 2004: 168-177.
[10] NAKANISHI T, FUNABIKI N. Verifier-local revocationgroup signature schemes with backward unlinkabilityfrom bilinear maps [C]// Advances in Cryptology:ASIACRYPT 2005. Berlin Heidelberg: Springer,2005: 533-548.
[11] BICHSEL P, CAMENISCH J, NEVEN G, et al. Getshorty via group signatures without encryption [J].Security and Cryptography for Networks, 2010, 6280:381-398.
[12] GORDON S D, KATZ J, VAIKUNTANATHAN V.A group signature scheme from lattice assumptions[C]//Advances in Cryptology: ASIACRYPT 2010.Berlin Heidelberg: Springer, 2010: 395-412.
[13] GENTRY C, PEIKERT C, VAIKUNTANATHAN V.Trapdoors for hard lattices and new cryptographic constructions[C]//Proceedings of the 40th Annual ACMSymposium on Theory of Computing. New York, USA:ACM, 2008: 197-206.
[14] REGEV O. On lattices, learning with errors, randomlinear codes, and cryptography [C]//Proceedings of the37th ACM Symposium on Theory of Computing. NewYork, USA: ACM, 2005: 84-93.
[15] MICCIANCIO D, VADHAN S. Statistical zeroknowledgeproofs with efficient provers: latticeproblems and more [C]//Advances in Cryptology:CRYPTO 2003. Berlin Heidelberg: Springer, 2003:282-298.
[16] CAMENISCH J, NEVEN G, R¨UCKERT M. Fullyanonymous attribute tokens from lattices [J]. LNCS:Security and Cryptography for Networks, 2012, 7485:57-75.
[17] LAGUILLAUMIE F, LANGLOIS A, LIBERT B, et al.Lattice-based group signatures with logarithmic signaturesize [C]//Advances in Cryptology: ASIACRYPT2013. Berlin Heidelberg: Springer, 2013: 41-61.
[18] LING S, NGUYEN K, STEHL′E D, et al. Improvedzero-knowledge proofs of knowledge for the ISIS problem,and applications [C]//Proceedings of 16th InternationalConference on Practice and Theory in Public-Key Cryptography. Berlin Heidelberg: Springer, 2013:107-124.
[19] AJTAI M. Generating hard instances of lattice problems(extended abstract) [C]//Proceedings of the 28thannual ACM Symposium on Theory of Computing.New York, USA: ACM, 1996: 99-108.
[20] ALWEN J, PEIKERT C. Generating shorter bases forhard random lattices [C]//Proceedings of 26th InternationalSymposium on Theoretical Aspects of ComputerScience. Schloss Dagstuhl, Germany: IBFI, 2009: 75-86.
[21] MICCIANCIO D, PEIKERT C. Trapdoors for lattices:Simpler, tighter, faster, smaller [C]//Advancesin Cryptology: EUROCRYPT 2012. Berlin Heidelberg:Springer, 2012: 700-718.
[22] BELLARE M, NEVEN G. Multi-signatures in theplain public-key model and a general forking lemma[C]//Proceedings of the 13th ACM Conference onComputer and Communications Security. New York,USA: ACM, 2006: 390-399.
[23] MICCIANCIO D, REGEV O. Worst-case to averagecasereductions based on gaussian measures [J]. SIAMJournal on Computing, 2007, 37(1): 267-302.
[24] LYUBASHEVSKY V. Lattice signatures without trapdoors[C]//Advances in Cryptology: EUROCRYPT2012. Berlin Heidelberg: Springer, 2012: 738-755.
