Paper 2020/1549

High-Precision Approximate Homomorphic Encryption by Error Variance Minimization

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

Abstract

The recent development of machine learning and cloud computing arises a new privacy problem; how can one outsource computation on confidential data? Homomorphic encryption (HE) is a solution for that as it allows computation on encrypted data without decryption. The Cheon-Kim-Kim-Song (CKKS) scheme (Asiacrypt '17) is one of the highlighted fully homomorphic encryption (FHE) schemes as it is efficient to deal with encrypted real numbers, which are the usual data type for many applications such as machine learning. This paper proposes a generally applicable method to achieve high-precision approximate FHE using the following two techniques. 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 in the CKKS scheme. For that, the error variance is minimized instead of the upper bound of error when we deal with encrypted data. Second, we propose a novel polynomial approximation method for the CKKS scheme from the same perspective of minimizing error variance. We especially apply the approximation method to the bootstrapping of the CKKS scheme, where we achieve the smaller error variance in the bootstrapping compared to the prior arts. The performance improvement of the proposed methods for the CKKS scheme is verified by implementation over HE libraries: HEAAN and SEAL. The implementation results show that the message precision of the CKKS scheme is improved by reordering homomorphic operations and using the proposed polynomial approximation. Specifically, the proposed method uses only depth 8, although the bootstrapping precision is increased by 1 bit compared to that of the previous method using depth 11. We also suggest a loose lower bound of bootstrapping error in the CKKS scheme and show that the proposed method’s bootstrapping error is only 2.8 bits on average larger than the lower bound. Therefore, various applications’ quality of services using the proposed CKKS scheme, such as privacy-preserving machine learning, can be improved without compromising performance and security.