Paper 2023/535

Practical Randomized Lattice Gadget Decomposition With Application to FHE

Sohyun Jeon, Ewha Womans University
Hyang-Sook Lee, Ewha Womans University
Jeongeun Park, KU Leuven

Gadget decomposition is widely used in lattice based cryptography, especially homomorphic encryption (HE) to keep the noise growth slow. If it is randomized following a subgaussian distribution, it is called subgaussian (gadget) decomposition which guarantees that we can bound the noise contained in ciphertexts by its variance. This gives tighter and cleaner noise bound in average case, instead of the use of its norm. Even though there are few attempts to build efficient such algorithms, most of them are still not practical enough to be applied to homomorphic encryption schemes due to somewhat high overhead compared to the deterministic decomposition. Furthermore, there has been no detailed analysis of existing works. Therefore, HE schemes use the deterministic decomposition algorithm and rely on a Heuristic assumption that every output element follows a subgaussian distribution independently. In this work, we introduce a new practical subgaussian gadget decomposition algorithm which has the least overhead (less than 14\%) among existing works for certain parameter sets, by combining two previous works. In other words, we bring an existing technique based on an uniform distribution to a simpler and faster design (PKC' 22) to exploit parallel computation, which allows to skip expensive parts due to pre-computation, resulting in even simpler and faster algorithm. When the modulus is large (over 100-bit), our algorithm is not always faster than the other similar work. Therefore, we give a detailed comparison, even for large modulus, with all the competitive algorithms for applications to choose the best algorithm for their choice of parameters.

Available format(s)
Publication info
Published elsewhere. ESORICS 2023
Subgaussian DecompositionRandomized Gadget DecompositionHomomorphic Encryption
Contact author(s)
jeonsh099 @ ewhain net
hsl @ ewha ac kr
jeongeun park @ esat kuleuven be
2023-08-17: revised
2023-04-13: received
See all versions
Short URL
Creative Commons Attribution


      author = {Sohyun Jeon and Hyang-Sook Lee and Jeongeun Park},
      title = {Practical Randomized Lattice Gadget Decomposition With Application to {FHE}},
      howpublished = {Cryptology ePrint Archive, Paper 2023/535},
      year = {2023},
      note = {\url{}},
      url = {}
Note: In order to protect the privacy of readers, does not use cookies or embedded third party content.