Lattice-based homomorphic encryption of vector spaces

Abstract

In this paper we introduce a new probabilistic lattice-based bounded homomorphic encryption scheme. For this scheme the sum of two encrypted messages is the encryption of the sum of two messages and the scheme is able to preserve a vector spave structure of the message. The size of the public key is rather large ap 3 Mb but the encryption and the decryption operations are very fast (of the same speed order than NTRU). The homomorphic operation, i.e. the addition of ciphertexts is dramatically fast compared to homomorphic schemes based on group theory like Paillier or El Gamal.