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.

错误:搜索内容不能为空,请输入英文关键词
错误:关键词超出字数限制,请精简
高级检索

Approximate CRT-Based Gadget Decomposition for Fully Homomorphic Encryption

  • Olivier Bernard,
  • Marc Joye

摘要

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.