Improved Efficiency of a Linearly Homomorphic Cryptosystem

Abstract

We present an extended version of the Castagnos and Laguillaumie linearly homomorphic cryptosystem in which the non-maximal imaginary quadratic order is allowed to have conductor equal to a power of a product of distinct primes as opposed to a single prime. Numerical results obtained with an optimized C implementation demonstrate that this variation improves performance when large messages and exponents are used. When compared to the cryptosystems of Paillier and Bresson et al. at the same security levels, the basic version of Castagnos and Laguillaumie is the fastest at high security levels for small messages.