Paper 2024/1952

Worst-Case Lattice Sampler with Truncated Gadgets and Applications

Corentin Jeudy, Orange (France)
Olivier Sanders, Orange (France)
Abstract

Gadget-based samplers have proven to be a key component of several cryptographic primitives, in particular in the area of privacy-preserving mechanisms. Most constructions today follow the approach introduced by Micciancio and Peikert (MP) yielding preimages whose dimension linearly grows with that of the gadget. To improve performance, some papers have proposed to truncate the gadget but at the cost of an important feature of the MP sampler, namely the ability to invert arbitrary syndromes. Technically speaking, they replace the worst-case MP sampler by an average-case sampler that can only be used in specific contexts. Far from being a mere theoretical restriction, it prevents the main applications of gadget-based samplers from using truncated variants and thus from benefiting from the associated performance gains. In this paper, we solve this problem by describing a worst-case sampler that still works with truncated gadgets. Its main strength is that it retains the main characteristics of the MP sampler while providing flexibility in the choice of the truncation parameter. As a consequence, it can be used as a plug-in replacement for all applications relying on the MP sampler so far, leading to performance improvements up to 30% as illustrated by several examples in this paper. Our sampler is supported by a thorough security analysis that addresses the hurdles met by previous works and its practicality is demonstrated by a concrete implementation.

Metadata
Available format(s)
PDF
Category
Public-key cryptography
Publication info
Preprint.
Keywords
Lattice-Based CryptographyTrapdoorsPreimage SamplingAdvanced Signatures
Contact author(s)
corentin jeudy @ orange com
olivier sanders @ orange com
History
2025-02-07: revised
2024-12-02: received
See all versions
Short URL
https://ia.cr/2024/1952
License
Creative Commons Attribution
CC BY

BibTeX

@misc{cryptoeprint:2024/1952,
      author = {Corentin Jeudy and Olivier Sanders},
      title = {Worst-Case Lattice Sampler with Truncated Gadgets and Applications},
      howpublished = {Cryptology {ePrint} Archive, Paper 2024/1952},
      year = {2024},
      url = {https://eprint.iacr.org/2024/1952}
}
Note: In order to protect the privacy of readers, eprint.iacr.org does not use cookies or embedded third party content.