Paper 2024/2052
Improved Rejection Sampling for Compact Lattice Signatures
, Royal Institute of TechnologyAbstract
One of the primary approaches used to construct lattice-based signature schemes is through the “Fiat-Shamir with aborts” methodology. Such a scheme may abort and restart during signing which corresponds to rejection sampling produced signatures 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 signatures influenced by the rejection condition. This allows our rejection sampling to target significantly narrower output distributions than previous approaches, allowing much more compact signatures. The combined size of a signature and a verification key for the resulting scheme is less than half of that for ML-DSA and comparable to that of compact hash-and-sign lattice signature schemes, such as Falcon.
Metadata
- Available format(s)
-
PDF
- Category
- Public-key cryptography
- Publication info
- Preprint.
- Keywords
- Lattice-based cryptographySignaturesFiat-ShamirRejection sampling
- Contact author(s)
- jgartner @ kth se
- History
- 2024-12-27: revised
- 2024-12-19: received
- See all versions
- Short URL
- https://ia.cr/2024/2052
- License
-
CC BY
BibTeX
@misc{cryptoeprint:2024/2052,
author = {Joel Gärtner},
title = {Improved Rejection Sampling for Compact Lattice Signatures},
howpublished = {Cryptology {ePrint} Archive, Paper 2024/2052},
year = {2024},
url = {https://eprint.iacr.org/2024/2052}
}
