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′=(HEpk(k),Ek(m)) that cloud decompresses homomorphically into the HEpk(m) through a decryption circuit CE-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 Ek(m0),…,Ek(ml-1) into a single C, send C′=(HEpk(k),C) to the cloud. Given C′, cloud only needs to homomorphically evaluate CE-1 for once to recover all HEpk(mi), 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.
