kth.sePublications
Change search
CiteExportLink to record
Permanent link

Direct link
Cite
Citation style
  • apa
  • ieee
  • modern-language-association-8th-edition
  • vancouver
  • Other style
More styles
Language
  • de-DE
  • en-GB
  • en-US
  • fi-FI
  • nn-NO
  • nn-NB
  • sv-SE
  • Other locale
More languages
Output format
  • html
  • text
  • asciidoc
  • rtf
Compact Lattice Signatures via Iterative Rejection Sampling
KTH, School of Engineering Sciences (SCI), Mathematics (Dept.), Algebra, Combinatorics and Topology. Swedish NCSA, Swedish Armed Forces, Stockholm, Sweden.ORCID iD: 0000-0002-3724-2914
2025 (English)In: Advances in Cryptology – CRYPTO 2025: 45th Annual International Cryptology Conference, Santa Barbara, CA, USA, August 17–21, 2025, Proceedings, Part I, Springer Nature , 2025, p. 514-547Conference paper, Published paper (Refereed)
Abstract [en]

One of the primary approaches for constructing lattice-based signature schemes is through the “Fiat-Shamir with aborts” methodology. Schemes constructed using this approach may abort and restart during signing, corresponding to rejection sampling produced signatures in order to ensure that they follow a distribution that is independent of the secret key. This rejection sampling is only feasible when the output distribution is sufficiently wide, limiting how compact this type of signature schemes can be. In this work, we develop a new method to construct lattice signatures with the “Fiat-Shamir with aborts” approach. By constructing signatures in a way that is influenced by the rejection condition, we can significantly lower the rejection probability. This allows our scheme to use an iterative rejection sampling to target narrower output distributions than previous methods, resulting in much more compact signatures. In the most compact variant of our new signature scheme, the combined size of a signature and a verification key is less than half of that for ML-DSA and comparable to that of compact hash-and-sign lattice signature schemes, such as Falcon. Alternatively, by targeting a somewhat wider distribution, the rejection condition of the scheme can be securely ignored. This non-aborting variant of our scheme still retains a notable size advantage over previous lattice-based Fiat-Shamir schemes.

Place, publisher, year, edition, pages
Springer Nature , 2025. p. 514-547
Series
Lecture Notes in Computer Science, ISSN 0302-9743, E-ISSN 1611-3349
National Category
Electrical Engineering, Electronic Engineering, Information Engineering
Identifiers
URN: urn:nbn:se:kth:diva-370315DOI: 10.1007/978-3-032-01855-7_17Scopus ID: 2-s2.0-105014140551OAI: oai:DiVA.org:kth-370315DiVA, id: diva2:2000627
Conference
45th Annual International Cryptology Conference, CRYPTO 2025, Santa Barbara, United States of America, Aug 17 2025 - Aug 21 2025
Note

Part of ISBN 9783032018540

QC 20250924

Not duplicate with DiVA 1957198

Available from: 2025-09-24 Created: 2025-09-24 Last updated: 2025-09-24Bibliographically approved

Open Access in DiVA

No full text in DiVA

Other links

Publisher's full textScopus

Authority records

Gärtner, Joel

Search in DiVA

By author/editor
Gärtner, Joel
By organisation
Algebra, Combinatorics and Topology
Electrical Engineering, Electronic Engineering, Information Engineering

Search outside of DiVA

GoogleGoogle Scholar

doi
urn-nbn

Altmetric score

doi
urn-nbn
Total: 23 hits
CiteExportLink to record
Permanent link

Direct link
Cite
Citation style
  • apa
  • ieee
  • modern-language-association-8th-edition
  • vancouver
  • Other style
More styles
Language
  • de-DE
  • en-GB
  • en-US
  • fi-FI
  • nn-NO
  • nn-NB
  • sv-SE
  • Other locale
More languages
Output format
  • html
  • text
  • asciidoc
  • rtf