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

Strongly Unforgeable Signatures and Hierarchical Identity-based Signatures from Lattices without Random Oracles.

Markus Rückert

Published Jan 1, 2010• 0 citations
OpenAlex

Abstract

Abstract. We propose a variant of the “bonsai tree ” signature scheme, a lattice-based existentially unforgeable signature scheme in the standard model. Our construction offers the same efficiency as the “bonsai tree” scheme but supports the stronger notion of strong unforgeability. Strong unforgeability demands that the adversary is unable to produce a new message-signature pair (m, s), even if he or she is allowed to see a different signature s ′ for m. In particular, we provide the first treeless signature scheme that supports strong unforgeability for the post-quantum era in the standard model. Moreover, we show how to directly implement identity-based, and even hierarchical identity-based, signatures (IBS) in the same strong security model without random oracles. An additional advantage of this direct approach over the usual generic conversion of hierarchical identity-based encryption to IBS is that we can exploit the efficiency of ideal lattices without significantly harming security. We equip all constructions with strong security proofs based on mild worst-case assumptions on lattices and we also propose concrete security parameters.

Related papers

Making Existential-Unforgeable Signatures Strongly Unforgeable in the Quantum Random-Oracle Model

Eaton, Edward, Fang Song

Strongly unforgeable signature schemes provide a more stringent security guarantee than the standard existential unforgeability. It requires that not only forging a signature on a new message is hard, it is infeasible as well to produce a new signature on a message for which the adversary has seen valid signatures before. Strongly unforgeable signatures are useful both in practice and as a building block in many cryptographic constructions. This work investigates a generic transformation that compiles any existential-unforgeable scheme into a strongly unforgeable one, which was proposed by Teranishi et al. and was proven in the classical random-oracle model. Our main contribution is showing that the transformation also works against quantum adversaries in the quantum random-oracle model. We develop proof techniques such as adaptively programming a quantum random-oracle in a new setting, which could be of independent interest. Applying the transformation to an existential-unforgeable signature scheme due to Cash et al., which can be shown to be quantum-secure assuming certain lattice problems are hard for quantum computers, we get an efficient quantum-secure strongly unforgeable signature scheme in the quantum random-oracle model.

arXiv:1509.02944•Leibniz international proceedings in informatics•Jan 1, 2015•17 citations

A New Hierarchical Identity-based Signature Scheme From Lattices In The Standard Model

Miaomiao Tian, Liusheng Huang, Wei Yang

Hierarchical identity-based signature (HIBS), which plays an important role in large communities, is a generaliza-tion of identity-based signature (IBS). In this paper, we present a new HIBS scheme from lattices without ran-dom oracles. The new scheme is proven to be strongly unforgeable against selective identity attacks under the standard hardness assumption of the short integer so-lution (SIS) problem. Furthermore, the secret key size and the signature length of our scheme are both invariant and much shorter than those of the previous lattice-based HIBS schemes. To the best of our knowledge, our con-struction is the first short lattice-based HIBS scheme in the standard model.

•Jan 1, 2011•15 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

Novel efficient identity-based signature on lattices

Jiangshan Chen, Yupu Hu, Liang Hong-mei +1 more

With the rapid development of electronic information technology, digital signature has become an indispensable part of our lives. Traditional public key certificate cryptosystems cannot overcome the limitations of certificate management. Identity-based cryptosystems can avoid the certificate management issues. The development of quantum computers has brought serious challenges to traditional cryptography. Post-quantum cryptography research is imperative. At present, almost all post-quantum identity-based signature (IBS) schemes are constructed using Gaussian sampling or trapdoor technologies. However, these two technologies have a great impact on computational efficiency. To overcome this problem, we construct an IBS scheme on lattices by employing Lyubashevsky’s signature scheme. Based on the shortest vector problem on lattices, our scheme does not use Gaussian sampling or trapdoor technologies. In the random oracle model, it is proved that our scheme is strongly unforgeable against adaptive chosen messages and identity attacks. The security level of our scheme is strongly unforgeable, which is a higher level than the existential unforgeability of other schemes. Compared with other efficient schemes, our scheme has advantages in computation complexity and security.

Frontiers of Information Technology & Electronic Engineering•Jul 2, 2020•7 citations

Post-quantum Strongly Unforgeable Identity-Based Signature Scheme from Lattices without Random Oracles

Zhenhua Liu, Xiangsong Zhang, Tsuyoshi Takagi

Inspired by Agrawal, Boneh and Boyen's identity-based encryption scheme, we proposed a post-quantum identity-based signature scheme from lattices. In this construction, two distinct trapdoors are used to find short bases. One trapdoor enables the real implementation to generate short bases for all lattices. The other trapdoor enables the simulator to generate short bases for all lattices. Moreover, the generating short bases are used to sample short vectors as signatures. Based on the hardness of the small integer solution (SIS) problem, the proposed scheme is proven to be strongly unforgeable against adaptive chosen-identity and adaptive chosen-message attacks without using random oracles. Compared with the existing strongly unforgeable identity-based signature schemes, our scheme has the advantages of full security and resistance to quantum computing attacks.

International Conference on Intelligent Networking and Collaborative Systems (INCoS)•Sep 1, 2013•1 citation

Adaptive-ID Secure Identity-Based Signature Scheme from Lattices in the Standard Model

Zecheng Wang, Xuemin Chen, Pingshui Wang

Identity-based signature (IBS) which is a paradigm built on public key cryptography has played a significant role in light-weight authentication. With the advent of the post quantum era, the lattice has become a main mathematical tool to construct quantum-immune cryptographic schemes. By utilizing an admissible hash function with compatible algorithms and lattice trapdoors as basic building blocks, we propose a new IBS scheme over lattices. The scheme is proved existentially unforgeable against adaptive identity attacks and chosen message attacks in the standard model under inhomogeneous short integer solution assumption via the generalized partitioning proof technique. Moreover, the scheme needs only logarithmic basic matrices as master public key while keeping the same private key size and signature size as those of other standard model lattice-based IBS schemes. This construction is the first adaptive-ID secure standard model IBS scheme over lattice with such space efficiency.

IEEE Access•Jan 1, 2017•6 citations
Abstract. We propose a variant of the “bonsai tree ” signature scheme, a lattice-based existentially unforgeable signature scheme in the standard model. Our construction offers the same efficiency as the “bonsai tree” scheme but supports the stronger notion of strong unforgeability. Strong unforgeability demands that the adversary is unable to produce a new message-signature pair (m, s), even if he or she is allowed to see a different signature s ′ for m. In particular, we provide the first treeless signature scheme that supports strong unforgeability for the post-quantum era in the standard model. Moreover, we show how to directly implement identity-based, and even hierarchical identity-based, signatures (IBS) in the same strong security model without random oracles. An additional advantage of this direct approach over the usual generic conversion of hierarchical identity-based encryption to IBS is that we can exploit the efficiency of ideal lattices without significantly harming security. We equip all constructions with strong security proofs based on mild worst-case assumptions on lattices and we also propose concrete security parameters.
Strongly unforgeable signature schemes provide a more stringent security guarantee than the standard existential unforgeability. It requires that not only forging a signature on a new message is hard, it is infeasible as well to produce a new signature on a message for which the adversary has seen valid signatures before. Strongly unforgeable signatures are useful both in practice and as a building block in many cryptographic constructions. This work investigates a generic transformation that compiles any existential-unforgeable scheme into a strongly unforgeable one, which was proposed by Teranishi et al. and was proven in the classical random-oracle model. Our main contribution is showing that the transformation also works against quantum adversaries in the quantum random-oracle model. We develop proof techniques such as adaptively programming a quantum random-oracle in a new setting, which could be of independent interest. Applying the transformation to an existential-unforgeable signature scheme due to Cash et al., which can be shown to be quantum-secure assuming certain lattice problems are hard for quantum computers, we get an efficient quantum-secure strongly unforgeable signature scheme in the quantum random-oracle model.
Hierarchical identity-based signature (HIBS), which plays an important role in large communities, is a generaliza-tion of identity-based signature (IBS). In this paper, we present a new HIBS scheme from lattices without ran-dom oracles. The new scheme is proven to be strongly unforgeable against selective identity attacks under the standard hardness assumption of the short integer so-lution (SIS) problem. Furthermore, the secret key size and the signature length of our scheme are both invariant and much shorter than those of the previous lattice-based HIBS schemes. To the best of our knowledge, our con-struction is the first short lattice-based HIBS scheme in the standard model.
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.
With the rapid development of electronic information technology, digital signature has become an indispensable part of our lives. Traditional public key certificate cryptosystems cannot overcome the limitations of certificate management. Identity-based cryptosystems can avoid the certificate management issues. The development of quantum computers has brought serious challenges to traditional cryptography. Post-quantum cryptography research is imperative. At present, almost all post-quantum identity-based signature (IBS) schemes are constructed using Gaussian sampling or trapdoor technologies. However, these two technologies have a great impact on computational efficiency. To overcome this problem, we construct an IBS scheme on lattices by employing Lyubashevsky’s signature scheme. Based on the shortest vector problem on lattices, our scheme does not use Gaussian sampling or trapdoor technologies. In the random oracle model, it is proved that our scheme is strongly unforgeable against adaptive chosen messages and identity attacks. The security level of our scheme is strongly unforgeable, which is a higher level than the existential unforgeability of other schemes. Compared with other efficient schemes, our scheme has advantages in computation complexity and security.
Inspired by Agrawal, Boneh and Boyen's identity-based encryption scheme, we proposed a post-quantum identity-based signature scheme from lattices. In this construction, two distinct trapdoors are used to find short bases. One trapdoor enables the real implementation to generate short bases for all lattices. The other trapdoor enables the simulator to generate short bases for all lattices. Moreover, the generating short bases are used to sample short vectors as signatures. Based on the hardness of the small integer solution (SIS) problem, the proposed scheme is proven to be strongly unforgeable against adaptive chosen-identity and adaptive chosen-message attacks without using random oracles. Compared with the existing strongly unforgeable identity-based signature schemes, our scheme has the advantages of full security and resistance to quantum computing attacks.
Identity-based signature (IBS) which is a paradigm built on public key cryptography has played a significant role in light-weight authentication. With the advent of the post quantum era, the lattice has become a main mathematical tool to construct quantum-immune cryptographic schemes. By utilizing an admissible hash function with compatible algorithms and lattice trapdoors as basic building blocks, we propose a new IBS scheme over lattices. The scheme is proved existentially unforgeable against adaptive identity attacks and chosen message attacks in the standard model under inhomogeneous short integer solution assumption via the generalized partitioning proof technique. Moreover, the scheme needs only logarithmic basic matrices as master public key while keeping the same private key size and signature size as those of other standard model lattice-based IBS schemes. This construction is the first adaptive-ID secure standard model IBS scheme over lattice with such space efficiency.