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• 17 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•48 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•59 citations

On the Design and Security of Post-Quantum Aggregate Signatures

Edoardo Signorini

Digital signatures are pivotal for ensuring the authenticity and integrity of digital communications, serving as the backbone of numerous cryptographic protocols and systems.However, the physical constraints of network communication pose challenges in the transmission of large number of signatures, including digital certificates in Public Key Infrastructures, routing protocols, and decentralized systems.The advent of quantum computing has heightened these challenges, given that post-quantum cryptographic schemes, like those proposed under NIST's standardization project, generally result in larger signature sizes.Aggregate signatures represent a powerful cryptographic tool to reduce communication costs in protocols that require the verification of multiple signatures.In fact, this method can reduce the total amount of transmitted data by allowing multiple signers to combine their individual signatures on separate messages into a single aggregate signature.Since general forms of aggregations are difficult to achieve in practice, weaker variants can be considered.For instance, in a Sequential Aggregate Signature (SAS) scheme, signatures are combined in a specific sequence, allowing each subsequent signer to append their signature to an already aggregated one.Although sequential aggregation is more restrictive, it often suits contexts where order or hierarchy are inherent, thus continuing to be beneficial in practical applications.This thesis contributes primarily by exploring aggregate signatures under post-quantum assumptions, particularly focusing on signature schemes that are not based on structured lattices.Our research delves into two main classes of digital signatures in the postquantum setting.Firstly, we explore the generalization of SAS schemes to Hashand-Sign signatures based on generic trapdoor functions.The simple structure of signatures within this paradigm appears to make them ideal candidates for sequential aggregation.However, early SAS proposals required the use of trapdoor permutation (e.g., RSA), while post-quantum trapdoor functions known so-far are not injective.Direct attempts at generalizing permutation-based schemes have been proposed, but they either lack formal security or require additional properties on the trapdoor function, which are typically not available for multivariate or code-based functions.We provide a comprehensive analysis of existing models, discuss their limitations, and prove how direct extensions of original SAS iii From the beginning, I perceived my PhD as a solitary journey, a constant juggling act between industry and academia.For that, I've had my fair share of moments wondering if I was in the right place at the right time.But looking back, I realize it's the people who've been there -sometimes pushing, sometimes supporting, always believing -that have made this journey not just possible, but worthwhile.First and foremost, I wish to express my deepest thanks to Guglielmo Morgari.It all started with an unexpected (and perhaps annoying) call, and you took a chance on me.Your unwavering dedication and endless support have been invaluable throughout this process.Thank you for constantly pushing me to reach higher, for making me a better communicator, and somehow convincing me that I'm now friends with the lab's oscilloscope.Perhaps most importantly, I want to thank you for imparting me a small piece of the immeasurable faith you've always placed in me.These acknowledgments naturally extend to Telsy, the company to which I owe this unique opportunity.I'm still amazed and grateful to be part of a team that's not afraid to bet on the value of research.A special thank you goes to Fabrizio Vacca and the colleagues who believed in this project and made it possible.I am grateful to my academic supervisor, Danilo Bazzanella, and the entire CrypTo group at Politecnico.You have provided me with the precious opportunity to work closely in an environment that is both stimulating and welcoming.Although my primary workspace has never been the department, and my "office" there remains more of a theoretical concept than a physical location I can reliably find, each visit has contributed to making me feel part of a broader research community.Among the group, my sincere thanks to Antonio Di Scala and Carlo Sanna for guiding me through my first academic works with patience and wisdom.I extend my gratitude to Simone Dutto and Nadir Murru for their meticulous review of my work and the numerous insightful suggestions they provided.I am deeply indebted to my closest co-authors and colleagues.To Alessio Meneghetti, thank you for being the first who helped me find a thread in a tangle of

•Oct 14, 2024•0 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
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.
Digital signatures are pivotal for ensuring the authenticity and integrity of digital communications, serving as the backbone of numerous cryptographic protocols and systems.However, the physical constraints of network communication pose challenges in the transmission of large number of signatures, including digital certificates in Public Key Infrastructures, routing protocols, and decentralized systems.The advent of quantum computing has heightened these challenges, given that post-quantum cryptographic schemes, like those proposed under NIST's standardization project, generally result in larger signature sizes.Aggregate signatures represent a powerful cryptographic tool to reduce communication costs in protocols that require the verification of multiple signatures.In fact, this method can reduce the total amount of transmitted data by allowing multiple signers to combine their individual signatures on separate messages into a single aggregate signature.Since general forms of aggregations are difficult to achieve in practice, weaker variants can be considered.For instance, in a Sequential Aggregate Signature (SAS) scheme, signatures are combined in a specific sequence, allowing each subsequent signer to append their signature to an already aggregated one.Although sequential aggregation is more restrictive, it often suits contexts where order or hierarchy are inherent, thus continuing to be beneficial in practical applications.This thesis contributes primarily by exploring aggregate signatures under post-quantum assumptions, particularly focusing on signature schemes that are not based on structured lattices.Our research delves into two main classes of digital signatures in the postquantum setting.Firstly, we explore the generalization of SAS schemes to Hashand-Sign signatures based on generic trapdoor functions.The simple structure of signatures within this paradigm appears to make them ideal candidates for sequential aggregation.However, early SAS proposals required the use of trapdoor permutation (e.g., RSA), while post-quantum trapdoor functions known so-far are not injective.Direct attempts at generalizing permutation-based schemes have been proposed, but they either lack formal security or require additional properties on the trapdoor function, which are typically not available for multivariate or code-based functions.We provide a comprehensive analysis of existing models, discuss their limitations, and prove how direct extensions of original SAS iii From the beginning, I perceived my PhD as a solitary journey, a constant juggling act between industry and academia.For that, I've had my fair share of moments wondering if I was in the right place at the right time.But looking back, I realize it's the people who've been there -sometimes pushing, sometimes supporting, always believing -that have made this journey not just possible, but worthwhile.First and foremost, I wish to express my deepest thanks to Guglielmo Morgari.It all started with an unexpected (and perhaps annoying) call, and you took a chance on me.Your unwavering dedication and endless support have been invaluable throughout this process.Thank you for constantly pushing me to reach higher, for making me a better communicator, and somehow convincing me that I'm now friends with the lab's oscilloscope.Perhaps most importantly, I want to thank you for imparting me a small piece of the immeasurable faith you've always placed in me.These acknowledgments naturally extend to Telsy, the company to which I owe this unique opportunity.I'm still amazed and grateful to be part of a team that's not afraid to bet on the value of research.A special thank you goes to Fabrizio Vacca and the colleagues who believed in this project and made it possible.I am grateful to my academic supervisor, Danilo Bazzanella, and the entire CrypTo group at Politecnico.You have provided me with the precious opportunity to work closely in an environment that is both stimulating and welcoming.Although my primary workspace has never been the department, and my "office" there remains more of a theoretical concept than a physical location I can reliably find, each visit has contributed to making me feel part of a broader research community.Among the group, my sincere thanks to Antonio Di Scala and Carlo Sanna for guiding me through my first academic works with patience and wisdom.I extend my gratitude to Simone Dutto and Nadir Murru for their meticulous review of my work and the numerous insightful suggestions they provided.I am deeply indebted to my closest co-authors and colleagues.To Alessio Meneghetti, thank you for being the first who helped me find a thread in a tangle of
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.