Verifier-local revocation group signatures with backward unlinkability from lattices

Yanhua ZHANG; Ximeng LIU; Yupu HU; Yong GAN; Huiwen JIA

doi:10.1631/FITEE.2000507

Your Location：

Home >

Browse articles >

Verifier-local revocation group signatures with backward unlinkability from lattices

Regular Papers | Updated：2022-07-11

- Verifier-local revocation group signatures with backward unlinkability from lattices
  Enhanced Publication
- 格上后向无关联性安全的验证者本地撤销群签名
- Frontiers of Information Technology & Electronic Engineering Vol. 23, Issue 6, Pages: 876-892(2022)
- Affiliations：
  
  1.College of Computer and Communication Engineering, Zhengzhou University of Light Industry, Zhengzhou450001, China
  2.College of Mathematics and Computer Science, Fuzhou University, Fuzhou350108, China
  3.State Key Laboratory of Integrated Service Networks, Xidian University, Xi’an710071, China
  4.College of Information Engineering, Zhengzhou University of Technology, Zhengzhou450044, China
  5.School of Mathematics and Information Science, Guangzhou University, Guangzhou510006, China
- Author bio：
  
  ‡Corresponding author
- Funds：
- DOI：10.1631/FITEE.2000507
  CLC： TP309.2
- Published：0 June 2022，
  
  Received：28 September 2020，
  
  Accepted：2021-03-15
- Accepted：
Scan QR Code
YANHUA ZHANG, XIMENG LIU, YUPU HU, et al. Verifier-local revocation group signatures with backward unlinkability from lattices. [J]. Frontiers of information technology & electronic engineering, 2022, 23(6): 876-892.
DOI：

YANHUA ZHANG, XIMENG LIU, YUPU HU, et al. Verifier-local revocation group signatures with backward unlinkability from lattices. [J]. Frontiers of information technology & electronic engineering, 2022, 23(6): 876-892. DOI： 10.1631/FITEE.2000507.

摘要

群成员可撤销的群签名中，验证者本地撤销机制似乎是一种更为灵活的选择，因为在签名验证过程中，仅需验证者获取最新的撤销信息，而不涉及签名者。与经典的数论型构造相对应，Langlois等人给出了后量子安全的首个格上验证者本地撤销群签名。然而，截至目前，所有格上验证者本地撤销群签名方案暂不满足后向无关联性，该特性可保障群成员被撤销前其对消息签名的匿名性和无关联性。本文给出了首个格上后向无关联性安全的验证者本地撤销群签名方案，从而解决了这一公开问题。新方案为群公钥和群成员签名密钥节省了

(log

)的比特大小，并且没有任何公钥加密。特别地，新方案在随机谕言机模型下是可证明安全的，其困难性可归约至两个经典格上难题假设，即小整数解难题和差错学习难题。

Abstract

For group signature (GS) supporting membership revocation

verifier-local revocation (VLR) mechanism seems to be a more flexible choice

because it requires only that verifiers download up-to-date revocation information for signature verification

and the signers are not involved. As a post-quantum secure cryptographic counterpart of classical number-theoretic cryptographic constructions

the first lattice-based VLR group signature (VLR-GS) was introduced by

Langlois et al. (2014)

. However

none of the contemporary lattice-based VLR-GS schemes provide backward unlinkability (BU)

which is an important property to ensure that previously issued signatures remain anonymous and unlinkable even after the corresponding signer (i.e.

member) is revoked. In this study

we introduce the first lattice-based VLR-GS scheme with BU security (VLR-GS-BU)

and thus resolve a prominent open problem posed by previous works. Our new scheme enjoys an

factor saving for bit-sizes of the group public-key (GPK) and the member's signing secret-key

and it is free of any public-key encryption. In the random oracle model

our scheme is proven secure under two well-known hardness assumptions of the short integer solution (SIS) problem and learning with errors (LWE) problem.

关键词

群签名格密码验证者本地撤销后向无关联性小整数解难题

Keywords

Group signatureLattice-based cryptographyVerifier-local revocationBackward unlikabilityShort integer solution

references

Agrawal S, Boneh D, Boyen X, 2010. Efficient lattice (H)IBE in the standard model. Proc 29th Annual Int Conf on the Theory and Applications of Cryptographic Techniques, p.553-572. doi: 10.1007/978-3-642-13190-5_28http://doi.org/10.1007/978-3-642-13190-5_28

Ajtai M, 1996. Generating hard instances of lattice problems (extended abstract). Proc 28th ACM Symp on Theory of Computing, p.99-108. doi: 10.1145/237814.237838http://doi.org/10.1145/237814.237838

Alwen J, Peikert C, 2011. Generating shorter bases for hard random lattices. Theor Comput Syst, 48(3):535-553. doi: 10.1007/s00224-010-9278-3http://doi.org/10.1007/s00224-010-9278-3

Bellare M, Micciancio D, Warinschi B, 2003. Foundations of group signatures: formal definitions, simplified requirements, and a construction based on general assumptions. Proc 22nd Int Conf on the Theory and Applications of Cryptographic Techniques, p.614-629. doi: 10.1007/3-540-39200-9_38http://doi.org/10.1007/3-540-39200-9_38

Bellare M, Shi HX, Zhang C, 2005. Foundations of group signatures: the case of dynamic groups. Cryptographers’ Track at the RSA Conf, p.136-153. doi: 10.1007/978-3-540-30574-3_11http://doi.org/10.1007/978-3-540-30574-3_11

Boneh D, Shacham H, 2004. Group signatures with verifier-local revocation. Proc 11th ACM Conf on Computer and Communications Security, p.168-177. doi: 10.1145/1030083.1030106http://doi.org/10.1145/1030083.1030106

Bootle J, Cerulli A, Chaidos P, et al., 2016. Foundations of fully dynamic group signatures. Proc 14th Int Conf on the Applied Cryptography and Network Security, p.117-136. doi: 10.1007/978-3-319-39555-5_7http://doi.org/10.1007/978-3-319-39555-5_7

Cash D, Hofheinz D, Kiltz E, et al., 2010. Bonsai trees, or how to delegate a lattice basis. Proc 29th Int Conf on the Theory and Applications of Cryptographic Techniques, p.523-552. doi: 10.1007/978-3-642-13190-5_27http://doi.org/10.1007/978-3-642-13190-5_27

Chaum D, van Heyst E, 1991. Group signatures. Workshop on the Theory and Application of Cryptographic Techniques, p.257-265. doi: 10.1007/3-540-46416-6_22http://doi.org/10.1007/3-540-46416-6_22

Emura K, Hayashi T, 2018. A revocable group signature scheme with scalability from simple assumptions and its implementation. Proc 21st Int Conf on Information Security, p.442-460. doi: 10.1007/978-3-319-99136-8_24http://doi.org/10.1007/978-3-319-99136-8_24

Gao W, Hu YP, Zhang YH, et al., 2017. Lattice-based group signature with verifier-local revocation. J Shanghai Jiao Tong Univ (Sci), 22(3):313-321. doi: 10.1007/s12204-017-1837-1http://doi.org/10.1007/s12204-017-1837-1

Gentry C, Peikert C, Vaikuntanathan V, 2008. Trapdoors for hard lattices and new cryptographic constructions. Proc 40th Annual ACM Symp on Theory of Computing, p.197-206. doi: 10.1145/1374376.1374407http://doi.org/10.1145/1374376.1374407

Gordon SD, Katz J, Vaikuntanathan V, 2010. A group signature scheme from lattice assumptions. Proc 16th Int Conf on the Theory and Application of Cryptology and Information Security, p.395-412. doi: 10.1007/978-3-642-17373-8_23http://doi.org/10.1007/978-3-642-17373-8_23

Huang JY, Huang Q, Susilo W, 2020. Leakage-resilient group signature: definitions and constructions. Inform Sci, 509:119-132. doi: 10.1016/j.ins.2019.09.004http://doi.org/10.1016/j.ins.2019.09.004

Ishida A, Sakai Y, Emura K, et al., 2018. Fully anonymous group signature with verifier-local revocation. Proc 11th Int Conf on Security and Cryptography for Networks, p.23-42. doi: 10.1007/978-3-319-98113-0_2http://doi.org/10.1007/978-3-319-98113-0_2

Kawachi A, Tanaka K, Xagawa K, 2008. Concurrently secure identification schemes based on the worst-case hardness of lattice problems. Proc 14th Int Conf on the Theory and Application of Cryptology and Information Security, p.372-389. doi: 10.1007/978-3-540-89255-7_23http://doi.org/10.1007/978-3-540-89255-7_23

Langlois A, Ling S, Nguyen K, et al., 2014. Lattice-based group signature scheme with verifier-local revocation. Proc 17th Int Conf on Practice and Theory in Public-Key Cryptography, p.345-361. doi: 10.1007/978-3-642-54631-0_20http://doi.org/10.1007/978-3-642-54631-0_20

Libert B, Vergnaud D, 2009. Group signatures with verifier-local revocation and backward unlinkability in the standard model. Proc 8th Int Conf on Cryptology and Network Security, p.498-517. doi: 10.1007/978-3-642-10433-6_34http://doi.org/10.1007/978-3-642-10433-6_34

Ling S, Nguyen K, Stehlé D, et al., 2013. Improved zero-knowledge proofs of knowledge for the ISIS problem, and applications. Proc 16th Int Conf on Practice and Theory in Public-Key Cryptography, p.107-124. doi: 10.1007/978-3-642-36362-7_8http://doi.org/10.1007/978-3-642-36362-7_8

Ling S, Nguyen K, Roux-Langlois A, et al., 2018. A lattice-based group signature scheme with verifier-local revocation. Theor Comput Sci, 730:1-20. doi: 10.1016/j.tcs.2018.03.027http://doi.org/10.1016/j.tcs.2018.03.027

Micciancio D, Peikert C, 2012. Trapdoors for lattices: simpler, tighter, faster, smaller. Proc 31st Annual Int Conf on the Theory and Applications of Cryptographic Techniques, p.700-718. doi: 10.1007/978-3-642-29011-4_41http://doi.org/10.1007/978-3-642-29011-4_41

Micciancio D, Peikert C, 2013. Hardness of SIS and LWE with small parameters. Proc 33rd Annual Cryptology Conf, p.21-39. doi: 10.1007/978-3-642-40041-4_2http://doi.org/10.1007/978-3-642-40041-4_2

Nakanishi T, Funabiki N, 2005. Verifier-local revocation group signature schemes with backward unlinkability from bilinear maps. Proc 11th Int Conf on the Theory and Application of Cryptology and Information Security, p.533-548. doi: 10.1007/11593447_29http://doi.org/10.1007/11593447_29

Nakanishi T, Funabiki N, 2006. A short verifier-local revocation group signature scheme with backward unlinkability. Proc 1st Int Workshop on Security, p.17-32. doi: 10.1007/11908739_2http://doi.org/10.1007/11908739_2

Nguyen PQ, Zhang J, Zhang ZF, 2015. Simpler efficient group signatures from lattices. Proc 18th IACR Int Conf on Practice and Theory in Public-Key Cryptography, p.401-426. doi: 10.1007/978-3-662-46447-2_18http://doi.org/10.1007/978-3-662-46447-2_18

Perera MNS, Koshiba T, 2018a. Achieving full security for lattice-based group signatures with verifier-local revocation. Proc 20th Int Conf on Information and Communications Security, p.287-302. doi: 10.1007/978-3-030-01950-1_17http://doi.org/10.1007/978-3-030-01950-1_17

Perera MNS, Koshiba T, 2018b. Zero-knowledge proof for lattice-based group signature schemes with verifier-local revocation. Proc 21st Int Conf on Network-Based Information Systems, p.772-782. doi: 10.1007/978-3-319-98530-5_68http://doi.org/10.1007/978-3-319-98530-5_68

Perera MNS, Koshiba T, 2018c. Achieving strong security and verifier-local revocation for dynamic group signatures from lattice assumptions. Proc 14th Int Conf on Security and Trust Management, p.3-19. doi: 10.1007/978-3-030-01141-3_1http://doi.org/10.1007/978-3-030-01141-3_1

Regev O, 2005. On lattices, learning with errors, random linear codes, and cryptography. Proc 37th Annual ACM Symp on Theory of Computing, p.84-93. doi: 10.1145/1060590.1060603http://doi.org/10.1145/1060590.1060603

Song DX, 2001. Practical forward secure group signature schemes. Proc 8th ACM Conf on Computer and Communications Security, p.225-234. doi: 10.1145/501983.502015http://doi.org/10.1145/501983.502015

Zhang YH, Hu YP, Gao W, et al., 2016. Simpler efficient group signature scheme with verifier-local revocation from lattices. KSII Trans Int Inform Syst, 10(1):414-430. doi: 10.3837/tiis.2016.01.024http://doi.org/10.3837/tiis.2016.01.024

Zhang YH, Hu YP, Zhang QK, et al., 2019a. On new zero-knowledge proofs for lattice-based group signatures with verifier-local revocation. Proc 22nd Int Conf on Information Security, p.190-208. doi: 10.1007/978-3-030-30215-3_10http://doi.org/10.1007/978-3-030-30215-3_10

Zhang YH, Liu XM, Hu YP, et al., 2019b. Lattice-based group signatures with verifier-local revocation: achieving shorter key-sizes and explicit traceability with ease. Proc 18th Int Conf on Cryptology and Network Security, p.120-140. doi: 10.1007/978-3-030-31578-8_7http://doi.org/10.1007/978-3-030-31578-8_7

Views

Downloads

CSCD

Alert me when the article has been cited

Submit

Tools

Publicity Resources

Efficient hierarchical identity based encryption scheme in the standard model over lattices

Related Author

Feng-he WANG

Chun-xiao WANG

Zhen-hua LIU

Related Institution

Department of Mathematics and Physics, Shandong Jianzhu University

School of Mathematics and Statistics, Xidian University

Address：Zhejiang University Press, 148 Tianmushan Road, Hangzhou, China Postal code：310028
Tel：+86-571-88273162 Email：fitee@zju.edu.cn
It is recommended to read the content of this site in Chrome&IE9+. Please switch to extreme mode in browser 360.
Cookies We use cookies to help provide and enhance our service and tailor content. By continuing, you agree to the use of cookies.

⁰