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

Lecture notes in computer science

Improvement and Efficient Implementation of a Lattice-Based Signature Scheme

Rachid El Bansarkhani, Johannes A Buchmann

Published Jan 1, 2014• 60 citations
Publisher
DOI
10.1007/978-3-662-43414-7_3

Related papers

Improving Bitcoin’s Post-Quantum Transaction Efficiency With a Novel Lattice-Based Aggregate Signature Scheme Based on CRYSTALS-Dilithium and a STARK Protocol

Yunjia Quan

This paper proposes a novel lattice-based aggregate signature (LAS) scheme that bring post-quantum security to the Bitcoin system without sacrificing its transaction efficiency. Bitcoin currently employs Elliptic Curve Digital Signature Algorithm (ECDSA), which is insecure against the emerging quantum technology, so post-quantum signature schemes like the proposed LAS will become necessary in the near future. However, most of the post-quantum signatures schemes have large signature sizes which decrease Bitcoin’s efficiency while our proposed scheme does not have this negative side effect. Our LAS scheme is based on CRYSTALS-Dilithium and a zero-knowledge Scalable Transparent Arguments of Knowledge (STARK) protocol. CRYSTALS-Dilithium is the most prominent algorithm chosen by the National Institute of Standards and Technology (NIST), yet it still has an adverse limitation: it would cause Bitcoin’s transaction efficiency to fall by 17 times due to its relatively large signature size. On the other hand, the proposed LAS scheme takes full advantage of signature aggregation using the STARK protocol and Dilithium’s easy and fast implementation, thus generating signatures with post-quantum security and small signature sizes which are critical to transaction efficiency. Our proofs convey the correctness, compactness, and post-quantum security of our construction in the quantum random oracle model, and our implementation conveyed that the proposed scheme would only decrease Bitcoin’s transaction efficiency by 3 times, a significant improvement from using Dilithium and other lattice-based aggregate signature schemes. Our proposed scheme has many advantages over the existing schemes and may become very valuable to Bitcoin.

IEEE Access•Jan 1, 2022•19 citations

Development of a lattice based blind signature scheme

Frank Nauheimer

•Jan 1, 2007•1 citation

An Efficient Lattice-Based Signature Scheme with Provably Secure Instantiation

Sedat Akleylek, Nina Bindel, Johannes A Buchmann +2 more

Lecture notes in computer science•Jan 1, 2016•71 citations

TESLA: Tightly-Secure Efficient Signatures from Standard Lattices.

Erdem Alkım, Nina Bindel, Johannes A Buchmann +2 more

Generally, lattice-based cryptographic primitives offer good performance and allow for strong security reductions.However, the most efficient current lattice-based signature schemes sacrifice (part of its) security to achieve good performance: first, security is based on ideal lattice problems, that might not be as hard as standard lattice problems.Secondly, the security reductions of the most efficient schemes are non-tight; hence, their choices of parameters offer security merely heuristically.Moreover, lattice-based signatures are instantiated for classical adversaries, although they are based on presumably quantum hard problems.Yet, it is not known how such schemes perform in a post-quantum world.We bridge this gap by proving the lattice-based signature scheme TESLA to be tightly secure based on the learning with errors problem over standard lattices in the random oracle model.As such, we improve the security of the original proposal by Bai and Galbraith (CT-RSA'14) twofold; we tighten the security reduction and we minimize the underlying security assumptions.Remarkably, by enhancing the security we can improve TESLA's performance by a factor of two.Furthermore, we are first to propose parameters providing a security of 128 bits against both classical and quantum adversaries for a lattice-based signature scheme.Our implementation of TESLA competes well with state-of-the-art lattice-based signatures and SPHINCS (EUROCRYPT'15), the only signature scheme instantiated with quantumhard parameters thus far.

•Jul 29, 2015•23 citations

Research on A Lattice-Based Fuzzy Signature and Bimodal Gaussian

Jinxin Huang, Jie Cai, Fenghe Wang +1 more

Fuzzy signatures differ from standard signature schemes in that they use noisy strings as keys, thereby eliminating the need for user-specific auxiliary data. With the advent of quantum computing, lattice-based digital signatures are considered potential candidates for resisting quantum attacks. In this work, we revisited the lattice-based fuzzy signature scheme proposed by Zhenget al. and demonstrated how the scheme can be implemented more efficiently and securely. In our new signature scheme, our contributions are as follows: The utilization of bimodal Gaussian sampling reduces the number of aborting terminations while simultaneously decreasing the signature size. By eliminating the T matrix from the verification equation, we improve verification efficiency. Additionally, in response to the linear sketch proposed by the authors, we provide a proof of the collision resistance of the mappingh, which further enhances the correctness of the scheme.

IEEE Access•Jan 1, 2025•0 citations

Lattice-based undeniable signature scheme

Swati Rawal, Sahadeo Padhye, Debiao He

Annals of Telecommunications•Jan 10, 2022•6 citations
This paper proposes a novel lattice-based aggregate signature (LAS) scheme that bring post-quantum security to the Bitcoin system without sacrificing its transaction efficiency. Bitcoin currently employs Elliptic Curve Digital Signature Algorithm (ECDSA), which is insecure against the emerging quantum technology, so post-quantum signature schemes like the proposed LAS will become necessary in the near future. However, most of the post-quantum signatures schemes have large signature sizes which decrease Bitcoin’s efficiency while our proposed scheme does not have this negative side effect. Our LAS scheme is based on CRYSTALS-Dilithium and a zero-knowledge Scalable Transparent Arguments of Knowledge (STARK) protocol. CRYSTALS-Dilithium is the most prominent algorithm chosen by the National Institute of Standards and Technology (NIST), yet it still has an adverse limitation: it would cause Bitcoin’s transaction efficiency to fall by 17 times due to its relatively large signature size. On the other hand, the proposed LAS scheme takes full advantage of signature aggregation using the STARK protocol and Dilithium’s easy and fast implementation, thus generating signatures with post-quantum security and small signature sizes which are critical to transaction efficiency. Our proofs convey the correctness, compactness, and post-quantum security of our construction in the quantum random oracle model, and our implementation conveyed that the proposed scheme would only decrease Bitcoin’s transaction efficiency by 3 times, a significant improvement from using Dilithium and other lattice-based aggregate signature schemes. Our proposed scheme has many advantages over the existing schemes and may become very valuable to Bitcoin.
Generally, lattice-based cryptographic primitives offer good performance and allow for strong security reductions.However, the most efficient current lattice-based signature schemes sacrifice (part of its) security to achieve good performance: first, security is based on ideal lattice problems, that might not be as hard as standard lattice problems.Secondly, the security reductions of the most efficient schemes are non-tight; hence, their choices of parameters offer security merely heuristically.Moreover, lattice-based signatures are instantiated for classical adversaries, although they are based on presumably quantum hard problems.Yet, it is not known how such schemes perform in a post-quantum world.We bridge this gap by proving the lattice-based signature scheme TESLA to be tightly secure based on the learning with errors problem over standard lattices in the random oracle model.As such, we improve the security of the original proposal by Bai and Galbraith (CT-RSA'14) twofold; we tighten the security reduction and we minimize the underlying security assumptions.Remarkably, by enhancing the security we can improve TESLA's performance by a factor of two.Furthermore, we are first to propose parameters providing a security of 128 bits against both classical and quantum adversaries for a lattice-based signature scheme.Our implementation of TESLA competes well with state-of-the-art lattice-based signatures and SPHINCS (EUROCRYPT'15), the only signature scheme instantiated with quantumhard parameters thus far.
Fuzzy signatures differ from standard signature schemes in that they use noisy strings as keys, thereby eliminating the need for user-specific auxiliary data. With the advent of quantum computing, lattice-based digital signatures are considered potential candidates for resisting quantum attacks. In this work, we revisited the lattice-based fuzzy signature scheme proposed by Zhenget al. and demonstrated how the scheme can be implemented more efficiently and securely. In our new signature scheme, our contributions are as follows: The utilization of bimodal Gaussian sampling reduces the number of aborting terminations while simultaneously decreasing the signature size. By eliminating the T matrix from the verification equation, we improve verification efficiency. Additionally, in response to the linear sketch proposed by the authors, we provide a proof of the collision resistance of the mappingh, which further enhances the correctness of the scheme.