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

Sequential Half-Aggregation of Lattice-Based Signatures

Katharina Boudgoust, Akira Takahashi

Published Jan 1, 2024• 15 citations
Publisher

Abstract

With $$\textsf {Dilithium} $$ and $$\textsf {Falcon} $$ , NIST selected two lattice-based signature schemes during their post-quantum standardization project. Whereas $$\textsf {Dilithium} $$ follows the Fiat-Shamir with Aborts (Lyubashevsky, Asiacrypt’09) blueprint, $$\textsf {Falcon} $$ can be seen as an optimized version of the GPV-paradigm (Gentry et al., STOC’06). An important question now is whether those signatures allow additional features such as the aggregation of distinct signatures. One example are sequential aggregate signature ( $$\textsf{SAS}$$ ) schemes (Boneh et al., Eurocrypt’04) which allow a group of signers to sequentially combine signatures on distinct messages in a compressed manner. The present work first reviews the state of the art of (sequentially) aggregating lattice-based signatures, points out the insecurity of one of the existing $$\textsf {Falcon} $$ -based $$\textsf{SAS}$$ (Wang and Wu, PROVSEC’19), and proposes a fix for it. We then construct the first Fiat-Shamir with Aborts based $$\textsf{SAS}$$ by generalizing existing techniques from the discrete-log setting (Chen and Zhao, ESORICS’22) to the lattice framework. Going from the pre-quantum to the post-quantum world, however, does most often come with efficiency penalties. In our work, we also meet obstacles that seem inherent to lattice-based signatures, making the resulting scheme less efficient than what one would hope for. As a result, we only achieve quite small compression rates. We compare our construction with existing lattice-based $$\textsf{SAS}$$ which all follow the GPV-paradigm. The bottom line is that none of the schemes achieves a good compression rate so far.

DOI
10.1007/978-3-031-50594-2_14

Related papers

Two-Round n-out-of-n and Multi-Signatures and Trapdoor Commitment from Lattices

Ivan Damgård, Claudio Orlandi, Akira Takahashi +1 more

Although they have been studied for a long time, distributed signature protocols have garnered renewed interest in recent years in view of novel applications to topics like blockchains. Most recent works have focused on distributed versions of ECDSA or variants of Schnorr signatures; however, and in particular, little attention has been given to constructions based on post-quantum secure assumptions like the hardness of lattice problems. A few lattice-based threshold signature and multi-signature schemes have been proposed in the literature, but they either rely on hash-and-sign lattice signatures (which tend to be comparatively inefficient), use expensive generic transformations, or only come with incomplete security proofs. In this paper, we construct several lattice-based distributed signing protocols with low round complexity following the Fiat–Shamir with Aborts (FSwA) paradigm of Lyubashevsky (Asiacrypt 2009). Our protocols can be seen as distributed variants of the fast Dilithium-G signature scheme and the full security proof can be made assuming the hardness of module SIS and LWE problems. A key step to achieving security (unexplained in some earlier papers) is to prevent the leakage that can occur when parties abort after their first message—which can inevitably happen in the Fiat–Shamir with Aborts setting. We manage to do so using homomorphic commitments. Exploiting the similarities between FSwA and Schnorr-style signatures, our approach makes the most of observations from recent advancements in the discrete log setting, such as Drijvers et al.’s seminal work on two-round multi-signatures (S&P 2019). In particular, we observe that the use of commitment not only resolves the subtle issue with aborts, but also makes it possible to realize secure two-round n -out-of- n distributed signing and multi-signature in the plain public key model , by equipping the commitment with a trapdoor feature. The construction of suitable trapdoor commitment from lattices is a side contribution of this paper.

Journal of Cryptology•Apr 1, 2022•42 citations

Two-Round n-out-of-n and Multi-signatures and Trapdoor Commitment from Lattices

Ivan Damgård, Claudio Orlandi, Akira Takahashi +1 more

Although they have been studied for a long time, distributed signature protocols have garnered renewed interest in recent years in view of novel applications to topics like blockchains. Most recent works have focused on distributed versions of ECDSA or variants of Schnorr signatures, however, and in particular, little attention has been given to constructions based on post-quantum secure assumptions like the hardness of lattice problems. A few lattice-based threshold signature and multi-signatureschemes have been proposed in the literature, but they either rely on hash-and-sign lattice signatures (which tend to be comparatively inefficient), use expensive generic transformations, or only come with incomplete security proofs.In this paper, we construct several lattice-based distributed signing protocols with low round complexity followingthe Fiat–Shamir with Aborts (FSwA) paradigm of Lyubashevsky (Asiacrypt 2009). Our protocols can be seen as distributed variants of the fast Dilithium-G signature scheme and the full security proof can be made assuming the hardness of module SIS and LWE problems. A key step to achieving security (unexplained in some earlier papers) is to prevent the leakage that can occur when parties abort after their first message—which can inevitably happen in the Fiat–Shamir with Aborts setting. We manage to do so using homomorphic commitments.Exploiting the similarities between FSwA and Schnorr-style signatures, our approach makes the most of observations from recent advancements in the discrete log setting, such as Drijvers et al.’s seminal work on two-round multi-signatures (S&P 2019). In particular, we observe that the use of commitment not only resolves the subtle issue with aborts, but also makes it possible to realize secure two-round n-out-of-n distributed signing and multi-signature in the plain public key model, by equipping the commitment with a trapdoor feature. The construction of suitable trapdoor commitment from lattices is a side contribution of this paper.

Lecture notes in computer science•Jan 1, 2021•54 citations

Towards a Lattice-Based Non-interactive Aggregate Signature Scheme Following the Fiat-Shamir with Aborts Paradigm

Mingmei Zheng, Masahiro Mambo, Junzuo Lai +1 more

Lecture notes in computer science•Jan 1, 2026•0 citations

Tight Lattice-Based Signatures without Trapdoors from Search LWE

Nico Döttling, Rutchathon Chairattana-Apirom, Julian Loss +2 more

The study of digital signatures with tight reductions has attracted considerable attention over the past two decades, as such schemes inherit essentially the same quantitative hardness as the underlying computational problem. In the context of lattice-based cryptography, the GPV approach (Gentry, Peikert, and Vaikuntanathan, STOC ’08) admits a simple tight reduction from the SIS problem, but relies on preimage sampling via trapdoors, which often leads to complex and brittle implementations. By contrast, tight proofs for trapdoor-free constructions, following the Fiat–Shamir paradigm, necessarily rely on decisional assumptions, most notably the decisional LWE assumption. From the perspective of concrete security, however, reliance on a search assumption is preferable, as known search-to-decision reductions for LWE provide only weak quantitative guarantees. \ind This paper presents the first efficient lattice-based signature scheme with a tight reduction to a search assumption (namely, the hardness of the search LWE problem) that does not require any trapdoor in the scheme itself (but merely uses, instead, a trapdoor in the proof). Our construction follows the Fiat-Shamir paradigm and can be viewed as a lattice analogue of Chevallier–Mames signatures (CRYPTO ’05). Establishing security in the lattice setting, however, requires overcoming significant technical obstacles: in particular, our proof develops several new techniques to cope with the inherently weak soundness guarantees of lattice-based interactive proofs.

•Jun 23, 2026•0 citations

An Investigation of Lattice-Based Digital Signatures and Their Aggregate Variants for Post-Quantum Security

Yiming Tong

With quantum computing now widely treated as a credible adversary to conventional public-key assumptions—most notably discrete logarithms and integer factorization—post-quantum cryptography has moved from a speculative research topic to an active engineering agenda. Within that broader landscape, lattice-based cryptography is routinely singled out as the leading candidate for next-generation digital signatures, largely because its security can be reduced to well-studied lattice problems believed resistant to quantum attacks. Aggregate signatures compress multiple individual signatures into a single compact object, translating into improved batch-verification throughput in settings such as blockchain and IoT. Against this backdrop, the present investigation offers a detailed analysis of lattice-based aggregate signature constructions. Core lattice notions are reviewed alongside security models, followed by an examination of two aggregation paradigms: unordered and ordered. Representative schemes are analyzed with respect to their construction logic and structural bottlenecks. A cross-scheme comparison is then used to motivate future research directions. By pulling together recent progress while isolating persistent obstacles, this investigation characterizes an ongoing shift from feasibility-oriented prototypes toward deployment-minded designs, offering a focused reference for standardization efforts targeting post-quantum-secure aggregate signatures.

Applied and Computational Engineering•Jun 23, 2026•0 citations

CURRENT PARADIGMS FOR CONSTRUCTION OF LATTICE-BASED DIGITAL SIGNATURE SCHEMES

QApp, Леевик Антон Георгиевич, Ekaterina Sergeevna Malygina +4 more

With the advent of quantum computing, research into post-quantum cryptography has gained significant attention. This is a novel branch of cryptography that utilizes algorithms and protocols designed to withstand attacks from quantum computers. Lattice theory represents a promising area within post-quantum cryptographic research. Two early examples of lattice-based cryptosystems are the GGH and NTRU schemes. These schemes are based on the challenge of finding the closest vector in a lattice and differ primarily in the type of lattice used. The NTRUSign protocol was developed by combining the strengths of both schemes. In 2008, another approach to lattice signatures was introduced by a group of authors. It is based on the hash-and-sign paradigm, in which a signature for a message is generated using a trapdoor. A year later, V. Lyubashevsky proposed another method for constructing lattice-based signatures that utilizes the Fiat — Shamir transform. However, due to the nature of the underlying lattice structure, the algorithm for signature generation produces a correct signature only with a certain probability. This is due to the use of a rejection sampling for security purposes. This paper presents an overview of existing lattice-based signature construction approaches and cryptographic schemes that are based on these approaches. A comparative analysis was conducted on these schemes, identifying the advantages and disadvantages of each method. Based on the results, optimal conditions for the application of each approach have been determined.

PRIKLADNAYa DISKRETNAYa MATEMATIKA•Jan 1, 2025•0 citations
With Dilithium\textsf {Dilithium} Dilithium and Falcon\textsf {Falcon} Falcon , NIST selected two lattice-based signature schemes during their post-quantum standardization project. Whereas Dilithium\textsf {Dilithium} Dilithium follows the Fiat-Shamir with Aborts (Lyubashevsky, Asiacrypt’09) blueprint, Falcon\textsf {Falcon} Falcon can be seen as an optimized version of the GPV-paradigm (Gentry et al., STOC’06). An important question now is whether those signatures allow additional features such as the aggregation of distinct signatures. One example are sequential aggregate signature ( SAS\textsf{SAS}SAS ) schemes (Boneh et al., Eurocrypt’04) which allow a group of signers to sequentially combine signatures on distinct messages in a compressed manner. The present work first reviews the state of the art of (sequentially) aggregating lattice-based signatures, points out the insecurity of one of the existing Falcon\textsf {Falcon} Falcon -based SAS\textsf{SAS}SAS (Wang and Wu, PROVSEC’19), and proposes a fix for it. We then construct the first Fiat-Shamir with Aborts based SAS\textsf{SAS}SAS by generalizing existing techniques from the discrete-log setting (Chen and Zhao, ESORICS’22) to the lattice framework. Going from the pre-quantum to the post-quantum world, however, does most often come with efficiency penalties. In our work, we also meet obstacles that seem inherent to lattice-based signatures, making the resulting scheme less efficient than what one would hope for. As a result, we only achieve quite small compression rates. We compare our construction with existing lattice-based SAS\textsf{SAS}SAS which all follow the GPV-paradigm. The bottom line is that none of the schemes achieves a good compression rate so far.
Although they have been studied for a long time, distributed signature protocols have garnered renewed interest in recent years in view of novel applications to topics like blockchains. Most recent works have focused on distributed versions of ECDSA or variants of Schnorr signatures; however, and in particular, little attention has been given to constructions based on post-quantum secure assumptions like the hardness of lattice problems. A few lattice-based threshold signature and multi-signature schemes have been proposed in the literature, but they either rely on hash-and-sign lattice signatures (which tend to be comparatively inefficient), use expensive generic transformations, or only come with incomplete security proofs. In this paper, we construct several lattice-based distributed signing protocols with low round complexity following the Fiat–Shamir with Aborts (FSwA) paradigm of Lyubashevsky (Asiacrypt 2009). Our protocols can be seen as distributed variants of the fast Dilithium-G signature scheme and the full security proof can be made assuming the hardness of module SIS and LWE problems. A key step to achieving security (unexplained in some earlier papers) is to prevent the leakage that can occur when parties abort after their first message—which can inevitably happen in the Fiat–Shamir with Aborts setting. We manage to do so using homomorphic commitments. Exploiting the similarities between FSwA and Schnorr-style signatures, our approach makes the most of observations from recent advancements in the discrete log setting, such as Drijvers et al.’s seminal work on two-round multi-signatures (S&P 2019). In particular, we observe that the use of commitment not only resolves the subtle issue with aborts, but also makes it possible to realize secure two-round n -out-of- n distributed signing and multi-signature in the plain public key model , by equipping the commitment with a trapdoor feature. The construction of suitable trapdoor commitment from lattices is a side contribution of this paper.
Although they have been studied for a long time, distributed signature protocols have garnered renewed interest in recent years in view of novel applications to topics like blockchains. Most recent works have focused on distributed versions of ECDSA or variants of Schnorr signatures, however, and in particular, little attention has been given to constructions based on post-quantum secure assumptions like the hardness of lattice problems. A few lattice-based threshold signature and multi-signatureschemes have been proposed in the literature, but they either rely on hash-and-sign lattice signatures (which tend to be comparatively inefficient), use expensive generic transformations, or only come with incomplete security proofs.In this paper, we construct several lattice-based distributed signing protocols with low round complexity followingthe Fiat–Shamir with Aborts (FSwA) paradigm of Lyubashevsky (Asiacrypt 2009). Our protocols can be seen as distributed variants of the fast Dilithium-G signature scheme and the full security proof can be made assuming the hardness of module SIS and LWE problems. A key step to achieving security (unexplained in some earlier papers) is to prevent the leakage that can occur when parties abort after their first message—which can inevitably happen in the Fiat–Shamir with Aborts setting. We manage to do so using homomorphic commitments.Exploiting the similarities between FSwA and Schnorr-style signatures, our approach makes the most of observations from recent advancements in the discrete log setting, such as Drijvers et al.’s seminal work on two-round multi-signatures (S&P 2019). In particular, we observe that the use of commitment not only resolves the subtle issue with aborts, but also makes it possible to realize secure two-round n-out-of-n distributed signing and multi-signature in the plain public key model, by equipping the commitment with a trapdoor feature. The construction of suitable trapdoor commitment from lattices is a side contribution of this paper.
The study of digital signatures with tight reductions has attracted considerable attention over the past two decades, as such schemes inherit essentially the same quantitative hardness as the underlying computational problem. In the context of lattice-based cryptography, the GPV approach (Gentry, Peikert, and Vaikuntanathan, STOC ’08) admits a simple tight reduction from the SIS problem, but relies on preimage sampling via trapdoors, which often leads to complex and brittle implementations. By contrast, tight proofs for trapdoor-free constructions, following the Fiat–Shamir paradigm, necessarily rely on decisional assumptions, most notably the decisional LWE assumption. From the perspective of concrete security, however, reliance on a search assumption is preferable, as known search-to-decision reductions for LWE provide only weak quantitative guarantees. \ind This paper presents the first efficient lattice-based signature scheme with a tight reduction to a search assumption (namely, the hardness of the search LWE problem) that does not require any trapdoor in the scheme itself (but merely uses, instead, a trapdoor in the proof). Our construction follows the Fiat-Shamir paradigm and can be viewed as a lattice analogue of Chevallier–Mames signatures (CRYPTO ’05). Establishing security in the lattice setting, however, requires overcoming significant technical obstacles: in particular, our proof develops several new techniques to cope with the inherently weak soundness guarantees of lattice-based interactive proofs.
With quantum computing now widely treated as a credible adversary to conventional public-key assumptions—most notably discrete logarithms and integer factorization—post-quantum cryptography has moved from a speculative research topic to an active engineering agenda. Within that broader landscape, lattice-based cryptography is routinely singled out as the leading candidate for next-generation digital signatures, largely because its security can be reduced to well-studied lattice problems believed resistant to quantum attacks. Aggregate signatures compress multiple individual signatures into a single compact object, translating into improved batch-verification throughput in settings such as blockchain and IoT. Against this backdrop, the present investigation offers a detailed analysis of lattice-based aggregate signature constructions. Core lattice notions are reviewed alongside security models, followed by an examination of two aggregation paradigms: unordered and ordered. Representative schemes are analyzed with respect to their construction logic and structural bottlenecks. A cross-scheme comparison is then used to motivate future research directions. By pulling together recent progress while isolating persistent obstacles, this investigation characterizes an ongoing shift from feasibility-oriented prototypes toward deployment-minded designs, offering a focused reference for standardization efforts targeting post-quantum-secure aggregate signatures.
With the advent of quantum computing, research into post-quantum cryptography has gained significant attention. This is a novel branch of cryptography that utilizes algorithms and protocols designed to withstand attacks from quantum computers. Lattice theory represents a promising area within post-quantum cryptographic research. Two early examples of lattice-based cryptosystems are the GGH and NTRU schemes. These schemes are based on the challenge of finding the closest vector in a lattice and differ primarily in the type of lattice used. The NTRUSign protocol was developed by combining the strengths of both schemes. In 2008, another approach to lattice signatures was introduced by a group of authors. It is based on the hash-and-sign paradigm, in which a signature for a message is generated using a trapdoor. A year later, V. Lyubashevsky proposed another method for constructing lattice-based signatures that utilizes the Fiat — Shamir transform. However, due to the nature of the underlying lattice structure, the algorithm for signature generation produces a correct signature only with a certain probability. This is due to the use of a rejection sampling for security purposes. This paper presents an overview of existing lattice-based signature construction approaches and cryptographic schemes that are based on these approaches. A comparative analysis was conducted on these schemes, identifying the advantages and disadvantages of each method. Based on the results, optimal conditions for the application of each approach have been determined.