Paper 2019/688

Better Bootstrapping for Approximate Homomorphic Encryption

Kyoohyung Han and Dohyeong Ki

Abstract

After Cheon et al. (Asiacrypt' 17) proposed approximate homomorphic encryption for operations between encrypted real (or complex) numbers, this scheme is widely used in various fields with the needs on privacy-preserving in data analysis. After that, the bootstrapping method is firstly proposed by Cheon et al. (Eurocrypt' 18) by replacing modulus reduction with sine function. In this paper, we generalize Full-RNS variant of HEAAN scheme to reduce the number of special primes which are used in key-switching. As a result, our scheme can use a smaller ring dimension or supports more depth computation without bootstrapping while preserving the same security level. And, we propose a bootstrapping specified polynomial approximation method to evaluate sine function in an encrypted state. In our method, the degree of a polynomial approximation is related to the plaintext size. This gives a smaller number of non-scalar multiplications which is about half of the previous work. With our variant of Full-RNS scheme and new sine evaluation method, we firstly implement bootstrapping on Full-RNS variant of approximate homomorphic encryption. Our implementation shows that bootstrapping takes about 120 seconds with 19-bit precisions.