Improved Homomorphic Discrete Fourier Transforms and FHE Bootstrapping

作者: Kyoohyung Han , Minki Hhan , Jung Hee Cheon

DOI: 10.1109/ACCESS.2019.2913850

关键词:

摘要: Homomorphic encryption (HE), which enables computation on ciphertexts without any leakage, rise as a most promising solution for privacy-preserving data processing, including secure machine learning and out-sourcing computation. Despite the extensive applicability of HE, current constructions are sometimes considered impractical due to its inefficiency. In this paper, we propose improvements linear transformation in bootstrapping, technique allowing infinite number operation homomorphic discrete Fourier (DFT) using batch encryption. We observe that multiplication sparse diagonal matrix ciphertext vector can be done within O(1) computations. This observation induces faster algorithm bootstrapping DFT. To achieve this, use Cooley-Tukey factorization construct new recursive bootstrapping. Our method with radix r only requires O(r log r n) constant O(√r rotations by consuming O(log depth when input size is n. The previous used library, library implements approximate computation, O(n) O(√n), respectively. show performance improvement, implement our top library. implementation, along further few techniques, these algorithms significant compared algorithm. New DFT length 2 14 takes about 8s results 150 times than method. Furthermore, 2 minutes ℂ 32768 plaintext space 8-bit precision, 26 hours same bit precision

参考文章(0)