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

Theoretical Computer Science

Lattice-based logarithmic-size forward-secure ring signatures in QROM

Priyanka Dutta, Willy Susilo, Fuchun Guo, Dung Hoang Duong

Published Jan 29, 2026• 2 citations
Publisher

Abstract

Ring signatures, a novel cryptographic primitive, were introduced by Rivest, Shamir, and Tauman at ASIACRYPT 2001. It allows a member of a group to sign a message on behalf of an ad-hoc group of users, known as a ring, without revealing its identity. Ring signatures, initially introduced for applications such as whistle-blowing and confidential disclosures, have since gained significant relevance and widespread adoption across various domains, including blockchain technologies, ad-hoc networks, anonymous transactions, location-based services, cloud computing platforms, and outsourced computation. However, traditional ring signatures are vulnerable if the signers’ keys are compromised. To resolve this vulnerability, Liu and Wong introduced the notion of forward-secure ring signatures at IJNS 2008. Forward-security ensures that even if a signer’s secret key is compromised, signatures generated in prior time periods remain secure. It significantly reduces the damage caused by secret key exposure, making it crucial for long-term security in applications such as whistle-blowing or anonymous authentication. However, most existing forward-secure ring signature schemes are based on number-theoretic assumptions, making them vulnerable to quantum adversaries. Yu and Wang proposed a quantum-safe forward-secure ring signature scheme at ICICS 2023, and Yu et al. further extended this work in Computer Networks (2025), retaining the same ring signature scheme with forward security. But the scheme suffers from large signatures that grow linearly with the ring size. In this paper, we propose a lattice-based forward-secure ring signature scheme in the quantum random oracle model ( QROM ) that simultaneously achieves security against quantum adversaries and compact signature size. Notably, the signature size is logarithmic in the number of members in the ring, enabling significantly better scalability compared to prior constructions.

DOI
10.1016/j.tcs.2026.115787

Related papers

Lattice-based group signatures with forward security for anonymous authentication

Simin Chen, Jiageng Chen

Group signatures allow users to sign messages on behalf of a group without revealing authority is capable of identifying the user who generated it. However, the exposure of the user's signing key will severely damage the group signature scheme. In order to reduce the loss caused by signing key leakage, Song proposed the first forward-secure group signature. If a group signing key is revealed at the current time period, the previous signing key will not be affected. This means that the attacker cannot forge group signatures regarding messages signed in the past. To resist quantum attacks, many lattice-based forward-secure group signatures have been proposed. However, their key-update algorithm is expensive since they require some costly computations such as the Hermite normal form (HNF) operations and conversion from a full-rank set of lattice vectors into a basis. In this paper, we propose the group signature with forward security from lattice. In comparison with previous works, we have several advantages: Firstly, our scheme is more effective since we only need to sample some vectors independently from a discrete Gaussian during the key-update algorithm. Secondly, the derived secret key size is linear instead of quadratic with the lattice dimensions, which is more friendly towards lightweight applications. Anonymous authentication plays an increasingly critical role in protecting privacy and security in the environment where private information could be collected for intelligent analysis. Our work contributes to the anonymous authentication in the post-quantum setting, which has wide potential applications in the IoT environment.

Heliyon•Mar 28, 2023•9 citations

A Lattice-Based Certificateless Traceable Ring Signature Scheme

Junbin Liang, Jianye Huang, Qiong Huang +2 more

A ring signature (RS) scheme enables a group member to sign messages on behalf of its group without revealing the definite signer identify, but this also leads to the abuse of anonymity by malicious signers, which can be prevented by traceable ring signatures (TRS). Up until that point, traceable ring signatures have been secure based on the difficult problem of number-theoretic (discrete logarithms or RSA), but since the advent of quantum computers, traditional traceable ring signatures may no longer be secure. Thus Feng proposed a lattice based TRS, which are resistant to attacks by quantum computers. However, that works did not tackle the certificate management problem. To close this gap, a quantum-resistant certificateless TRS scheme was proposed in the study. To the best of our knowledge, this is the first lattice based certificateless TRS. In detail, a specific TRS scheme was combined with the lattice-based certificateless signature technology to solve the certificate management problem while avoid key escrow problem. Additionally, a better zero-knowledge protocol is used to improve the computational efficiency of the scheme, and by reducing the soundness error of the zero-knowledge protocol, the number of runs of the zero-knowledge protocol is reduced, so that the communication overhead of the scheme is reduced. Under random oracle model, the proposed scheme satisfies tag-linkability, anonymity, exculpability and is secure based on the SIS problem and the DLWE problem. In conclusion, the proposed scheme is more practical and promising in e-voting.

Information•Mar 2, 2023•11 citations

Efficient Ring Signature Scheme Without Random Oracle from Lattices

Wen Gao, Yupu Hu, Baocang Wang +2 more

Among post-quantum alternatives, latticebased cryptography is the most promising one, due to its simple operations, reduction from aver-age-case to worstcase hardness, and supporting of rich functionalities. Ring signature enables a user to sign anonymously on behalf of an adaptively chosen group, and has multiple applications in anonymous e-voting, anonymous authentication, whistle blowing etc. However, most lattice-based ring signature schemes were constructed in the random oracle model from lattice basis delegation and they suffer large verification key sizes as a common disadvantage. This work proposes an efficient ring signature scheme from lattice basis delegation without random oracle based on the extended split-SIS problem, whose security is approximately as hard as the worst-case SIVP problem. Our scheme is proved to be anonymous and existentially unforgeable under latticebased assumptions. Finally, the verification key size is significantly reduced to a small constant, instead of increasing linearly with the number of ring members.

Chinese Journal of Electronics•Mar 1, 2019•6 citations

Lattice-based deniable ring signatures

Wen Gao, Liqun Chen, Yupu Hu +3 more

In cryptography, a ring signature is anonymous as it hides the signer’s identity among other users. When generating the signature, the users are arranged as a ring. Compared with group signatures, a ring signature scheme needs no group manager or special setup and supports flexibility of group choice. However, the anonymity provided by ring signatures can be used to conceal a malicious signer and put other ring members under suspicion. At the other extreme, it does not allow the actual signer to prove their identity and gain recognition for their actions. A deniable ring signature is designed to overcome these disadvantages. It can initially protect the signer, but if necessary, it enables other ring members to deny their involvement, and allows the real signer to prove who made the signed action. Many real-world applications can benefit from such signatures. Inspired by the requirement for them to remain viable in the post-quantum age, this work proposes a new non-interactive deniable ring signature scheme based on lattice assumptions. Our scheme is proved to be anonymous, traceable and non-frameable under quantum attacks.

International Journal of Information Security•Aug 20, 2018•19 citations

Strongly Unforgeable Ring Signature Scheme from Lattices in the Standard Model

Geontae Noh, Ji Young Chun, Ik Rae Jeong

In a ring signature scheme, a user selects an arbitrary ring to be able to sign a message on behalf of the ring without revealing the signer’s identity. Whistle-blowers especially find this useful. To date, various ring signature schemes have been proposed, all considered to be secure as existentially unforgeable with respect to insider corruption; that is, an adversary who chooses ring-message pairs for which he requests signatures, corrupts honest users, and obtains their signing keys can not produce forgeries for new ring-message pairs. Lattice-based ring signature schemes offer lower computational overhead and security from quantum attacks. In this paper, we offer a lattice-based scheme. We begin by showing that the existing ring signature schemes are not sufficiently secure, because existential unforgeability still permits a signer to potentially produce a new signature on previously signed messages. Furthermore, we show that existing ring signature schemes from lattices are not even existentially unforgeable with respect to insider corruption. We then improve previous schemes by applying, for the first time, the concept of strong unforgeability with respect to insider corruption to a ring signature scheme in lattices. This offers more security than any previous ring signature scheme: adversaries cannot produce new signatures for any ring-message pair, including previously signed ring-message pairs.

Journal of Applied Mathematics•Jan 1, 2014•3 citations

Improved lattice-based ring signature schemes from basis delegation

Gao Gao, Wen Wen, Hu +5 more

Ring signature enables the members to sign anonymously without a manager, it has many online applications, such as e-voting, e-money, whistle blowing etc. As a promising post-quantum candidate, lattice-based cryptography attracts much attention recently. Several efficient lattice-based ring signatures have been naturally constructed from lattice basis delegation, but all of them have large verification key sizes. Our observation finds that a new concept called the split- small integer solution(SIS) problem introduced by Nguyen et al. at PKC’15 is excellent in reducing the public key sizes of lattice-based ring signature schemes from basis delegation. In this research, we first define an extended concept called the extended split-SIS problem, and then prove that the hardness of the extended problem is as hard as the approximating shortest independent vectors problem(SIVP) problem within certain polynomial factor. Moreover, we present an improved ring signature and prove that it is anonymous and unforgeable against the insider corruption. Finally, we give two other improved existing ring signature schemes from lattices. In the end, we show the comparison with the original scheme in terms of the verification key sizes. Our research data illustrate that the public key sizes of the proposed schemes are reduced significantly.

中国邮电高校学报：英文版•Jan 1, 2016•1 citation
Ring signatures, a novel cryptographic primitive, were introduced by Rivest, Shamir, and Tauman at ASIACRYPT 2001. It allows a member of a group to sign a message on behalf of an ad-hoc group of users, known as a ring, without revealing its identity. Ring signatures, initially introduced for applications such as whistle-blowing and confidential disclosures, have since gained significant relevance and widespread adoption across various domains, including blockchain technologies, ad-hoc networks, anonymous transactions, location-based services, cloud computing platforms, and outsourced computation. However, traditional ring signatures are vulnerable if the signers’ keys are compromised. To resolve this vulnerability, Liu and Wong introduced the notion of forward-secure ring signatures at IJNS 2008. Forward-security ensures that even if a signer’s secret key is compromised, signatures generated in prior time periods remain secure. It significantly reduces the damage caused by secret key exposure, making it crucial for long-term security in applications such as whistle-blowing or anonymous authentication. However, most existing forward-secure ring signature schemes are based on number-theoretic assumptions, making them vulnerable to quantum adversaries. Yu and Wang proposed a quantum-safe forward-secure ring signature scheme at ICICS 2023, and Yu et al. further extended this work in Computer Networks (2025), retaining the same ring signature scheme with forward security. But the scheme suffers from large signatures that grow linearly with the ring size. In this paper, we propose a lattice-based forward-secure ring signature scheme in the quantum random oracle model ( QROM ) that simultaneously achieves security against quantum adversaries and compact signature size. Notably, the signature size is logarithmic in the number of members in the ring, enabling significantly better scalability compared to prior constructions.
Group signatures allow users to sign messages on behalf of a group without revealing authority is capable of identifying the user who generated it. However, the exposure of the user's signing key will severely damage the group signature scheme. In order to reduce the loss caused by signing key leakage, Song proposed the first forward-secure group signature. If a group signing key is revealed at the current time period, the previous signing key will not be affected. This means that the attacker cannot forge group signatures regarding messages signed in the past. To resist quantum attacks, many lattice-based forward-secure group signatures have been proposed. However, their key-update algorithm is expensive since they require some costly computations such as the Hermite normal form (HNF) operations and conversion from a full-rank set of lattice vectors into a basis. In this paper, we propose the group signature with forward security from lattice. In comparison with previous works, we have several advantages: Firstly, our scheme is more effective since we only need to sample some vectors independently from a discrete Gaussian during the key-update algorithm. Secondly, the derived secret key size is linear instead of quadratic with the lattice dimensions, which is more friendly towards lightweight applications. Anonymous authentication plays an increasingly critical role in protecting privacy and security in the environment where private information could be collected for intelligent analysis. Our work contributes to the anonymous authentication in the post-quantum setting, which has wide potential applications in the IoT environment.
A ring signature (RS) scheme enables a group member to sign messages on behalf of its group without revealing the definite signer identify, but this also leads to the abuse of anonymity by malicious signers, which can be prevented by traceable ring signatures (TRS). Up until that point, traceable ring signatures have been secure based on the difficult problem of number-theoretic (discrete logarithms or RSA), but since the advent of quantum computers, traditional traceable ring signatures may no longer be secure. Thus Feng proposed a lattice based TRS, which are resistant to attacks by quantum computers. However, that works did not tackle the certificate management problem. To close this gap, a quantum-resistant certificateless TRS scheme was proposed in the study. To the best of our knowledge, this is the first lattice based certificateless TRS. In detail, a specific TRS scheme was combined with the lattice-based certificateless signature technology to solve the certificate management problem while avoid key escrow problem. Additionally, a better zero-knowledge protocol is used to improve the computational efficiency of the scheme, and by reducing the soundness error of the zero-knowledge protocol, the number of runs of the zero-knowledge protocol is reduced, so that the communication overhead of the scheme is reduced. Under random oracle model, the proposed scheme satisfies tag-linkability, anonymity, exculpability and is secure based on the SIS problem and the DLWE problem. In conclusion, the proposed scheme is more practical and promising in e-voting.
Among post-quantum alternatives, latticebased cryptography is the most promising one, due to its simple operations, reduction from aver-age-case to worstcase hardness, and supporting of rich functionalities. Ring signature enables a user to sign anonymously on behalf of an adaptively chosen group, and has multiple applications in anonymous e-voting, anonymous authentication, whistle blowing etc. However, most lattice-based ring signature schemes were constructed in the random oracle model from lattice basis delegation and they suffer large verification key sizes as a common disadvantage. This work proposes an efficient ring signature scheme from lattice basis delegation without random oracle based on the extended split-SIS problem, whose security is approximately as hard as the worst-case SIVP problem. Our scheme is proved to be anonymous and existentially unforgeable under latticebased assumptions. Finally, the verification key size is significantly reduced to a small constant, instead of increasing linearly with the number of ring members.
In cryptography, a ring signature is anonymous as it hides the signer’s identity among other users. When generating the signature, the users are arranged as a ring. Compared with group signatures, a ring signature scheme needs no group manager or special setup and supports flexibility of group choice. However, the anonymity provided by ring signatures can be used to conceal a malicious signer and put other ring members under suspicion. At the other extreme, it does not allow the actual signer to prove their identity and gain recognition for their actions. A deniable ring signature is designed to overcome these disadvantages. It can initially protect the signer, but if necessary, it enables other ring members to deny their involvement, and allows the real signer to prove who made the signed action. Many real-world applications can benefit from such signatures. Inspired by the requirement for them to remain viable in the post-quantum age, this work proposes a new non-interactive deniable ring signature scheme based on lattice assumptions. Our scheme is proved to be anonymous, traceable and non-frameable under quantum attacks.
In a ring signature scheme, a user selects an arbitrary ring to be able to sign a message on behalf of the ring without revealing the signer’s identity. Whistle-blowers especially find this useful. To date, various ring signature schemes have been proposed, all considered to be secure as existentially unforgeable with respect to insider corruption; that is, an adversary who chooses ring-message pairs for which he requests signatures, corrupts honest users, and obtains their signing keys can not produce forgeries for new ring-message pairs. Lattice-based ring signature schemes offer lower computational overhead and security from quantum attacks. In this paper, we offer a lattice-based scheme. We begin by showing that the existing ring signature schemes are not sufficiently secure, because existential unforgeability still permits a signer to potentially produce a new signature on previously signed messages. Furthermore, we show that existing ring signature schemes from lattices are not even existentially unforgeable with respect to insider corruption. We then improve previous schemes by applying, for the first time, the concept of strong unforgeability with respect to insider corruption to a ring signature scheme in lattices. This offers more security than any previous ring signature scheme: adversaries cannot produce new signatures for any ring-message pair, including previously signed ring-message pairs.
Ring signature enables the members to sign anonymously without a manager, it has many online applications, such as e-voting, e-money, whistle blowing etc. As a promising post-quantum candidate, lattice-based cryptography attracts much attention recently. Several efficient lattice-based ring signatures have been naturally constructed from lattice basis delegation, but all of them have large verification key sizes. Our observation finds that a new concept called the split- small integer solution(SIS) problem introduced by Nguyen et al. at PKC’15 is excellent in reducing the public key sizes of lattice-based ring signature schemes from basis delegation. In this research, we first define an extended concept called the extended split-SIS problem, and then prove that the hardness of the extended problem is as hard as the approximating shortest independent vectors problem(SIVP) problem within certain polynomial factor. Moreover, we present an improved ring signature and prove that it is anonymous and unforgeable against the insider corruption. Finally, we give two other improved existing ring signature schemes from lattices. In the end, we show the comparison with the original scheme in terms of the verification key sizes. Our research data illustrate that the public key sizes of the proposed schemes are reduced significantly.