Approximate CRT-Based Gadget Decomposition for Fully Homomorphic Encryption
摘要
Managing noise growth is a central challenge in fully homomorphic encryption (FHE). Gadget decomposition mitigates this by representing elements as vectors whose inner product with a gadget vector approximately reconstructs the original value. Radix-based decompositions support approximation but CRT-based ones have, so far, required exactness. We introduce, for the first time, CRT-based gadget decompositions in the approximate setting, combining the benefits of approximate decompositions with the structural advantages of CRT-based methods. This enables efficient blind rotation and (programmable) bootstrapping in TFHE using only native arithmetic while increasing parallelism. On a typical FPGA (17-bit multipliers), our approach achieves a speedup of over \(2\times \) and approximately \(50\%\) lower area than comparable radix-based approximate designs. The methodology also reduces bandwidth, memory, and compute in settings with large ciphertext moduli (e.g., 128-bit), benefiting both hardware and software implementations.