Paper 2018/946

Building an Efficient Lattice Gadget Toolkit: Subgaussian Sampling and More

Nicholas Genise, Daniele Micciancio, and Yuriy Polyakov


Many advanced lattice cryptography applications require efficient algorithms for inverting the so-called "gadget" matrices, which are used to formally describe a digit decomposition problem that produces an output with specific (statistical) properties. The common gadget inversion problems are the classical (often binary) digit decomposition, subgaussian decomposition, Learning with Errors (LWE) decoding, and discrete Gaussian sampling. In this work, we build and implement an efficient lattice gadget toolkit that provides a general treatment of gadget matrices and algorithms for their inversion/sampling. The main contribution of our work is a set of new gadget matrices and algorithms for efficient subgaussian sampling that have a number of major theoretical and practical advantages over previously known algorithms. Another contribution deals with efficient algorithms for LWE decoding and discrete Gaussian sampling in the Residue Number System (RNS) representation. We implement the gadget toolkit in PALISADE and evaluate the performance of our algorithms both in terms of runtime and noise growth. We illustrate the improvements due to our algorithms by implementing a concrete complex application, key-policy attribute-based encryption (KP-ABE), which was previously considered impractical for CPU systems (except for a very small number of attributes). Our runtime improvements for the main bottleneck operation based on subgaussian sampling range from 18x (for 2 attributes) to 289x (for 16 attributes; the maximum number supported by a previous implementation). Our results are applicable to a wide range of other advanced applications in lattice cryptography, such as GSW-based homomorphic encryption schemes, leveled fully homomorphic signatures, key-hiding PRFs and other forms of ABE, some program obfuscation constructions, and more.

Available format(s)
Publication info
A minor revision of an IACR publication in EUROCRYPT 2019
FHELattice-based cryptographySamplingSubgaussiandiscrete gaussianTrapdoor lattices
Contact author(s)
ngenise @ eng ucsd edu
2019-03-12: revised
2018-10-09: received
See all versions
Short URL
Creative Commons Attribution


      author = {Nicholas Genise and Daniele Micciancio and Yuriy Polyakov},
      title = {Building an Efficient Lattice Gadget Toolkit: Subgaussian Sampling and More},
      howpublished = {Cryptology ePrint Archive, Paper 2018/946},
      year = {2018},
      note = {\url{}},
      url = {}
Note: In order to protect the privacy of readers, does not use cookies or embedded third party content.