Paper 2025/087

On Gaussian Sampling for q-ary Lattices and Linear Codes with Lee Weight

Maiara F. Bollauf, Simula UiB
Maja Lie, Imperial College London
Cong Ling, Imperial College London
Abstract

We show that discrete Gaussian sampling for a q-ary lattice is equivalent to codeword sampling for a linear code over Zq with the Lee weight. This insight allows us to derive the theta series of a q-ary lattice from the Lee weight distribution of the associated code. We design a novel Gaussian sampler for q-ary lattices assuming an oracle that computes the symmetrized weight enumerator of the associated code. We apply this sampler to well-known lattices, such as the , Barnes-Wall, and Leech lattice, highlighting both its advantages and limitations, which depend on the underlying code properties. For certain root lattices, we show that the sampler is indeed efficient, forgoing the need to assume an oracle. We also discuss applications of our results in digital signature schemes and the Lattice Isomorphism Problem. In many cases, our sampler achieves a significant speed-up compared to state-of-the-art sampling algorithms in cryptographic applications.

Metadata
Available format(s)
PDF
Category
Foundations
Publication info
Preprint.
Keywords
Lattice Gaussian samplingLee weightq-ary latticeSchur productTheta series
Contact author(s)
maiarabollauf @ gmail com
m lie22 @ imperial ac uk
c ling @ imperial ac uk
History
2025-01-22: revised
2025-01-20: received
See all versions
Short URL
https://ia.cr/2025/087
License
Creative Commons Attribution
CC BY

BibTeX

@misc{cryptoeprint:2025/087,
      author = {Maiara F. Bollauf and Maja Lie and Cong Ling},
      title = {On Gaussian Sampling for $q$-ary Lattices and Linear Codes with Lee Weight},
      howpublished = {Cryptology {ePrint} Archive, Paper 2025/087},
      year = {2025},
      url = {https://eprint.iacr.org/2025/087}
}
Note: In order to protect the privacy of readers, eprint.iacr.org does not use cookies or embedded third party content.