Paper 2021/048

Efficient Lattice Gadget Decomposition Algorithm with Bounded Uniform Distribution

Sohyun Jeon
Hyang-Sook Lee
Jeongeun Park

A gadget decomposition algorithm is commonly used in many advanced lattice cryptography applications which support homomorphic operation over ciphertexts to control the noise growth. For a special structure of a gadget, the algorithm is digit decomposition. If such algorithm samples from a subgaussian distribution, that is, the output is randomized, it gives more benefits on output quality. One of important advantages is Pythagorean additivity which makes resulting noise contained in a ciphertext grow much less than naive digit decomposition. Therefore, the error analysis becomes cleaner and tighter than the use of other measures like $\ell_2$ and $\ell_\infty$. Even though such advantage can also be achieved by the use of discrete Gaussian sampling, it is not preferable for practical performance due to large factor in resulting noise and the complex computation of exponential function, whereas more relaxed probability condition is required for subgaussian distribution. Nevertheless, subgaussian sampling has barely received an attention so far, thus no practical algorithms was implemented before an efficient algorithm is presented by Genis et al., recently. In this paper, we present a practically efficient gadget decomposition algorithm where output follows a subgaussian distribution. We parallelize the existing practical subgaussian gadget decomposition algorithm, using bounded uniform distribution. Our algorithm is divided into two independent subalgorithms and only one algorithm depends on input. Therefore, the other algorithm can be considered as pre-computation. As an experimental result, our algorithm performs over 50\% better than the existing algorithm.

Available format(s)
Publication info
Published elsewhere. IEEE Access
Subgaussian distribution Gadget decomposition Bounded uniform distribution Lattice gadget
Contact author(s)
jeonsh099 @ ewhain net
hsl @ ewha ac kr
jeongeun park @ esat kuleuven be
2022-09-08: last of 8 revisions
2021-01-18: received
See all versions
Short URL
Creative Commons Attribution


      author = {Sohyun Jeon and Hyang-Sook Lee and Jeongeun Park},
      title = {Efficient Lattice Gadget Decomposition Algorithm with Bounded Uniform Distribution},
      howpublished = {Cryptology ePrint Archive, Paper 2021/048},
      year = {2021},
      note = {\url{}},
      url = {}
Note: In order to protect the privacy of readers, does not use cookies or embedded third party content.