Paper 2021/1664

Towards a Simpler Lattice Gadget Toolkit

Shiduo Zhang and Yang Yu


As a building block, gadgets and associated algorithms are widely used in advanced lattice cryptosystems. The gadget algorithms for power-of-base moduli are very efficient and simple, however the current algorithms for arbitrary moduli are still complicated and practically more costly despite several efforts. Considering the necessity of arbitrary moduli, developing simpler and more practical gadget algorithms for arbitrary moduli is crucial to improving the practical performance of lattice based applications. In this work, we propose two new gadget sampling algorithms for arbitrary moduli. Our first algorithm is for gadget Gaussian sampling. It is simple and efficient. One distinguishing feature of our Gaussian sampler is that it does not need floating-point arithmetic, which makes it better compatible with constrained environments. Our second algorithm is for gadget subgaussian sampling. Compared with the existing algorithm, it is simpler, faster, and requires asymptotically less randomness. In addition, our subgaussian sampler achieves an almost equal quality for different practical parameters. Overall these two algorithms provide simpler options for gadget algorithms and enhance the practicality of the gadget toolkit.

Available format(s)
Public-key cryptography
Publication info
Published by the IACR in PKC 2022
lattice-based cryptographyGaussian samplingsubgaussian sampling
Contact author(s)
yang yu0986 @ gmail com
zsd19 @ mails tsinghua edu cn
2021-12-20: received
Short URL
Creative Commons Attribution


      author = {Shiduo Zhang and Yang Yu},
      title = {Towards a Simpler Lattice Gadget Toolkit},
      howpublished = {Cryptology ePrint Archive, Paper 2021/1664},
      year = {2021},
      note = {\url{}},
      url = {}
Note: In order to protect the privacy of readers, does not use cookies or embedded third party content.