A Privacy-preserving BGN-type Parallel Homomorphic Encryption Algorithm Based on LWE

Abstract

Although the rapid development of cloud computing brings many conveniences to people’s lives, it also leads to the problems of user data privacy protection and the massive bandwidth resource consumption caused by frequent access to cloud servers. A feasible solution is to combine the Homomorphic Encryption (HE) technique to realize the efficient operation of ciphertext without decryption. The low encryption efficiency is a common issue faced by both Partially Homomorphic Encryption (PHE) algorithm and Fully Homomorphic Encryption (FHE) algorithm. To this end, based on the cryptosystem of Boneh, Goh and Nissim (BGN), we propose an efficient BGN-type parallel homomorphic encryption algorithm to address this issue, which security is based on the hardness of the Learning with Errors problem (LWE). Specifically, the proposed algorithm utilizes the characteristics of multi-nodes in cloud environment to conduct parallel encryption through block matrix multiplication, and simultaneously conduct the group-wise ciphertext computations. The experimental results show that, in a 16-core 4-node cluster with MapReduce environment, the proposed encryption algorithm achieves the maximum speedup up to 5.3, which meets the practical requirements for the implementing efficient homomorphic encryption in cloud computing environment.