Batch Scheme Based on Fully Homomorphic Encryption-Symmetric Encryption Framework

Abstract:

All homomorphic encryption schemes proposed so far suffer from a very large ciphertext expansion, which is a very significant bottleneck in practice. In order to improve the transmission efficiency, Naehrig et al. proposed an idea of hybrid encryption, i.e. a user encrypt some plaintext m with a symmetric encryption scheme E under some private key k, and encrypt the private key k with a homomorphic encryption scheme under some public key pk, transmit a much smaller cipertext c′=(HEpk(k),Ek(m)) that cloud decompresses homomorphically into the HEpk(m) through a decryption circuit CE-1. In this paper, we extend the Fully Homomorphic EncryptionSymmetric Encryption framework into a batch one, i.e. we use the Chinese Remainder Theorem to pack l ciphertexts Ek(m0),…,Ek(ml-1) into a single C, send C′=(HEpk(k),C) to the cloud. Given C′, cloud only needs to homomorphically evaluate CE-1 for once to recover all HEpk(mi), rather than l times in original scheme. By this way, we can greatly reduce the times of homomorphically evaluating decryption circuit, which costs a lot of computation. We also give out an instance of batch GSW13FLIP scheme to explain in detail. Comparing to original scheme, our batch scheme can reduce the computational complexity from O~(λ3) to O~(λ2), where λ is security parameter of FLIP.