Paper 2014/033

Lattice-based Group Signature Scheme with Verier-local Revocation

Adeline Langlois, San Ling, Khoa Nguyen, and Huaxiong Wang


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. In the random oracle model, our scheme is proven secure based on the hardness of the SIVP_O(n^{2.5}) problem in general lattices. Moreover, our construction works without relying on public-key encryption schemes, which is an intriguing feature for group signatures.

Note: The previous version, published at PKC 2014, contains a flaw in the revocation mechanism. This flaw is fixed in the present version, by binding the user's revocation token to an LWE instance. The authors are grateful to Shota Yamada for pointing out the flaw, and for insightful discussions that lead to the amendment.

Available format(s)
Publication info
A major revision of an IACR publication in PKC 2014
group signatureverifier-local revocationlattice-based cryptography
Contact author(s)
khoantt @ ntu edu sg
2016-08-05: revised
2014-01-12: received
See all versions
Short URL
Creative Commons Attribution


      author = {Adeline Langlois and San Ling and Khoa Nguyen and Huaxiong Wang},
      title = {Lattice-based Group Signature Scheme with Verier-local Revocation},
      howpublished = {Cryptology ePrint Archive, Paper 2014/033},
      year = {2014},
      note = {\url{}},
      url = {}
Note: In order to protect the privacy of readers, does not use cookies or embedded third party content.