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

Journal of King Saud University - Computer and Information Sciences

A constant-size lattice-based partially-dynamic group signature scheme in quantum random oracle model

Meryem Soysaldı, Sedat Akleylek

Published Feb 10, 2022• 11 citations
Publisher

Abstract

A group signature allows a group member who signs the message on behalf of the other group members. Any recipient also verifies the signature without knowing the signer. However, it is possible to reveal the signer’s identity since the group signatures have the tracing mechanism. In general, the group signature size increases the number of group members. However, the schemes are also proposed with the constant signature size. On the other hand, the security of some schemes are based on the discrete logarithm and factorization problems while some schemes which are secure against quantum attacks are proposed. To the best of our knowledge, the signature scheme in the group concept has not been proposed on lattices in quantum oracles. In this paper, we propose a new constant-size and partially-dynamic group signature scheme on lattice assumptions. We combine the Dilithium signature scheme, a Stern-like zero-knowledge scheme and Regev’s encryption scheme. We give a zero-knowledge argument system for our proposed scheme and security analysis in the quantum random oracle model. According to the comparison results, the proposed scheme has better size complexity in asymptotic concept.

DOI
10.1016/j.jksuci.2021.12.014

Related papers

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

A fully dynamic forward-secure group signature from lattice

Zhijian Liao, Qiong Huang, Xinjian Chen

Abstract A forward-secure group signature (FSGS) ensures the unforgeability of signatures in the past time period despite signing secret key is leaked in the current time period. As we know, traditional FSGS schemes are mostly relying on number-theoretic assumptions unable to resist quantum attacks. Therefore, we present an efficient lattice-based fully dynamic (i.e. users can flexibly join or quit the group) forward-secure group signature (DFSGS) by combining an improved version of FSGS scheme proposed by Ling. Based on an efficient zero-knowledge argument, we construct argument of knowledge of the committed value and the plaintext that help with privacy protection. Our DFSGS scheme is proved to be anonymous and forward-secure traceable relying on short integer solution and learning with errors assumptions in random oracle model. Moreover, the lengths of group public key and signature of our DFSGS scheme have been improved, and the length of user secret key has no connection with the quantity of group members.

Cybersecurity•Oct 2, 2022•7 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

A novel lattice-based proxy signature scheme

Mohammad Beheshti-Atashgah, Mohsen Ajori, Mahmoud Gardeshi +1 more

In a proxy signature scheme, an original signer delegates his/her signing capability to a proxy signer and then the proxy signer can sign messages on behalf of the original signer. The security of many proxy signature schemes that have been proposed depends, either directly or indirectly, on either the difficulty of big integers factoring problem or the difficulty of finding discrete logarithm in a finite group. These types of schemes cannot resist quantum attacks. In this paper, we propose a new lattice-based proxy signature scheme which can resist quantum attacks. The proposed scheme is based on the GGH-signature scheme and also satisfies all the security requirements of proxy signature schemes.

Iranian Conference on Electrical Engineering•May 1, 2012•0 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

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
A group signature allows a group member who signs the message on behalf of the other group members. Any recipient also verifies the signature without knowing the signer. However, it is possible to reveal the signer’s identity since the group signatures have the tracing mechanism. In general, the group signature size increases the number of group members. However, the schemes are also proposed with the constant signature size. On the other hand, the security of some schemes are based on the discrete logarithm and factorization problems while some schemes which are secure against quantum attacks are proposed. To the best of our knowledge, the signature scheme in the group concept has not been proposed on lattices in quantum oracles. In this paper, we propose a new constant-size and partially-dynamic group signature scheme on lattice assumptions. We combine the Dilithium signature scheme, a Stern-like zero-knowledge scheme and Regev’s encryption scheme. We give a zero-knowledge argument system for our proposed scheme and security analysis in the quantum random oracle model. According to the comparison results, the proposed scheme has better size complexity in asymptotic concept.
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 A forward-secure group signature (FSGS) ensures the unforgeability of signatures in the past time period despite signing secret key is leaked in the current time period. As we know, traditional FSGS schemes are mostly relying on number-theoretic assumptions unable to resist quantum attacks. Therefore, we present an efficient lattice-based fully dynamic (i.e. users can flexibly join or quit the group) forward-secure group signature (DFSGS) by combining an improved version of FSGS scheme proposed by Ling. Based on an efficient zero-knowledge argument, we construct argument of knowledge of the committed value and the plaintext that help with privacy protection. Our DFSGS scheme is proved to be anonymous and forward-secure traceable relying on short integer solution and learning with errors assumptions in random oracle model. Moreover, the lengths of group public key and signature of our DFSGS scheme have been improved, and the length of user secret key has no connection with the quantity of group members.
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 a proxy signature scheme, an original signer delegates his/her signing capability to a proxy signer and then the proxy signer can sign messages on behalf of the original signer. The security of many proxy signature schemes that have been proposed depends, either directly or indirectly, on either the difficulty of big integers factoring problem or the difficulty of finding discrete logarithm in a finite group. These types of schemes cannot resist quantum attacks. In this paper, we propose a new lattice-based proxy signature scheme which can resist quantum attacks. The proposed scheme is based on the GGH-signature scheme and also satisfies all the security requirements of proxy signature schemes.
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
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.