F-FHEW: High-Precision Approximate Homomorphic Encryption with Batch Bootstrapping

F-FHEW: High-Precision Approximate Homomorphic Encryption with Batch Bootstrapping

연구 분야: Cryptography

학회: Australasian Conference on Information Security and Privacy

Floating-point fully homomorphic encryption (FPFHE) supports arbitrary computation on ciphertexts and yields approximate results. On one hand, for the state-of-the-art, the CKKS-like scheme (Jutla et al., EUROCRYPT 2022) achieves a precision of 100-bit decimal as the messages originally include some encoding noise, as well as some additional errors will be generated by bootstrapping operation. Nonetheless, operations with higher precision are also appreciated by various kinds of applications, such as Semidefinite Programming requiring 128-bit precision. On the other hand, the CKKS-like scheme is very computationally intensive. Compared to processing the same data in clear, it is slower, less efficient, and more energy-consuming. In this paper, we propose a high-precision approximate homomorphic encryption with batch bootstrapping based on the Gentry-Sahai-Waters scheme over rings (or RingGSW). Firstly, to support a precision of 128-bit decimal, mapping floating-point numbers to B-based cyclotomic polynomials with \(128-\)fraction coefficients. Furthermore, we use polynomial truncation in homomorphic multiplication to support deep-level circuit with upper-bound depth \(O(\log q/(B_g\sigma ))\). Next, we utilize trace function computation to achieve batch multiplication, achieving an amortized multiplication complexity of \(O(n^{1.75}\log q)\). Overall, the proposed scheme has half amortized multiplication time and supports deeper-level circuit \(>O(\log q_0/(B_g\sigma ))\), when compared to the CKKS-like scheme.