How to Realize Highly Accurate Computation with Fully Homomorphic Encryption

In recent years, as the number of cloud services increases, leakage of confidential information is a matter of concern. Techniques for processing data while preserving confidentiality of data are called secure computation, and secure computation based on fully homomorphic encryption (FHE for short) is one of the most important ways of realizing secure computation. FHE is a cryptosystem that can perform both arbitrary times of additions and multiplications of data in the encrypted state. Therefore, by using FHE, we can realize arbitrary operations in the encrypted state. However, it is not so easy to realize complex operations using FHE in practice. In particular, there are difficulties in realizing complex operations with high accuracy. Such computation is highly desired in various situations (e.g., in computing medical statistics). Nevertheless, the methodology to compute complex operations given a certain accuracy is not well studied so far. In this research, we propose a method to compute division and a u-th root in the encrypted state using FHE. In the proposed method, the result of an operation can achieve the given accuracy. We employ the n-th order maclaurin approximate polynomial to approximate division and a u-th root by homomorphic addition and multiplication. We evaluate the error of an approximation using a remainder term. Also, we implemented the proposed method and measured execution time for division and a square root.