Lattice-Based Group Signature with Verifier-Local Revocation

doi:10.1007/s12204-017-1837-1

Abstract

Abstract: 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.

Key words: lattice-based| member revocation| digital signature

摘要： 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.

关键词: lattice-based| member revocation| digital signature

CLC Number:

TP 309

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.

References 24

[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.