We show that discrete Gaussian sampling for a q-ary lattice is equivalent to codeword sampling for a linear code over \(\mathbb {Z}_q\) with the Lee weight profile. 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 \(\operatorname {E}_8\) , 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. In many cases, our sampler achieves a significant speed-up compared to state-of-the-art sampling algorithms in cryptographic applications.

错误:搜索内容不能为空,请输入英文关键词
错误:关键词超出字数限制,请精简
高级检索

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

  • Maiara F. Bollauf,
  • Maja Lie,
  • Cong Ling

摘要

We show that discrete Gaussian sampling for a q-ary lattice is equivalent to codeword sampling for a linear code over \(\mathbb {Z}_q\) with the Lee weight profile. 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 \(\operatorname {E}_8\) , 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. In many cases, our sampler achieves a significant speed-up compared to state-of-the-art sampling algorithms in cryptographic applications.