Challenges
Datasets
Workspaces
Papers
Discussions
Leaderboard
Log inSign up
Challenges
Datasets
Workspaces
Papers
Discussions
Leaderboard
Blog
Job Board
Q3AS

© 2026 Aqora Quantum S.A.S.

TermsPrivacyLegal Notice

Lattice-based Group Signature Scheme with Verifier-local Revocation.

Adeline Roux-Langlois, San Ling, Khoa Nguyen, Huaxiong Wang

Published Jan 1, 2014• 3 citations
OpenAlex

Abstract

Abstract. 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 weaker security assumption. In the random oracle model, our scheme is proved to be secure based on the hardness of the SIVPÕ(n1.5) problem in general lattices- an assumption that is as weak as those of state-of-the-art lattice-based standard signatures. Moreover, our construction works without relying on encryption schemes, which is an intriguing feature for group signatures.

Related papers

Verifier-local revocation group signatures with backward unlinkability from lattices

Yanhua Zhang, Ximeng Liu, Yupu Hu +2 more

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 $${\cal O}\left( {\log \,N} \right)$$ 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.

Frontiers of Information Technology & Electronic Engineering•Jun 1, 2022•7 citations

An Improved Group Signature Scheme with VLR over Lattices

Yanhua Zhang, Ximeng Liu, Yupu Hu +2 more

For group signatures (GS) supporting membership revocation, verifier-local revocation (VLR) mechanism is the most flexible choice. As a post-quantum secure cryptographic counterpart of classical schemes, the first dynamic GS-VLR scheme over lattices was put forward by Langlois et al. at PKC 2014; furthermore, a corrected version was shown at TCS 2018. However, both designs are within Bonsai trees and featuring bit-sizes of group public-key and member secret signing key proportional to log N where N is the group size; therefore, both schemes are not suitable for a large group. In this paper, we provide an improved dynamic GS-VLR over lattices, which is efficient by eliminating a O log N factor for both sizes. To realize the goal, we adopt a more efficient and compact identity-encoding technique. At the heart of our new construction is a new Stern-type statistical zero-knowledge argument of knowledge protocol which may be of some independent cryptographic interest.

Security and Communication Networks•Oct 21, 2021•3 citations

Lattice-based group signature scheme without random oracle

Thakkalapally Preethi, B. B. Amberker

Group signature is a cryptographic primitive where any member can anonymously sign a message on behalf of the population they belong to. Several group signatures were proposed based on number-theoretic assumptions. All these schemes are insecure in the presence of quantum computers. Group signatures based on lattice assumptions are believed to be quantum-resistant. In the past few years, group signatures based on lattice assumptions have been proposed and most of them are proved to be secure in random-oracle model. This paper presents a lattice-based group signature scheme without using random-oracle. Our scheme is based on correlation-intractable function ensembles for all evasive relations which are constructed recently based on well-defined assumptions. Security of our scheme is proved based on correlation-intractable function ensembles and hardness of Short Integer Solution and Learning With Errors problem.

Information Security Journal A Global Perspective•Jun 20, 2020•6 citations

Lattice-based verifiably encrypted group signatures

Peidong Guan, Shuai Wang

Abstract Verifiably encrypted signature (VES) schemes are extensively utilized in fair exchange which combine the features of encryption and signature, aiming to provide a solution that can not only verify the validity of signatures but also safeguard the privacy of signatures. With the development of quantum algorithms and quantum computing, it is necessary to construct a VES protocol that can resist attack of quantum computing. At the same time, some new security properties can also be added to the VES protocol to enhance its security. To reach this goal, we propose a state-of-the-art lattice-based verifiably encrypted group signature (VEGS) scheme. In the random oracle model, the VEGS scheme is provably secure under the assumptions of learning with error (LWE) and inhomogeneous small integer solution (ISIS). Our scheme provides five security properties, namely unforgeability, opacity, extractability, anonymity and traceability. The three properties unforgeability, opacity and extractability are the properties that the VES protocol needs to meet, and the anonymity and traceability properties are additional security properties brought by combining with the group signature.

Cybersecurity•Jan 7, 2026•0 citations

Lattice-Based Revocable Certificateless Signature

Ying-Hao Hung, Yuh‐Min Tseng, Sen‐Shan Huang

Certificateless signatures (CLS) are noticeable because they may resolve the key escrow problem in ID-based signatures and break away the management problem regarding certificate in conventional signatures. However, the security of the mostly previous CLS schemes relies on the difficulty of solving discrete logarithm or large integer factorization problems. These two problems would be solved by quantum computers in the future so that the signature schemes based on them will also become insecure. For post-quantum cryptography, lattice-based cryptography is significant due to its efficiency and security. However, no study on addressing the revocation problem in the existing lattice-based CLS schemes is presented. In this paper, we focus on the revocation issue and present the first revocable CLS (RCLS) scheme over lattices. Based on the short integer solution (SIS) assumption over lattices, the proposed lattice-based RCLS scheme is shown to be existential unforgeability against adaptive chosen message attacks. By performance analysis and comparisons, the proposed lattice-based RCLS scheme is better than the previously proposed lattice-based CLS scheme, in terms of private key size, signature length and the revocation mechanism.

Symmetry•Oct 20, 2017•15 citations

Traceable Signatures using Lattices

Thakkalapally Preethi, B. B. Amberker

Traceable Signatures is an extension of group signatures that allow tracing of all signatures generated by a particular group member without violating the privacy of remaining members. It also allows members to claim the ownership of previously signed messages. Till date, all the existing traceable signatures are based on number-theoretic assumptions which are insecure in the presence of quantum computers. This work presents the first traceable signature scheme in lattices, which is secure even after the existence of quantum computers. Our scheme is proved to be secure in the random oracle model based on the hardness of Short Integer Solution and Learning with Errors

The International Arab Journal of Information Technology•Oct 22, 2020•1 citation
Abstract. 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 weaker security assumption. In the random oracle model, our scheme is proved to be secure based on the hardness of the SIVPÕ(n1.5) problem in general lattices- an assumption that is as weak as those of state-of-the-art lattice-based standard signatures. Moreover, our construction works without relying on encryption schemes, which is an intriguing feature for group signatures.
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 O(log⁡ N){\cal O}\left( {\log \,N} \right)O(logN) 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.
For group signatures (GS) supporting membership revocation, verifier-local revocation (VLR) mechanism is the most flexible choice. As a post-quantum secure cryptographic counterpart of classical schemes, the first dynamic GS-VLR scheme over lattices was put forward by Langlois et al. at PKC 2014; furthermore, a corrected version was shown at TCS 2018. However, both designs are within Bonsai trees and featuring bit-sizes of group public-key and member secret signing key proportional to log N where N is the group size; therefore, both schemes are not suitable for a large group. In this paper, we provide an improved dynamic GS-VLR over lattices, which is efficient by eliminating a O log N factor for both sizes. To realize the goal, we adopt a more efficient and compact identity-encoding technique. At the heart of our new construction is a new Stern-type statistical zero-knowledge argument of knowledge protocol which may be of some independent cryptographic interest.
Group signature is a cryptographic primitive where any member can anonymously sign a message on behalf of the population they belong to. Several group signatures were proposed based on number-theoretic assumptions. All these schemes are insecure in the presence of quantum computers. Group signatures based on lattice assumptions are believed to be quantum-resistant. In the past few years, group signatures based on lattice assumptions have been proposed and most of them are proved to be secure in random-oracle model. This paper presents a lattice-based group signature scheme without using random-oracle. Our scheme is based on correlation-intractable function ensembles for all evasive relations which are constructed recently based on well-defined assumptions. Security of our scheme is proved based on correlation-intractable function ensembles and hardness of Short Integer Solution and Learning With Errors problem.
Abstract Verifiably encrypted signature (VES) schemes are extensively utilized in fair exchange which combine the features of encryption and signature, aiming to provide a solution that can not only verify the validity of signatures but also safeguard the privacy of signatures. With the development of quantum algorithms and quantum computing, it is necessary to construct a VES protocol that can resist attack of quantum computing. At the same time, some new security properties can also be added to the VES protocol to enhance its security. To reach this goal, we propose a state-of-the-art lattice-based verifiably encrypted group signature (VEGS) scheme. In the random oracle model, the VEGS scheme is provably secure under the assumptions of learning with error (LWE) and inhomogeneous small integer solution (ISIS). Our scheme provides five security properties, namely unforgeability, opacity, extractability, anonymity and traceability. The three properties unforgeability, opacity and extractability are the properties that the VES protocol needs to meet, and the anonymity and traceability properties are additional security properties brought by combining with the group signature.
Certificateless signatures (CLS) are noticeable because they may resolve the key escrow problem in ID-based signatures and break away the management problem regarding certificate in conventional signatures. However, the security of the mostly previous CLS schemes relies on the difficulty of solving discrete logarithm or large integer factorization problems. These two problems would be solved by quantum computers in the future so that the signature schemes based on them will also become insecure. For post-quantum cryptography, lattice-based cryptography is significant due to its efficiency and security. However, no study on addressing the revocation problem in the existing lattice-based CLS schemes is presented. In this paper, we focus on the revocation issue and present the first revocable CLS (RCLS) scheme over lattices. Based on the short integer solution (SIS) assumption over lattices, the proposed lattice-based RCLS scheme is shown to be existential unforgeability against adaptive chosen message attacks. By performance analysis and comparisons, the proposed lattice-based RCLS scheme is better than the previously proposed lattice-based CLS scheme, in terms of private key size, signature length and the revocation mechanism.
Traceable Signatures is an extension of group signatures that allow tracing of all signatures generated by a particular group member without violating the privacy of remaining members. It also allows members to claim the ownership of previously signed messages. Till date, all the existing traceable signatures are based on number-theoretic assumptions which are insecure in the presence of quantum computers. This work presents the first traceable signature scheme in lattices, which is secure even after the existence of quantum computers. Our scheme is proved to be secure in the random oracle model based on the hardness of Short Integer Solution and Learning with Errors