International Association for Cryptologic Research

International Association
for Cryptologic Research


Towards a Simpler Lattice Gadget Toolkit

Shiduo Zhang , Tsinghua University
Yang Yu , Tsinghua University
Search ePrint
Search Google
Conference: PKC 2022
Abstract: 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.
Video from PKC 2022
  title={Towards a Simpler Lattice Gadget Toolkit},
  author={Shiduo Zhang and Yang Yu},