Paper 2020/1549

High-Precision and Low-Complexity Approximate Homomorphic Encryption by Error Variance Minimization

Yongwoo Lee and Joonwoo Lee and Young-Sik Kim and HyungChul Kang and Jong-Seon No

Abstract

In this paper, we propose a high-precision and low-complexity Cheon-Kim-Kim-Song (CKKS) scheme (Asiacrypt '17) by reducing error and improving its bootstrapping through error variance minimization. The proposed algorithm allows us to leave more levels after bootstrapping, and thus, with practical accuracy, we reduce the degree of ciphertext polynomial of the CKKS scheme from 2^16 to 2^15. The sizes of the key and ciphertext are reduced by at least 1/4, which significantly reduces their computational complexity. Those are possible from the fact that a smaller scaling factor can be used with the proposed algorithms for the same precision since the following two contributions significantly reduce the error of the CKKS scheme, especially in bootstrapping. First, we apply the concept of signal-to-noise ratio (SNR) and propose a method of maximizing the SNR of encrypted data by reordering homomorphic operations. For that, the error variance is minimized instead of the upper bound of error when we deal with encrypted data. Especially, we propose lazy rescaling and lazy relinearization, which reduces computational complexity as well as error variance. Second, we propose a novel polynomial approximation specialized for the CKKS scheme from the same perspective of minimizing the error variance of the encrypted data. We mainly apply the approximation to the bootstrapping of the CKKS scheme, where we achieve a smaller bootstrap error compared to the prior arts. The performance improvement of the proposed algorithms for the CKKS scheme is verified by implementation over a well-known homomorphic encryption library, SEAL. Specifically, for very accurate bootstrapping, the proposed method achieves the same bootstrap error with only a depth of 8, whereas it requires a depth of 13 in the prior art.

Note: We added the use of a higher Hamming weight secret key, a smaller parameter (N=2^15) for practical precision, and a new baby-step giant-step algorithm with lazy rescaling and relinearization with some error fixes.