Generalized Bootstrapping Technique Based on Block Equality Test Algorithm

With the rapid development of cloud computation and big data, the data storage and outsource computation are delegated to the untrusted cloud, which has led to a series of challenging security and privacy threats. Fully homomorphic encryption can be used to protect the privacy of cloud data and solve the trust problem of third party. The key problem of achieving fully homomorphic encryption is how to reduce the increasing noise during the ciphertext evaluation. Bootstrapping procedure can refresh ciphertext with large error, such that the resulting ciphertext has potentially smaller error and allows being continuous homomorphic evaluation. In this paper, we investigated the bootstrapping procedure used to construct fully homomorphic encryption scheme. We proposed a new concept of block homomorphic equality test algorithm and gave an instance based on the FH-SIMD scheme. Furthermore, based on the block homomorphic equality test algorithm, we proposed a faster bootstrapping procedure with smaller bootstrapping keys. Both theory analysis and experiment simulation validate high performance of our bootstrapping algorithm.