Cryptology ePrint Archive: Report 2021/1664

Towards a Simpler Lattice Gadget Toolkit

Shiduo Zhang and Yang Yu

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.

Category / Keywords: public-key cryptography / lattice-based cryptography, Gaussian sampling, subgaussian sampling

Original Publication (in the same form): IACR-PKC-2022

Date: received 19 Dec 2021

Contact author: yang yu0986 at gmail com, zsd19 at mails tsinghua edu cn

Available format(s): PDF | BibTeX Citation

Version: 20211220:135723 (All versions of this report)

Short URL: ia.cr/2021/1664


[ Cryptology ePrint archive ]